import random

def gcd(a: int, b: int):
    while (b):
        a, b = b, a % b
    return a


def is_prime(n):
    return 1 == gcd(n, 1)


def get_p():
    p = random.randint(500000, 3000000)
    while not is_prime(p):
        p = random.randint(500000, 3000000)
    return p


def get_q(p):
    x = 2
    q = 0
    while x < p - 1:
        if (p - 1) % x == 0:
            if is_prime(x):
                q = x
        x += 1
    return q


def get_a(p, q):
    a = 2
    while a < p - 1:
        if pow(a, q, p) == 1:
            break
        a += 1
    return a


p = get_p()
q = get_q(p)
a = get_a(p, q)
print(p, q, a)

def get_H(message):
    H = 0
    for i in range(len(message)):
        H = H + bin(ord(message[i])).count('1')
    return H


def check(p, q, a):
    k = random.randint(2, q - 1)
    x = random.randint(2, q - 1)

    y = pow(a, x, p)
    print("Введите сообщение")
    message = input()

    H = get_H(message)
    if H % p == 0:
        H = 1

    while True:
        k = random.randint(2, q - 1)
        r1 = pow(a, k, p) % q
        if r1 == 0:
            continue
        s = (x * r1 + k * H) % q
        if s != 0:
            break

    print(f'Сгенерированные r1 = {r1}, s = {a}')

    v = pow(H, q - 2, q)
    z1 = (s * v) % q
    z2 = ((q - r1) * v) % q
    u = ((pow(a, z1) * pow(y, z2)) % p) % q

    print(f'Вычисленное u = {u}')

    if u == r1:
        print('OK')
        return
    print('Подпись недействительна')


check(p, q, a)