20200910, 13:20  #1 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2^{2}×3×5×13 Posts 
Python script for search for factors of M1277 using random kintervals
Code:
import numpy as np from random import randint f = open("m1277.txt", "a") def tf1277(k, r): expos = np.zeros((4, r), int) p = 1277 y = 0 z = 0 e1 = 2555 e2 = 3832 e3 = 7663 e4 = 8940 pbinary = [] q = p while q > 0: if q % 2 == 0: pbinary.append(0) q //= 2 if q % 2 == 1: pbinary.append(1) q //= 2 pbinary.reverse() for x in range(4): for prime in [3, 5, 7, 11, 13, 17, 19, 23, 29]: for a in range(prime + 5): if x == 0: e = e1 elif x == 1: e = e2 elif x == 2: e = e3 else: e = e4 if ((a + k) * 10216 + e) % prime == 0: c = a while c < r: expos[x][c] = 1 c += prime break for a in range(len(expos[0])): if expos[0][a] == 0: c = 1 kp = (k + a) * 10216 + 2555 for d in pbinary: c **= 2 if d == 1: c *= 2 c %= kp if c == 1: print("") print("factor = ", kp) print("k = ", (kp  1) // 2 // 1277) f.write("\n") f.write("factor = " + str(kp)) f.write("\n") f.write("k = " + str((kp  1) // 2 // 1277)) f.write("\n") quit() if y == 1000: y = 0 z += 1 print(z * 1000) y += 1 for a in range(len(expos[1])): if expos[1][a] == 0: c = 1 kp = (k + a) * 10216 + 3832 for d in pbinary: c **= 2 if d == 1: c *= 2 c %= kp if c == 1: print("") print("factor = ", kp) print("k = ", (kp  1) // 2 // 1277) f.write("\n") f.write("factor = " + str(kp)) f.write("\n") f.write("k = " + str((kp  1) // 2 // 1277)) f.write("\n") quit() if y == 1000: y = 0 z += 1 print(z * 1000) y += 1 for a in range(len(expos[2])): if expos[2][a] == 0: c = 1 kp = (k + a) * 10216 + 7663 for d in pbinary: c **= 2 if d == 1: c *= 2 c %= kp if c == 1: print("") print("factor = ", kp) print("k = ", (kp  1) // 2 // 1277) f.write("\n") f.write("factor = " + str(kp)) f.write("\n") f.write("k = " + str((kp  1) // 2 // 1277)) f.write("\n") quit() if y == 1000: y = 0 z += 1 print(z * 1000) y += 1 for a in range(len(expos[3])): if expos[3][a] == 0: c = 1 kp = (k + a) * 10216 + 8940 for d in pbinary: c **= 2 if d == 1: c *= 2 c %= kp if c == 1: print("") print("factor = ", kp) print("k = ", (kp  1) // 2 // 1277) f.write("\n") f.write("factor = " + str(kp)) f.write("\n") f.write("k = " + str((kp  1) // 2 // 1277)) f.write("\n") quit() if y == 1000: y = 0 z += 1 print(z * 1000) y += 1 while True: tf1277(randint(58000000000000000, 2 ** (1277 / 2) / 1277 / 2), 1000000) If there is a mistake (either logical or mathematical) in my script, I'll be grateful for pointing out. I would also be grateful if somebody could help me with making the code runnable on a Nvidia GPU with CUDA (or in OpenCL, if it's easier), without necessarily using FFT or Barrett multiplication. (But if somebody is willing to explain, I'll be happy to listen, or read...). And for the last, if you want, you can try to find the factor yourself with that code. It takes my CPU about 12 seconds on average to go through random range of size 10216000000 (that is difference between largest and smallest k tested). So if I was to randomly check the equivalent number of ranges (untested range from 2^67 to 2^639 divided by range size 10216000000), it would take me... about 2*10^172 years . But if more people engage in search, probability increases (unfortunately it's only slight change). So if you want to help, you can run the script any time you like. If you want to help more, you can help with improving the speed of the script. 
20200910, 13:56  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5·1,321 Posts 
Running this code is a fantastic way to waste power/time/money/energy.
Random TF for this number is pointless. And trying to "optimise" a scripting language is equally pointless. You need another method (not TF), and you need another language (not a scripting language). 
20200910, 14:58  #3  
Mar 2019
3·101 Posts 
Quote:
The only hope for M1277, with presently known factoring techniques, is a mountain of ECM or (eventually) SNFS. 

