mersenneforum.org question
 Register FAQ Search Today's Posts Mark Forums Read

 2009-07-05, 00:22 #1 ATH Einyen     Dec 2003 Denmark 5×683 Posts 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? Last fiddled with by ATH on 2009-07-05 at 00:22
 2009-07-05, 03:49 #2 davieddy     "Lucan" Dec 2006 England 2×3×13×83 Posts I helieve you use the Extended Euclidean Algorithm.
 2009-07-05, 17:53 #3 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts Hope to spare you the indignities I suffered when I asked the same question for the same reason http://mersenneforum.org/showthread.php?t=9700 David
 2009-07-06, 00:41 #4 ATH Einyen     Dec 2003 Denmark 5×683 Posts 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. Last fiddled with by ATH on 2009-07-06 at 00:52
2009-07-06, 07:41   #5
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by ATH 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.
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!

Last fiddled with by davieddy on 2009-07-06 at 07:42

All times are UTC. The time now is 01:20.

Sun Dec 4 01:20:24 UTC 2022 up 107 days, 22:48, 0 users, load averages: 1.12, 1.29, 1.19