Strassen’s factoring algorithm

gistfile1.txt

$ time python3 strassen_factor.py 12814570762777948741
12814570762777948741 = 3318288047 * 3861801803

real    1m17.824s
user    1m17.800s
sys     0m0.012s

$ time python3 strassen_factor.py 18366865165381711817
18366865165381711817 is prime

real    20m44.679s
user    20m44.435s
sys     0m0.024s

strassen_factor.py

# strassen_factor.py

import sys
import gmpy2
from math import gcd

def f(k, M, n):
    x = 1
    for i in range(k*M + 1, k*M + M + 1):
        x = (x*i) % n
    return x

# https://37zigen.com/deterministic-factoring/
# https://programmingpraxis.com/2018/01/27/strassens-factoring-algorithm/
def strassen_factor(n):
    M, is_exact = gmpy2.iroot(n, 4)
    for i in reversed(range(M + 2)):
        a = gcd(f(i, M, n), n)
        if a > 1:
            return a

if __name__ == '__main__':
    n = int(sys.argv[1])
    p = strassen_factor(n)
    if p:
        print('{} = {} * {}'.format(n, p, n//p)) 
    else:
        print('{} is prime'.format(n))