1615.sagews

# Problem 4(a)

p = 2^31 - 1
g = Mod(7, p)
g_n = Mod(833287206, p)
m = 9392
g_mn = Mod(g_n, p)^m
print "The secret key we agree on is %s"%g_mn

# Problem 4(b)
n = discrete_log(g_n, g)
print "The you chose is n = %s"%n

The secret key we agree on is 560618491 The you chose is n = 2011

# Problem 5

p = Mod(2008, 1000)^2010
last_3 = Mod(2011, 1000)^p
print "The last 3 digits of 2011^(2008^2010) is %s"%last_3

The last 3 digits of 2011^(2008^2010) is 841

# Problem 6

p = 2^1279 - 1
a = Mod(2, p)^997 - 1
if legendre_symbol(a, p) == 1:
    print "2^997 - 1 is a perfect square modulo p = 2^1279 - 1"
else:
    print "2^997 - 1 is NOT a perfect square modulo p = 2^1279 - 1"

2^997 - 1 is a perfect square modulo p = 2^1279 - 1