20200910, 21:57  #4 
Sep 2017
USA
AE_{16} Posts 
Fun! I have a machine that is rambottlenecked for Prime95. So far, running this too doesn't seem to affect the iterations per second. I'll leave it on for a week or so and perhaps lightning with strike! (Or strike 10 times, per the comment above. But I will probably not buy the requisite lotto ticket.)
Last fiddled with by Runtime Error on 20200910 at 21:58 
20200910, 22:15  #5 
"Curtis"
Feb 2005
Riverside, CA
3·1,831 Posts 
How long will it take this program to search for all 70digit factors? Or, most of them? How about 1% of the 70digit range?
ECM on this number has ruled out factors smaller than about 67 digits, and a 70digit or smaller factor is unlikely. So, I'm not even sure you should set it to look at 70 digits maybe 73 is smarter. How many k's are there that make 73digit candidate factors? 
20200910, 22:57  #6 
"Vincent"
Apr 2010
Over the rainbow
2859_{10} Posts 
we are looking at a 245 bit factor? hmmm
6667 bits TF took 11 704 Ghz/D, and it double each bit. so 24567=178. Sooo 2^178*11 704= 4.484e57 Ghz/D for the last bit. Not counting all that is before it, Which double it. Lets handwave this a bit and it come to 9e57Ghz/D. Problem: The fastest current TF card,will give you 6e3Ghz/D by day. so, AFAIK, it would take 1.5e54 Day, About 3e41 time the duration since the beginning of the universe. Thats, by TF only. PM1 is almost excluded because of its requirement. Last fiddled with by firejuggler on 20200910 at 22:58 
20200911, 00:50  #7 
"Curtis"
Feb 2005
Riverside, CA
3×1,831 Posts 
So, one fast GPU can spend 1e54 days to have roughly a 1 in 250 chance to find a factor.
Or, you could run regular ECM with large bounds (B1=3e9 or bigger) and actually contribute nonuseless work. 
20200911, 01:10  #8 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2^{2}×2,687 Posts 
Is there enough data yet to suggest that Mersenne nonprimes have a higher likelihood to have 3 only factors vs 2 only?

20200911, 01:24  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3×1,657 Posts 

20200911, 10:06  #10  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·5·1,013 Posts 
Quote:
Oneline pari "search by q" (as posted a lot of times in the forum) with a parfor and a random start would be faster that the posted script. 

20200911, 13:22  #11  
Feb 2017
Nowhere
7×857 Posts 
Quote:
I'll assume, for the sake of discussion, that you mean Mersenne numbers M_{p} with prime exponent p. For composite exponents n, the algebraic factorization alone is very likely to provide more than two proper factors, which, in turn, are very likely to provide more than two prime factors. From an old factorization table of 2^{n}  1 for odd n < 1200 I have on file, a quick scan finds that M_{p} was known to be prime for 13 odd prime p, known to have exactly two prime factors for 38 prime p, and known to have 3 or more prime factors for 143 odd prime p. The table lists M_{1061} as a C320 so the number of factors was only known to be 2 or more at the time. It seems that 2^{1061}  1 was subsequently found to be the product of two prime factors, so M_{p} is known to be prime for 13 odd prime p < 1200, known to have exactly two prime factors for 39 odd primes p < 1200, and known to have 3 or more prime factors for 143 odd prime p < 1200. That accounts for all 195 odd primes p < 1200. So I would say that the data suggest that more than two factors is much more likely than exactly two. There are only about 400 primes p for which the exact number of factors of 2^{p}  1 is known or "probably" known. I'm too lazy to check for how many p the number of factors is known to be at least 3. Last fiddled with by Dr Sardonicus on 20200911 at 13:30 Reason: Omit unnecessary words! 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
inconsistent timestamp intervals in prime.log  ixfd64  Software  1  20201101 20:27 
Could I run this py python script on a supercomputer?  Ghost  Information & Answers  4  20181130 04:07 
M1277  no factors below 2^65?  DanielBamberger  Data  17  20180128 04:21 
search for MMM127 small factors?  Orgasmic Troll  Miscellaneous Math  7  20060611 15:38 
Random numbers and proper factors  mfgoode  Math  20  20060205 02:09 