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

 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:

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.