import math
import random
import secrets
from functools import reduce



"""def fast_pow_mod(n, a, d):
    if d == 0:
        return 1
    if d % 2 != 0:
        return fast_pow_mod(n, a, d - 1) * a % n
    else:
        a = fast_pow_mod(n, a, int(math.floor(d/2)))
        return a * a % n
    pass"""""




def gen_primes():
    max_number = pow(2, 218)
    min_number = pow(2, 213)
    min_amount_of_primes = 5
    primes_range = 128
    must_p = 2


    def creating_primes_list():
        numbers = []
        primes = []
        for i in range(2, primes_range + 1):
            numbers.append(i)
        for p in range(2, primes_range + 1):
            if (numbers[p - 2] == p):
                primes.append(p)
                for i in range(p, primes_range + 1, p):
                    numbers[i - 2] = 0
        return primes


    def get_random_number(max_number, primes, must_p):
        powers = [0] * len(primes)
        n = must_p
        powers[0] += 1
        for i in range(min_amount_of_primes - 1):
            j = secrets.randbelow(len(primes))-1
            n *= primes[j]
            powers[j] += 1
        while True:
            j = secrets.randbelow(len(primes))
            n = n * primes[j]
            if(n > max_number):
                n = n//primes[j]
                n += 1
                return (powers, n)
            else:
                powers[j] += 1

    def check_if_number_is_correct(n, max_number, min_number):
        if (n < max_number and n > min_number):
            return True
        return False

    def find_A(n, primes, powers):
        for a in range(42, math.floor(math.log(n))+1):
            might_found = True
            if pow(a, n-1, n) != 1:
                continue
            for i in range(len(primes)):
                if powers[i] != 0 and pow(a, int((n - 1) / primes[i]), n) == 1:
                        might_found = False
                        break
            if might_found == False:
                continue
            return a


    primes = creating_primes_list()
    found = False
    while not found:
        powers, n = get_random_number(max_number, primes, must_p)
        correct = check_if_number_is_correct(n, max_number, min_number)
        if not correct:
            continue
        a = find_A(n, primes, powers)
        if (not a):
            continue
        print(a)
        j = 0
        for i in primes:
            if(powers[j] != 0):
                print(i)
            j +=1
        print(n)
        print(pow(a, n-1, n))
        return True

    pass








def gen_pseudoprime():
    """Генерация псевдопростых на основе теста Миллера—Рабина.

    Возвращает целое число n в диапазоне от 2^123 до 2^128,
    псевдопростое по основание не менее чем log(n) чисел."""
    pass


def rsa_gen_keys():
    """Генерация открытого и секретного ключей.

    Возвращает кортеж (n, p, q, e, d), где
    n = p*q;
    p, q — сильно псевдопростые по не менее чем log(q) основаниям;
    e — целое число, меньшее n и взаимно простое с phi(n), значением функции Эйлера от n,
    d — целое число, обратное к e по модулю phi(n)."""
    pass


def rsa_encrypt(n, e, t):
    """Шифрование по RSA.

    На входе открытый ключ n, e и сообщение t.
    Возвращает целое число, равное t^e mod n."""
    pass


def rsa_decrypt(n, d, s):
    """Дешифрование по RSA.

    На входе закрытый ключ n, d и зашифрованное сообщение s.
    Возвращает целое число, равное s^d mod n."""
    pass

def prime_factorization_pollard(n, cutoff):
    """Разложение на простые по алгоритму Полларда.

    На входе целое число n (имеющие вид p*q для некоторых простых p, q)
    и константа отсечения cutoff ~ log(n).
    Возвращает нетривиальный делитель p (или 1, если найти такой не удалось)."""
    pass




gen_primes()