20130319, 14:45  #1 
Sep 2009
2^{2}·3^{2} 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 
20130319, 15:23  #2 
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.

20130319, 16:48  #3  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,889 Posts 
Quote:
item 3 can not be defined unless one gives an upper bound on the trial factoring bit level. 

20130319, 17:56  #4 
Jun 2003
2^{2}·3·5·7·13 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" 
20130319, 19:27  #5 
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,889 Posts 

20130319, 19:30  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,889 Posts 
Quote:
no fast LLtype tests for generalized Fermat numbers. There is only AKS or APRCl 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. 

20130319, 22:48  #7  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
3^{3}·227 Posts 
Quote:


20130320, 12:44  #8 
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,889 Posts 

20130320, 13:29  #9 
Jun 2003
1554_{16} Posts 

20130320, 13:31  #10 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
3^{3}·227 Posts 

20130320, 14:15  #11  
Jun 2003
1010101010100_{2} Posts 
Quote:
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 GFNWR search by PrimeGrid to be a legitimate contender for find a world record prime. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sublinear complexity of trial division?  yih117  Math  5  20180202 02:49 
Complexity of Chinese Remainder Theorem  carpetpool  Miscellaneous Math  4  20170209 19:26 
What is the time complexity of base conversion?  Mr. P1  Computer Science & Computational Number Theory  5  20130402 15:47 
Complexity of LLT  T.Rex  Math  9  20070529 21:15 
complexity of Pepin's test  ixfd64  Math  14  20051201 22:50 