# imports
import random
import math

def large_random(n):
    return random.randrange(2**(n-1)+1, 2**n)

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def large_prime(n):
    while True:
        lr = large_random(n)
        if is_prime(lr): return lr

p = large_prime(32)

# p = 283
q = 47
g = 60
x = 24
k = 15
y = pow(g, x, p)
print(f"y: {y}\n")

def hash(M):
    sum = 0
    for i in M:
        sum += ord(i)
    return sum%10000007

def sign(M):
    r = pow(g, k, p) % q
    s = ( (hash(M) + x*r) * pow(k, -1, q) ) % q
    print(f"r: {r}, s: {s}")
    return (r, s)

def verify(M, r1, s1):
    w = pow(s1, -1, q)
    u1 = (hash(M) * w) % q
    u2 = (r1 * w) % q
    v = ( ( g**u1 * y**u2 ) % p ) % q
    print(f"g: {g}, w: {w}, u1: {u1}, u2: {u2}, v: {v}")
    return v

print(">>> Test case 1")
r, s = sign("abcdf")
v = verify("abcdf", r, s)
if v==r: print("Verified\n")

print(">>> Test case 2")
r_new, s_new = sign("abcdefguyhgfdgfdgfdgfdhjgfdskgfdk")
v_new = verify("abcdf", r_new, s_new)
print("Verified") if v_new==r_new else print("Not verified")

print(f"Large number: {large_prime(32)}")