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? 
I helieve you use the Extended Euclidean Algorithm.

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 
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=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.