mersenneforum.org Help? I have been holding on to a Prime
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-11-26, 01:01 #1 artacer   Nov 2020 116 Posts Help? I have been holding on to a Prime 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! -Gary
2020-11-26, 01:27   #2
Batalov

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

33·73 Posts

Quote:
 Originally Posted by artacer 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! -Gary
You have been trying to factor the Prime since discovery? That's intriguing!

Tell us more!

2020-11-26, 02:16   #3
Dr Sardonicus

Feb 2017
Nowhere

101138 Posts

Quote:
 Originally Posted by artacer The suspected Prime is over 26 million digits. I have been trying to factor it since discovery.
I don't understand. Are you trying to prove that a 26-million decimal digit number is prime by trial division?
Quote:
 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.
I'm not sure what you mean is probable, but if you mean one can say it is "probable" that a 26-million digit number is prime based on its first and last digit, that is fascinating.

There is a way to tell a number greater than ten is composite by its last decimal digit alone - if that digit is 2, 4, 5, 6, 8, or 0, the number is composite.

Last fiddled with by Dr Sardonicus on 2020-11-26 at 02:17 Reason: gixnif stopy

2020-11-26, 04:01   #4
Gelly

May 2020

328 Posts

Quote:
 Originally Posted by artacer If there is anyone who can help me please contact me. Thanks! -Gary
There is a program called PFGW which will take just about anything you throw at it and run a probable prime test that is better than just looking at some digits of it. Just put the number into a text file (or, better, if you have a more efficient formula for it, you can use the flag -q"INSERT FORMULA HERE") and use PFGW to crunch it.

There are no promises on it being particularly quick - if you dedicate a desktop computer to it, I'm fairly certain it'll finish in a year? Couple months? I really don't know the timescale for PRP tests on big numbers like that

At the very least, if it's a probable prime, it will let you know there's a very good chance it's prime - and, if the form of the number is conducive to it, may even let you absolutely prove it's primality. Would check if it's "probably" prime first, though.

2020-11-26, 06:10   #5
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

113558 Posts

Quote:
 Originally Posted by artacer 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! -Gary
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? https://en.wikipedia.org/wiki/RSA_(c...nd_RSA_problem
(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

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 ICWiener Software 38 2018-06-09 13:59 rcv FactorDB 1 2017-10-02 06:18 emily PrimeNet 3 2013-03-01 05:49 hhh Prime Cullen Prime 4 2007-09-21 16:34

All times are UTC. The time now is 12:10.

Thu Jan 21 12:10:39 UTC 2021 up 49 days, 8:21, 0 users, load averages: 2.82, 3.01, 3.01