138.sagews

# (i)
q=7541
p=2*q + 1
a=604
b=3791

print power_mod(a,2,p) 
print power_mod(a,q,p)

2824 1

print power_mod(b,2,p) 
print power_mod(b,q,p)

12665 1

# (ii)
x1=7431
x2=5564
h1=power_mod(a,x1,p)*power_mod(b,x2,p)
y1=1459
y2=954
h2=power_mod(a,y1,p)*power_mod(b,y2,p)
mod(h1-h2,p)

0

# (iii)
# having a collision means
# a^{x1} b^{x2} == a^{y1} b^{y2} # with (x1,x2)!==(y1,y2)
# taking discrete logarithms dlog_a on both sides give
z = var('z')
x1 + x2 * z == y1 + y2 * z # where z is the requested dlog_a b

5564*z + 7431 == 954*z + 1459

solve_mod(x1 + x2 * z == y1 + y2 * z, q)
# Beware about the modulus! p-1 would give two solutions for this equation, i.e. additionally 9555).

# double-check
b == power_mod(a,2014,p)

True