kmzi6_8sem

from math import log
from datetime import datetime
from Cryptodome.Random.random import randint
from Cryptodome.Util.number import isPrime, GCD, inverse


# Params generations
def generate_params(num):
    while 1:
        a, x, y = randint(0, num - 1), randint(0, num - 1), randint(0, num - 1)
        b = (y ** 2 - x ** 3 - a * x) % num
        g = GCD(num, 4 * a ** 3 + 27 * b ** 2)
        result = list()
        if g == num:
            continue
        if g > 1:
            result.append(g)
            return result
        result.append(a)
        result.append(b)
        result.append(x)
        result.append(y)
        return result


# Lenstra algorithm for factorizing numbers
def lenstra_algorithm(n, base):
    point = list()
    curve = list()
    counter = 0
    while True:
        temp = generate_params(n)
        if len(temp) == 1:
            return temp[0]
        # A and B
        curve.append(temp[0])
        curve.append(temp[1])
        # X and Y
        point.append(temp[2])
        point.append(temp[3])
        i = 0
        # Q = (X, Y)
        Q = [point[0], point[1]]
        while i < base:
            if not isPrime(i):
                i += 1
                continue
            r = int((log(n, 2) / log(i, 2)) * (1 / 2))
            if r == 0:
                r = 1
            p = i ** r
            for j in range(1, p):
                counter += 1
                if Q[0] == point[0] and Q[1] == point[1]:
                    chisl = (3 * Q[0] ** 2 + curve[0]) % n
                    znam = inverse((2 * Q[1]), n)
                    L = chisl * znam % n
                    if GCD(L, n) > 1 and GCD(L, n) < n:
                        return GCD(L, n), counter
                    x3 = (L ** 2 - 2 * Q[0]) % n
                    y3 = (L * (Q[0] - x3) - Q[1]) % n
                    Q[1] = y3
                    Q[0] = x3
                else:
                    chisl = (point[1] - Q[1]) % n
                    znam = inverse((point[0] - Q[0]), n)
                    L = chisl * znam % n
                    if GCD(L, n) > 1 and GCD(L, n) < n:
                        return GCD(L, n), counter
                    x3 = (L ** 2 - Q[0] - point[0]) % n
                    y3 = (L * (Q[0] - x3) - Q[1]) % n
                    Q[1] = y3
                    Q[0] = x3
                if counter % 10000000 == 0:
                    print(counter)


# main func
def main():
    user_number = int(input("Enter not prime number for factorizing: "))
    user_base = int(input("Enter base of factorization: "))
    if isPrime(user_number):
        print("Your number is prime, try more\n")
        return
    start_time = datetime.now()
    p, iter_num = lenstra_algorithm(user_number, user_base)
    end_time = datetime.now() - start_time
    q = user_number // p
    print("{} * {} = {}" . format(p, q, user_number))
    print("Number of iterations: {}" . format(iter_num))
    print("Time: {}" . format(end_time))

main()