kmzi6_8semv2

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:
            continue
        # 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]]

        print("Elliptic curve: y^2 = x^3 + {}x + {}".format(curve[0], curve[1]))
        print("Point: Q = ({}, {})".format(point[0], point[1]))

        i = 0
        Q = list([point[0], point[1]])
        while i < base:
            #Check whether i is prime
            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]:
                    Lmbd = inverse((2 * Q[1]), n)
                    if 1 < GCD(Lmbd, n) < n:
                        return GCD(Lmbd, n), counter
                    x3 = (Lmbd ** 2 - 2 * Q[0]) % n
                    y3 = (Lmbd * (Q[0] - x3) - Q[1]) % n
                    Q[1] = y3
                    Q[0] = x3
                else:
                    Lmbd = inverse((point[0] - Q[0]), n)
                    if 1 < GCD(Lmbd, n) < n:
                        return GCD(Lmbd, n), counter
                    x3 = (Lmbd ** 2 - Q[0] - point[0]) % n
                    y3 = (Lmbd * (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()