 mersenneforum.org Pocklington's Theorem
 Register FAQ Search Today's Posts Mark Forums Read 2015-10-07, 21:04 #1 bgbeuning   Dec 2014 22·32·7 Posts Pocklington's Theorem This theorem has expression gcd(a^(n-1)/q-1,n) = 1 how does one compute that efficiently for large n ?   2015-10-08, 02:22   #2
LaurV
Romulan Interpreter

Jun 2011
Thailand

22·3·739 Posts Quote:
 Originally Posted by bgbeuning This theorem has expression gcd(a(n-1)/q-1,n) = 1 how does one compute that efficiently for large n ?
Fixed the expression for you. Powering is executed (mod n), and powermod is a very efficient method, you do as many squarings (mod n) as bits in n, and as many multiplications with a (mod n) as bits 1 in n. Look for "modular exponentiation". It is like the first step of Euclid's algorithm, i.e. gcd(a,b)=gcd(a (mod b), b).

Last fiddled with by LaurV on 2015-10-08 at 02:27   2015-10-08, 04:08 #3 bgbeuning   Dec 2014 22×32×7 Posts The part I am having trouble with is the -1 . gcd( 2^2000, 10000 ) is much different than gcd( (2^2000)-1, 10000 ) Thanks for the reply.   2015-10-08, 06:33   #4
LaurV
Romulan Interpreter

Jun 2011
Thailand

22A416 Posts Quote:
 Originally Posted by bgbeuning The part I am having trouble with is the -1 . gcd( 2^2000, 10000 ) is much different than gcd( (2^2000)-1, 10000 ) Thanks for the reply.
Huh???
2000 in binary is 111 1101 0000
compute 2^2000 (mod 10000)
Take out the second 1 from the binary representation.
Square, 2^2 (mod 10000)=4 and because it was a 1, multiply by 2, 4*2=8 (mod 10000).
Take out the third 1 from the binary representation.
Square, 8^2 (mod 10000)=64 and because it was a 1, multiply by 2, 64*2=128 (mod 10000).
Take out the forth 1 from the binary representation.
Square, 128^2 (mod 10000)=6384 and because it was a 1, multiply by 2, 6384*2=2768 (mod 10000).
Take out the fifth 1 from the binary representation.
Square, 2768^2 (mod 10000)=1824 and because it was a 1, multiply by 2, 1824*2=3648 (mod 10000).
Take out the 0 from the binary representation.
Square, 3648^2 (mod 10000)=7904 and because it was a 0, don't multiply by 2
Take out the next 1 from the binary representation.
Square, 7904^2 (mod 10000)=3216 and because it was a 1, multiply by 2, 3216*2=6432 (mod 10000).
Take out the next 0 from the binary representation.
Square, 6432^2 (mod 10000)=624 and because it was a 0, don't multiply by 2
Take out the next 0 from the binary representation.
Square, 624^2 (mod 10000)=9376 and because it was a 0, don't multiply by 2
Take out the next 0 from the binary representation.
Square, 9376^2 (mod 10000)=9376 and because it was a 0, don't multiply by 2
(look maa, I actually found a root, hahaha)
Take out the last 0 from the binary representation.
Square, 9376^2 (mod 10000)=9376 and because it was a 0, don't multiply by 2
The string finished, end of story.

Gcd(9376-1,10000)=625

I only used a pocket calculator and less than 5 minutes of my precious time.

edit: and I did the "mod 10000" step in my head, EVERYTIME Last fiddled with by LaurV on 2015-10-08 at 06:35   2015-10-08, 08:54   #5
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

142628 Posts Quote:
 Originally Posted by bgbeuning The part I am having trouble with is the -1 . gcd( 2^2000, 10000 ) is much different than gcd( (2^2000)-1, 10000 ) Thanks for the reply.
But gcd(A mod B, B) is the same as GCD(A,B), so you can compute 2^2000-1 mod 10000, by the method LaurV went through, and then do the GCD of two much smaller numbers.   2015-10-08, 12:52   #6
R.D. Silverman

Nov 2003

26×113 Posts Quote:
 Originally Posted by fivemack But gcd(A mod B, B) is the same as GCD(A,B), so you can compute 2^2000-1 mod 10000, by the method LaurV went through, and then do the GCD of two much smaller numbers.
And we have a winner!

This thread is yet another instance of 'compute first and learn the math later'........

The math, in this case, is basic modular arithmetic.

Last fiddled with by R.D. Silverman on 2015-10-08 at 12:53 Reason: typo   2015-10-09, 22:31 #7 bgbeuning   Dec 2014 22×32×7 Posts I had it implemented as you explain, but I was not comfortable it was accurate. Thanks for making it clear. I was skimming the book "Prime Numbers and Computer Methods for Factorization, Second Edition, by Hans Riesel" and came across the Lehmer-Pocklington's Theorem (page 122). Most people use it for an n-1 style primality test. I can not find a link to the version in the book. so it is reproduced below. Theorem 4.13. Lehmer-Pocklington's Theorem. Suppose N-1 = R*F [formula not reproduced, basically we know the prime factors qj of F but not R], GCD(F,R) = 1. If there is an integer a, satisfying GCD(a(N-1)/q[SUB]j[/SUB]-1,N) = 1 for all j = 1, 2, ..., n. and such that aN-1 = 1 (mod N), then each prime factor r [changed from p] of N has the form r = F*m+1 [ for m = 1, 2, ...]. [End of Theorem] When prime95 is doing trial factoring on N=2p-1, it looks factors of the form r = 2*k*p+1. So I was wondering what if the Lehmer-Pocklington's Theorem F value was sometimes much larger than 2*p and would make trial factoring faster. The computer results When N=2p-1, then looking for factors of N-1 usually finds a bunch. But when N is composite, all of the factors of F fail the Lehmer-Pocklington's Theorem tests except for qj = p (for the couple hundred small p values I tested). Even p fails when it is a factor twice. Also qj = 2 fails which makes this plan worse that 2*k*p+1. But when N is one of the first 27 Mersenne primes, then ALL of the factors of F pass the Lehmer-Pocklington's Theorem tests. Does Number Theory predict this Computational Observation?   2015-10-13, 13:55 #8 alpertron   Aug 2002 Buenos Aires, Argentina 24658 Posts For almost all composite Mersenne numbers, aN-1 is not 1 in general because N is composite, so the Pocklington theorem will not be helpful to generate an enhanced trial factoring algorithm. And since LL is faster than the calculations to be done when you check the theorem condition, this does not help GIMPS at all.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post flouran Math 84 2009-05-20 21:37 wpolly Math 3 2008-11-12 12:31 herege Math 25 2006-11-18 09:54 grandpascorpion Factoring 0 2006-09-10 04:59 Numbers Math 2 2005-09-07 15:22

All times are UTC. The time now is 02:22.

Mon Oct 26 02:22:14 UTC 2020 up 45 days, 23:33, 0 users, load averages: 1.91, 1.83, 1.81