mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-09-10, 13:20   #1
Viliam Furik
 
Jul 2018
Martin, Slovakia

23·31 Posts
Default Python script for search for factors of M1277 using random k-intervals

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)
Hello, I have made the above Python script, that is called with random starting k value, and then tests about 1263000 sived-out k's above that value. It uses a grid of zeroes to sieve k's and combines the facts that factors must be 2*k*p+1 and also 1 or 7 (mod 8) - so it only tests factors that are 2555, 3832, 7663, 8940 (mod 10216).

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.
Viliam Furik is offline   Reply With Quote
Old 2020-09-10, 13:56   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32·653 Posts
Default

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).
retina is offline   Reply With Quote
Old 2020-09-10, 14:58   #3
mathwiz
 
Mar 2019

2×32×7 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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.
You'd probably have a better chance of being struck by lightning 10 times and winning the lottery all on the same day.

The only hope for M1277, with presently known factoring techniques, is a mountain of ECM or (eventually) SNFS.
mathwiz is offline   Reply With Quote
Old 2020-09-10, 21:57   #4
Runtime Error
 
Sep 2017
USA

181 Posts
Default

Fun! I have a machine that is ram-bottle-necked 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 2020-09-10 at 21:58
Runtime Error is offline   Reply With Quote
Old 2020-09-10, 22:15   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·7·11·29 Posts
Default

How long will it take this program to search for all 70-digit factors? Or, most of them? How about 1% of the 70-digit range?

ECM on this number has ruled out factors smaller than about 67 digits, and a 70-digit 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 73-digit candidate factors?
VBCurtis is offline   Reply With Quote
Old 2020-09-10, 22:57   #6
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

46448 Posts
Default

we are looking at a 245 bit factor? hmmm
66-67 bits TF took 11 704 Ghz/D, and it double each bit.
so 245-67=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 2020-09-10 at 22:58
firejuggler is offline   Reply With Quote
Old 2020-09-11, 00:50   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·7·11·29 Posts
Default

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 non-useless work.
VBCurtis is offline   Reply With Quote
Old 2020-09-11, 01:10   #8
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

8,863 Posts
Default

Is there enough data yet to suggest that Mersenne non-primes have a higher likelihood to have 3 only factors vs 2 only?
Uncwilly is offline   Reply With Quote
Old 2020-09-11, 01:24   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×1,831 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
Is there enough data yet to suggest that Mersenne non-primes have a higher likelihood to have 3 only factors vs 2 only?
Many more Mersenne non-primes have a thousand factors. And even more have a million factors!
Infinity is a rather large thing.
Batalov is offline   Reply With Quote
Old 2020-09-11, 10:06   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

892910 Posts
Default

Quote:
Originally Posted by firejuggler View Post
Problem: The fastest current TF card,will give you 1.2e4Ghz/D by day.
Fixed it for you. Not that would change much, haha.

One-line 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.
LaurV is online now   Reply With Quote
Old 2020-09-11, 13:22   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1110110000112 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
Is there enough data yet to suggest that Mersenne non-primes have a higher likelihood to have 3 only factors vs 2 only?
Exactly three versus exactly two prime factors, not sure. Exactly two versus more than two, long-known data suggest "no contest."

I'll assume, for the sake of discussion, that you mean Mersenne numbers Mp 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 2n - 1 for odd n < 1200 I have on file, a quick scan finds that Mp 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 M1061 as a C320 so the number of factors was only known to be 2 or more at the time.

It seems that 21061 - 1 was subsequently found to be the product of two prime factors, so Mp 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 2p - 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 2020-09-11 at 13:30 Reason: Omit unnecessary words!
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


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

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

Tue Nov 24 10:03:12 UTC 2020 up 75 days, 7:14, 4 users, load averages: 2.19, 3.26, 3.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.