20151007, 21:04  #1 
Dec 2014
2^{2}·3^{2}·7 Posts 
Pocklington's Theorem
This theorem has expression
gcd(a^^{(n1)/q}1,n) = 1 how does one compute that efficiently for large n ? 
20151008, 02:22  #2 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·3·739 Posts 
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 20151008 at 02:27 
20151008, 04:08  #3 
Dec 2014
2^{2}×3^{2}×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. 
20151008, 06:33  #4  
Romulan Interpreter
Jun 2011
Thailand
22A4_{16} Posts 
Quote:
2000 in binary is 111 1101 0000 compute 2^2000 (mod 10000) Start with 2, ignore the first 1 on the binary representation 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(93761,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 20151008 at 06:35 

20151008, 08:54  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
14262_{8} Posts 
But gcd(A mod B, B) is the same as GCD(A,B), so you can compute 2^20001 mod 10000, by the method LaurV went through, and then do the GCD of two much smaller numbers.

20151008, 12:52  #6  
Nov 2003
2^{6}×113 Posts 
Quote:
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 20151008 at 12:53 Reason: typo 

20151009, 22:31  #7 
Dec 2014
2^{2}×3^{2}×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 LehmerPocklington's Theorem (page 122). Most people use it for an n1 style primality test. I can not find a link to the version in the book. so it is reproduced below. Theorem 4.13. LehmerPocklington's Theorem. Suppose N1 = R*F [formula not reproduced, basically we know the prime factors q_{j} of F but not R], GCD(F,R) = 1. If there is an integer a, satisfying GCD(a^{(N1)/q[SUB]j[/SUB]}1,N) = 1 for all j = 1, 2, ..., n. and such that a^{N1} = 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=2^{p}1, it looks factors of the form r = 2*k*p+1. So I was wondering what if the LehmerPocklington's Theorem F value was sometimes much larger than 2*p and would make trial factoring faster. The computer results When N=2^{p}1, then looking for factors of N1 usually finds a bunch. But when N is composite, all of the factors of F fail the LehmerPocklington's Theorem tests except for q_{j} = p (for the couple hundred small p values I tested). Even p fails when it is a factor twice. Also q_{j} = 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 LehmerPocklington's Theorem tests. Does Number Theory predict this Computational Observation? 
20151013, 13:55  #8 
Aug 2002
Buenos Aires, Argentina
2465_{8} Posts 
For almost all composite Mersenne numbers, a^{N1} 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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ErdosKac Theorem  flouran  Math  84  20090520 21:37 
Koebe's 1/4 Theorem  wpolly  Math  3  20081112 12:31 
Number Theorem  herege  Math  25  20061118 09:54 
StÃ¸rmer's theorem  grandpascorpion  Factoring  0  20060910 04:59 
Lagrange's Theorem  Numbers  Math  2  20050907 15:22 