evaluation for https://www.reddit.com/r/crypto/comments/bmm8h3/rsa_factorization_algorithm/

new_factor.py

# from https://stackoverflow.com/questions/15390807/integer-square-root-in-python
def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

# everything from here on is a slightly modified version of https://github.com/goldcove/RSA-defacto

def getnewnr(x, y, carry, num):
    """Calcualtes the next numbers"""
    y-=2 #Only odd numbers can be prime, subtract 2.
    x+=(x*2+carry)//y #(2 rows + carry) over y
    carry=num-(x*y)
    return x, y, carry


def initnumber(num):
    """Get initial value of x, y and carry"""
    x = isqrt(num)
    #We can also check for last digit 1, 3, 7 or 9 as prime number must end with one of these.
    if x % 2 == 0: #not odd number
        x+=1
    y=num//x
    if y % 2 == 0: #not odd number
        y-=1
    carry=num-x*y
    return x,y,carry


def new_factor(num):
    iterations=1
    x,y,carry = initnumber(num)
    while carry != 0:
        iterations+=1
        x, y, carry = getnewnr(x,y,carry,num)
    return x, y, iterations


print(new_factor(3119712991*2274712361))
# output = (3119712991, 2274712361, 194601937)
# => 194601937 iterations

trial_division.py

from functools import reduce

# from https://stackoverflow.com/questions/15390807/integer-square-root-in-python
def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x


def comp_wheel(primes):
    product = reduce(lambda x,y: x*y, primes)
    wheel = [1] * product
    for p in primes:
        for i in range(0, product // p):
            wheel[p*i] = 0
    offsets = []
    for i in range(product):
        if wheel[i] == 1:
            offsets += [i]
    return product, list(reversed(offsets))



def naive_factor(n, primes = [2,3,5,7]):
    wheel_size, wheel = comp_wheel(primes)
    for p in primes:
        if n % p == 0:
            return p, 0
    x = isqrt(n)
    y = x // wheel_size
    iterations = 0
    for base in range(y * wheel_size, -wheel_size, -wheel_size):
        for offset in wheel:
            iterations += 1
            tmp = base + offset
            #print(f"{base} + {offset} = {tmp} => {tmp % n}")
            if n % (base + offset) == 0 and tmp < n:
                return base + offset, iterations


print(naive_factor(3119712991*2274712361, [2,3,5,7,11,13]))
# output = (2274712361, 74655377)
# => 74655377 iterations