mersenneforum.org > Math Complexity analysis of 3 tests
 User Name Remember Me? Password
 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

22·1,889 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
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.

 2013-03-19, 17:56 #4 axn     Jun 2003 22·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"
2013-03-19, 19:27   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,889 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

22·1,889 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)

33·227 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,889 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

155416 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)

33·227 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

10101010101002 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 01:12.

Sun Jun 4 01:12:11 UTC 2023 up 289 days, 22:40, 0 users, load averages: 1.91, 1.57, 1.25

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.

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