mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Homework Help (https://www.mersenneforum.org/forumdisplay.php?f=78)
-   -   question (https://www.mersenneforum.org/showthread.php?t=12120)

ATH 2009-07-05 00:22

question
 
Its not really homework, just something I'm wondering about.

Given 2 primes p and q I want to find the smallest k>0 so (2*k*p+1) = 0 (mod q)

Is there any faster way than trying all k from 1 until you find one that works?

davieddy 2009-07-05 03:49

I helieve you use the Extended Euclidean Algorithm.

davieddy 2009-07-05 17:53

Hope to spare you the indignities I suffered when I asked
the same question for the same reason:smile:

[URL]http://mersenneforum.org/showthread.php?t=9700[/URL]

David

ATH 2009-07-06 00:41

Thanks, it was just something like this I was looking for:

(2kp+1)=0 (mod q) => 2kp+1= c*q => c*q - 2kp = 1

Then I can find c and more importantly -2*k my using the algorithm on GCD(p,q). Allready tested it and it works great.

davieddy 2009-07-06 07:41

[quote=ATH;179865]Thanks, it was just something like this I was looking for:

(2kp+1)=0 (mod q) => 2kp+1= c*q => c*q - 2kp = 1

Then I can find c and more importantly -2*k my using the algorithm on GCD(p,q). Allready tested it and it works great.[/quote]
If you did GCD(2p,q) you'd get -k. Is this any improvement?

I see Davar55 has revived that embarrassing thread I cited in
the Math forum!


All times are UTC. The time now is 16:38.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.