mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-11-26, 01:01   #1
artacer
 
Nov 2020

1 Posts
minus 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
artacer is offline   Reply With Quote
Old 2020-11-26, 01:27   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,333 Posts
Default

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

Tell us more!
Batalov is offline   Reply With Quote
Old 2020-11-26, 02:16   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·5·7·31 Posts
Default

Quote:
Originally Posted by artacer View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-26, 04:01   #4
Gelly
 
Gelly's Avatar
 
May 2020

2×3×5 Posts
Default

Quote:
Originally Posted by artacer View Post
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.
Gelly is offline   Reply With Quote
Old 2020-11-26, 06:10   #5
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·3·5·41 Posts
Default

Quote:
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!
-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
kriesel is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
How does one prove that a mersenne prime found with CUDALucas is really prime? ICWiener Software 38 2018-06-09 13:59
Thank you for a database capable of holding a billion+ numbers rcv FactorDB 1 2017-10-02 06:18
disk died, prime work lost forever? where to put prime? on SSD or HDD? emily PrimeNet 3 2013-03-01 05:49
Prime Cullen Prime, Rest in Peace hhh Prime Cullen Prime 4 2007-09-21 16:34

All times are UTC. The time now is 19:32.

Thu Mar 4 19:32:00 UTC 2021 up 91 days, 15:43, 0 users, load averages: 1.81, 1.37, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.