mersenneforum.org > Math Complexity analysis of 3 tests
 Register FAQ Search Today's Posts Mark Forums Read

 2013-03-19, 14:45 #1 kurtulmehtap   Sep 2009 22×32 Posts Complexity analysis of 3 tests Dear All, Which one of the following tests have the minimum complexity to find extremely large primes? 1. Lucas lehmer Test for Mersenne Numbers 2. Testing generalized Fermat Numbers for primality 3. Trial factoring Fermat Numbers to find large Proth primes. Thanks
 2013-03-19, 15:23 #2 TimSorbet Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 11×389 Posts Mersenne numbers. There's a reason the largest known prime has been a Mersenne for decades, now.
2013-03-19, 16:48   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165248 Posts

Quote:
 Originally Posted by kurtulmehtap Dear All, Which one of the following tests have the minimum complexity to find extremely large primes? 1. Lucas lehmer Test for Mersenne Numbers 2. Testing generalized Fermat Numbers for primality 3. Trial factoring Fermat Numbers to find large Proth primes. Thanks
item 3 can not be defined unless one gives an upper bound on the
trial factoring bit level.

 2013-03-19, 17:56 #4 axn     Jun 2003 22·32·151 Posts 1 & 2 have similar "complexity". 3 is more "complex" (and gets worse as the k part of k*2^n+1 grows). I'm using "complexity" to mean "runtime as a function of size"
2013-03-19, 19:27   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts

Quote:
 Originally Posted by axn 1 & 2 have similar "complexity". 3 is more "complex" (and gets worse as the k part of k*2^n+1 grows). I'm using "complexity" to mean "runtime as a function of size"
Yes, indeed. That is what it means and that is how I took it.

2013-03-19, 19:30   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

Quote:
 Originally Posted by R.D. Silverman Yes, indeed. That is what it means and that is how I took it.
Actually, (1) and (2) have very DIFFERENT complexities. There are
no fast LL-type tests for generalized Fermat numbers. There is
only AKS or APR-Cl or ECPP.

For Fermat numbers there is Pepin's test, which has the same
complexity as LL. It takes O(log N) multiplications mod N where N
is the number being tested.

2013-03-19, 22:48   #7
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

178F16 Posts

Quote:
 Originally Posted by R.D. Silverman Actually, (1) and (2) have very DIFFERENT complexities. There are no fast LL-type tests for generalized Fermat numbers. There is only AKS or APR-Cl or ECPP. For Fermat numbers there is Pepin's test, which has the same complexity as LL. It takes O(log N) multiplications mod N where N is the number being tested.
Because of the above mentioned problem the subset of the GFN(depending on definition) b^2^n+1 is what was being referred to.

2013-03-20, 12:44   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by henryzz Because of the above mentioned problem the subset of the GFN(depending on definition) b^2^n+1 is what was being referred to.
This was clear.

Now what?

2013-03-20, 13:29   #9
axn

Jun 2003

22×32×151 Posts

Quote:
 Originally Posted by R.D. Silverman This was clear. Now what?
Why would that form require a general purpose proving algo? Straightforward N-1 test would be sufficient, no?

2013-03-20, 13:31   #10
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

603110 Posts

Quote:
 Originally Posted by axn Why would that form require a general purpose proving algo? Straightforward N-1 test would be sufficient, no?
Not for a^2^n+b^2^n with a and b not equal to 1. There are two definitions for GFNs. We usually refer to the other one.

2013-03-20, 14:15   #11
axn

Jun 2003

124748 Posts

Quote:
 Originally Posted by R.D. Silverman There are no fast LL-type tests for generalized Fermat numbers.
If we're limiting our discussions to b^2^N+1, current state-of-the-art allows you to test small b values (on the order of 10^7), large N (on the order of 20-30). So N-1 test will be applicable. I don't know how to efficiently do it for large b (where we can't get necessary factorization of b), but then no one would be searching with that kind of parameters.

PS:- Since the context is about finding primes, I had implicitly factored in trial factoring as well as PRP testing capabilities in my answer.
PPS:- I consider GFN-WR search by PrimeGrid to be a legitimate contender for find a world record prime.

 Similar Threads Thread Thread Starter Forum Replies Last Post yih117 Math 5 2018-02-02 02:49 carpetpool Miscellaneous Math 4 2017-02-09 19:26 Mr. P-1 Computer Science & Computational Number Theory 5 2013-04-02 15:47 T.Rex Math 9 2007-05-29 21:15 ixfd64 Math 14 2005-12-01 22:50

All times are UTC. The time now is 19:24.

Fri Feb 3 19:24:26 UTC 2023 up 169 days, 16:52, 1 user, load averages: 1.34, 1.10, 1.10