import random
import time
from Cryptodome.Util import number

start_time = time.time()

count_of_iterations = int(input("Введите количество итераций:\n"))

prime_numbers = []
q = number.getPrime(16)

for _ in range(1):
    while True:
        b = q.bit_length()
        if b == 256:
            prime_numbers.append(q)
            q = number.getPrime(16)
            break
        N = number.getPrime(q.bit_length())
        p = 2 * q * N + 1
        if p.bit_length() == q.bit_length() * 2 and pow(2, 2 * N, p) != 1 and pow(2, 2 * N * q, p) == 1:
            q = p

print(prime_numbers)


def Ferm(n, k):
    if n == 1:
        print("Ни простое, ни составное\n")
        return

    for a in range(1, k + 1):
        if a % n != 0:
            mod_a = pow(a, n - 1, n)
            if mod_a != 1:
                print("Тест Ферма: составное с вероятностью 100.0 %")
                break
    print("Тест Ферма: простое с вероятностью ", (1 - 2 ** (-k)) * 100, "%")


def Miller_Rabin(n, k):
    flag = False

    if n == 2 or n == 3:
        print("Тест Миллера-Рабина: простое с вероятностью ", (1 - 4 ** (-k)) * 100, "%")
    if n <= 1 or n % 2 == 0:
        print("Тест Миллера-Рабина: составное с вероятностью 100.0 %")

    s = 0
    d = n - 1

    while d & 1 == 0:
        s += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n)
        x = pow(a, d, n)
        if x != 1 and x != n - 1:
            r = 1
            while r < s and x != n - 1:
                x = pow(x, 2, n)
                if x == 1:
                    break
                r += 1
            if x != n - 1:
                break
        flag = True

    if flag:
        print("Тест Миллера-Рабина: простое с вероятностью ", (1 - 4 ** (-k)) * 100, "%")
    else:
        print("Тест Миллера-Рабина: составное с вероятностью 100.0 %")


def calculate_Lejandr(base, degree, mod):
    x = 1
    a = base
    p = mod
    while degree > 0:
        if degree % 2 == 1:
            x = (x * a) % p

        a = (a * a) % p
        degree = degree // 2

    return x % p


def calculateJacobian(a, n):
    if a == 0:
        return 0

    ans = 1
    if a < 0:

        a = -a
        if n % 4 == 3:
            ans = -ans

    if a == 1:
        return ans

    while a:
        if a < 0:

            a = -a
            if n % 4 == 3:
                ans = -ans

        while a % 2 == 0:
            a = a // 2
            if n % 8 == 3 or n % 8 == 5:
                ans = -ans

        a, n = n, a

        if a % 4 == 3 and n % 4 == 3:
            ans = -ans
        a = a % n

        if a > n // 2:
            a = a - n

    if n == 1:
        return ans
    return 0


def Solovay_Strassen(n, k):
    if n < 2 or (n != 2 and n % 2 == 0):
        print("Тест Соловея-Штрассена: составное с вероятностью 100.0 %")

    for i in range(k):
        a = random.randrange(n - 1) + 1
        jacobi = (n + calculateJacobian(a, n)) % n
        lejandr = calculate_Lejandr(a, (n - 1) / 2, n)

        if jacobi == 0 or lejandr != jacobi:
            print("Тест Соловея-Штрассена: составное с вероятностью 100.0 %")

    print("Тест Соловея-Штрассена: простое с вероятностью", (1 - 2 ** (-k)) * 100, "%")


for x in prime_numbers:
    print("Число ", x, ":")
    Ferm(x, count_of_iterations)
    Solovay_Strassen(x, count_of_iterations)
    Miller_Rabin(x, count_of_iterations)
    print("\n")

print("--- %s seconds ---" % (time.time() - start_time))