import random
p = next_prime(451643)
x = random.randint(1, p)
g = random_prime(p)
b = power_mod(g,x,p)
M = 11111
r = random.randint(1, p-1)
while gcd(r,p-1) != 1:
r = r +1
if r >= p-1:
r = random.randint(1, p-1)
y = power_mod(g, r, p)
signature = mod((M-x*y)/r, p-1)
v2 = power_mod(g, M, p)
v2
v1 = mod((power(y, signature) * power(b, y)), p)
v1
if v1 == v2:
print('verification success')
else:
print('verification failed')