mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2015-10-07, 21:04   #1
bgbeuning
 
Dec 2014

22·32·7 Posts
Default Pocklington's Theorem

This theorem has expression

gcd(a^(n-1)/q-1,n) = 1

how does one compute that efficiently for large n ?
bgbeuning is offline   Reply With Quote
Old 2015-10-08, 02:22   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
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
LaurV is offline   Reply With Quote
Old 2015-10-08, 04:08   #3
bgbeuning
 
Dec 2014

22×32×7 Posts
Default

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.
bgbeuning is offline   Reply With Quote
Old 2015-10-08, 06:33   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22A416 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
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)
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(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
LaurV is offline   Reply With Quote
Old 2015-10-08, 08:54   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

142628 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
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.
fivemack is offline   Reply With Quote
Old 2015-10-08, 12:52   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2015-10-09, 22:31   #7
bgbeuning
 
Dec 2014

22×32×7 Posts
Default

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?
bgbeuning is offline   Reply With Quote
Old 2015-10-13, 13:55   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24658 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Erdos-Kac Theorem flouran Math 84 2009-05-20 21:37
Koebe's 1/4 Theorem wpolly Math 3 2008-11-12 12:31
Number Theorem herege Math 25 2006-11-18 09:54
Størmer's theorem grandpascorpion Factoring 0 2006-09-10 04:59
Lagrange's Theorem 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.