mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Help? I have been holding on to a Prime (https://www.mersenneforum.org/showthread.php?t=26231)

artacer 2020-11-26 01:01

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

Batalov 2020-11-26 01:27

[QUOTE=artacer;564418]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[/QUOTE]
You have been trying to factor the Prime since discovery? That's intriguing!

Tell us more! :beer2::popcorn:

Dr Sardonicus 2020-11-26 02:16

[QUOTE=artacer;564418]The suspected Prime is over 26 million digits. I have been trying to factor it since discovery.[/quote]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.[/quote]
I'm not sure [i]what[/i] 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 [i]is[/i] a way to tell a number greater than ten is [i]composite[/i] by its last decimal digit alone - if that digit is 2, 4, 5, 6, 8, or 0, the number is composite.

Gelly 2020-11-26 04:01

[QUOTE=artacer;564418]If there is anyone who can help me please contact me. Thanks!
-Gary[/QUOTE]

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.

kriesel 2020-11-26 06:10

[QUOTE=artacer;564418]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[/QUOTE]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? [URL]https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Integer_factorization_and_RSA_problem[/URL]
(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 [URL="https://primes.utm.edu/bios/page.php?id=175"]2.56 Megadigits[/URL]. The run time scaling for LL or PRP based primality testing with the best software for testing Mersennes is ~p[SUP]2.1[/SUP] 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.


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

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