View Single Post
Old 2020-11-26, 06:10   #5
kriesel's Avatar
Mar 2017
US midwest

7·19·37 Posts

Originally Posted by artacer View Post
Yes, I have been holding on to a Prime I generated in 2011 by reverse engineering an RSA algorithm. The suspected Prime is over 26 million digits. I have been trying to factor it since discovery. Unsuccessful attempts have been made and i did have my Mathematics professor take a look at it and by using some type of modular mathematics found it probable by looking at the first and last digit. If there is anyone who can help me please contact me. Thanks!
How does one get a suspected 26-megadigit prime from RSA, which commonly uses keys in the 1024-bit to 4096-bit range? Especially in 2011, when 512-bit were apparently successfully attacked by factoring?
(It would in any event be smaller than the smallest (LL or PRP)-untested Mersenne number, at ~86.4Mbits vs. ~98.6Mbits at the moment.)
A similar sized Mersenne number can be primality tested in about a day on a Radeon VII gpu. A number of that size, not of a special form, may be entirely untestable in a human lifespan. If I understand correctly, the current record for pfgw is 2.56 Megadigits. The run time scaling for LL or PRP based primality testing with the best software for testing Mersennes is ~p2.1 where p is the exponent of the Mersenne number (due mainly to run time of the irrational base discrete weighted transform squaring operations and ~p iterations required), so 26. megadigits would be more than 100 times more effort than the current pfgw record, and would be remarkable / incredible for 2011 or now.

What specific factoring has been applied to the suspected prime? Why is it suspected to be prime?
First and last digit only makes little or no indication of primality. A few examples:
11 prime
121 composite
131 prime
1331 composite
1151 prime
11511 composite

Disclose the form of the number here if you know it, and people may be able to advise how best to attack it.

Last fiddled with by kriesel on 2020-11-26 at 07:03
kriesel is online now   Reply With Quote