mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2013-03-19, 14:45   #1
kurtulmehtap
 
Sep 2009

22×32 Posts
Default 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
kurtulmehtap is offline   Reply With Quote
Old 2013-03-19, 15:23   #2
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11×389 Posts
Default

Mersenne numbers. There's a reason the largest known prime has been a Mersenne for decades, now.
TimSorbet is offline   Reply With Quote
Old 2013-03-19, 16:48   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

165248 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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
As asked, your question has no answer, since the complexity for
item 3 can not be defined unless one gives an upper bound on the
trial factoring bit level.
R.D. Silverman is offline   Reply With Quote
Old 2013-03-19, 17:56   #4
axn
 
axn's Avatar
 
Jun 2003

22·32·151 Posts
Default

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"
axn is offline   Reply With Quote
Old 2013-03-19, 19:27   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts
Default

Quote:
Originally Posted by axn View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-03-19, 19:30   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

750810 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-03-19, 22:48   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

178F16 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
henryzz is offline   Reply With Quote
Old 2013-03-20, 12:44   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts
Default

Quote:
Originally Posted by henryzz View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2013-03-20, 13:29   #9
axn
 
axn's Avatar
 
Jun 2003

22×32×151 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This was clear.

Now what?
Why would that form require a general purpose proving algo? Straightforward N-1 test would be sufficient, no?
axn is offline   Reply With Quote
Old 2013-03-20, 13:31   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

603110 Posts
Default

Quote:
Originally Posted by axn View Post
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.
henryzz is offline   Reply With Quote
Old 2013-03-20, 14:15   #11
axn
 
axn's Avatar
 
Jun 2003

124748 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sublinear complexity of trial division? yih117 Math 5 2018-02-02 02:49
Complexity of Chinese Remainder Theorem carpetpool Miscellaneous Math 4 2017-02-09 19:26
What is the time complexity of base conversion? Mr. P-1 Computer Science & Computational Number Theory 5 2013-04-02 15:47
Complexity of LLT T.Rex Math 9 2007-05-29 21:15
complexity of Pepin's test 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