mersenneforum.org Help factor some b such that b^4096+1 are mega(PR)primes
 Register FAQ Search Today's Posts Mark Forums Read

2021-11-09, 17:42   #12
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

968710 Posts

Quote:
 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.

 2021-11-09, 21:38 #13 Viliam Furik     "Viliam Furík" Jul 2018 Martin, Slovakia 74510 Posts 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. Attached Thumbnails   Last fiddled with by Viliam Furik on 2021-11-09 at 21:40
2021-11-09, 22:00   #14
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101111110102 Posts

Quote:
 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.

Last fiddled with by R. Gerbicz on 2021-11-09 at 22:06

2021-11-09, 22:24   #15
JeppeSN

"Jeppe"
Jan 2016
Denmark

24×11 Posts

Quote:
 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.

2021-11-09, 22:40   #16
JeppeSN

"Jeppe"
Jan 2016
Denmark

24×11 Posts

Quote:
 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

2021-11-10, 06:54   #17
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

5×149 Posts

Quote:
 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.

2021-11-10, 16:39   #18
chris2be8

Sep 2009

2,221 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 44 2021-10-16 14:10 Gordon PrimeNet 6 2015-07-04 17:30 pepi37 Riesel Prime Search 5 2014-02-05 21:39 jasong jasong 1 2008-12-26 10:19 Tasuke Hardware 17 2002-08-23 22:06

All times are UTC. The time now is 08:38.

Wed Jan 19 08:38:11 UTC 2022 up 180 days, 3:07, 0 users, load averages: 1.03, 0.91, 0.99