Help factor some b such that b^4096+1 are mega(PR)primes

[Batalov]

Originally Posted by chris2be8

For b^2048+1 I suggest choose b_min, search for primes p_min above it and check if p_min^2048+1 is PRP.

These primes will have to be even.

[Viliam Furik]

Probably unnecessary, but why not... (after making the screenshot I stopped it)

The number is one of the two composite cofactors you need to factor.

[R. Gerbicz]

Originally Posted by chris2be8

An easier way would be to make b_min a power of a known number (eg 10^244 or 10^245 since 999999/4096 is 244.140) and search for PRPs near to it on either side. That way the bases could be factored by SNFS which is relatively easy for a c244.

Much better: sieve and search only
b=k*2^762 for k>10^15 (you can limit to say k<2^64).
This will be good since now b is easily fully factored (you need to factor only k, but that is trivial).
and N=b^4096+1>10^1000000.

ps. maybe the sieve would be somewhat slower, not checked this, but the gain is much larger with a fully factored b.
N is also a Proth number, so you don't need to factor k, and you can use the classical test.

[JeppeSN]

Originally Posted by chris2be8

An easier way would be to make b_min a power of a known number (eg 10^244 or 10^245 since 999999/4096 is 244.140) and search for PRPs near to it on either side. That way the bases could be factored by SNFS which is relatively easy for a c244.

Or can the b_min you quote be expressed as a simple formula?

For b^2048+1 I suggest choose b_min, search for primes p_min above it and check if p_min^2048+1 is PRP. That way you don't need to factor the base. Or look for number just above b_min that are easy to factor and check them.

The b such that b^2048+1 is prime, are 1, 150, 2558, 4650, 4772, 11272, 13236, ....

The game here is to skip forward in this sequence to the first values b such that b^2048 > 10^999999 where 10^999999 is the first integer with one million (decimal) digits. You solve b^2048 > 10^999999 for b by extracting the 2048th root on both sides of the inequality symbol, so the criterion becomes:

b > 10^(999999/2048)

So we will start from the first (even) integer after 10^(999999/2048).

Note that some b that make b^2048+1 a megaprime are already known, and they are easy to factor. For example, 24518^262144+1 is a known megaprime, and we can write:

24518^262144 + 1 = (24518^128)^2048 + 1

So all known generalized Fermat numbers can be rewritten as b^N+1 with a smaller N and a higher b, in this way. So I do not think we are interested in your procedure for finding "easy" b values.

[JeppeSN]

Originally Posted by Viliam Furik

Probably unnecessary, but why not... (after making the screenshot I stopped it)

The number is one of the two composite cofactors you need to factor.

Thanks. Note that a lot of ECM (elliptic-curve factorization) had already been attempted on these two numbers even before their values were disclosed. For that reason I expect it to be quite difficult to find new factors. /JeppeSN

[Viliam Furik]

Originally Posted by JeppeSN

Thanks. Note that a lot of ECM (elliptic-curve factorization) had already been attempted on these two numbers even before their values were disclosed. For that reason I expect it to be quite difficult to find new factors. /JeppeSN

That's why I said it was probably unnecessary.

[chris2be8]

Originally Posted by Batalov

These primes will have to be even.

Doh!

I should have said look for potential bases that are easy to factor, then check if base^2048+1 is PRP. Since a hard number around 490 digits would be impossible to factor without a lot of luck.


For 4096 it would be enough to find the first sixth power above b_min, int(b_min^(1/6))+1 which I'll call b_root, then search each side of b_root^6. Any bases that yield a PRP would be fairly easy to factor with SNFS. Or a fifth or seventh power would be possible options.