Complexity analysis of 3 tests

[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

[TimSorbet]

Mersenne numbers. There's a reason the largest known prime has been a Mersenne for decades, now.

[R.D. Silverman]

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.

[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"

[R.D. Silverman]

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.

[R.D. Silverman]

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.

[henryzz]

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.

[R.D. Silverman]

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?

[axn]

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?

[henryzz]

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.

[axn]

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.