SharedRSA wkst 2018-02-07-093754.sagewsOpen in CoCalc
# Mina Kim

# question 1

# pt 1: choose two large primes
p = 11
q = 17
n = p*q
print "n = " + str(n)

# pt 2: all of invertible elements mod n
Z_n = [] # create a list Z_n of multiplicative inverses of n
for a in range (1, n):
if gcd(a, n) == 1: # a is relatively prime to n
Z_n.append(a) # add a to list L
else:
print str(a) + " = " + str(factor(a))
# factor(a) shows the factorization of each multiple of p and q
print Z_n

# pt 3: calculate phi_n and verify that phi_n is the number of elements in the group
phi_n = (p-1)*(q-1) # phi_n is the magnitude of the invertible elements of modulo n
len(Z_n) == phi_n # verify that phi_n is indeed equal to the number of elements in the group L

# question 2

# pt 1: calculate the order for each element in Z_n
# given element g in Z_n
n = 187 # don't know why i need to include the value of n again; for some reason the value of n doesnt carry forward from question 1
M = [] # create a list of all g
for g in range(1, n): # range of g is n bc we need to figure out which values are invertible like we did in question 1
if gcd(g, n) == 1: # this makes sure that g is relatively prime to n aka g includes all the invertible elements modulo n
for m in range(1, phi_n): # we know m would not surpass phi_n bc g^(phi_n) = 1 mod n
if int(power_mod(g, m, n)) == 1: # then we find the order of g
M.append(m)
print "The order of element " + str(g) + " is " + str(m) + "."

# pt 2: show Langrange's thm works, ie. m divides phi_n
if (phi_n % m == 0): # this asks to verify whether the order of g divides the order of Z_n
print str(m) + " divides " + str(phi_n)
break
print "Below is a list of the order of elements g in Z_n"
print M

# question 3

# pt 1: display cyclic subgroups generated by 3 elements in Z_n
G1 = []
G2 = []
G3 = []
g = [Z_n[1], Z_n[7], Z_n[8]]; # g1 is the second element of Z_n, g2 is the eighth element of Z_n, etc
print "g = " + str(g)
m = [M[1], M[7], M[8]]; # m1 is the order of gl, m2 is the order of g2, etc
print "m = " + str(m)
for a in range (0, 3): # note this means a = 0,1,2 (3 not included)
for b in range (1, m[a]+1): # so this means b = 1,2,...,m[a]
x = power_mod(g[a], b, n)
if a == 0:
G1.append(x)
if a == 1:
G2.append(x)
if a == 2:
G3.append(x)

print G1
print G2
print G3

# pt 2: factorization of both phi_n and the orders m1, m2, m3 and show that m divides phi_n
print "phi_n = " + str(phi_n) + " = " + str(factor(phi_n)) # this factors phi_n
for r in range (1, 4): # from 1 to 3
print "m" + str(r) + " = " + str(factor(M[r])) # this just factors the m values
if phi_n%(m[r]) == 0: # if m divides phi_n
print str(m[r]) + " divides " + str(phi_n)

# pt 3: this shows that g^m = 1 mod n and g^phi_n = 1 mod n
for h in range (0, 3): # for the 3 entries g1,g2,g3 and m1,m2,m3
power_mod(g[h], m[h], n) == power_mod(g[h], phi_n, n)

n = 187 11 = 11 17 = 17 22 = 2 * 11 33 = 3 * 11 34 = 2 * 17 44 = 2^2 * 11 51 = 3 * 17 55 = 5 * 11 66 = 2 * 3 * 11 68 = 2^2 * 17 77 = 7 * 11 85 = 5 * 17 88 = 2^3 * 11 99 = 3^2 * 11 102 = 2 * 3 * 17 110 = 2 * 5 * 11 119 = 7 * 17 121 = 11^2 132 = 2^2 * 3 * 11 136 = 2^3 * 17 143 = 11 * 13 153 = 3^2 * 17 154 = 2 * 7 * 11 165 = 3 * 5 * 11 170 = 2 * 5 * 17 176 = 2^4 * 11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 100, 101, 103, 104, 105, 106, 107, 108, 109, 111, 112, 113, 114, 115, 116, 117, 118, 120, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 133, 134, 135, 137, 138, 139, 140, 141, 142, 144, 145, 146, 147, 148, 149, 150, 151, 152, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 166, 167, 168, 169, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186] True The order of element 1 is 1. 1 divides 160 The order of element 2 is 40. 40 divides 160 The order of element 3 is 80. 80 divides 160 The order of element 4 is 20. 20 divides 160 The order of element 5 is 80. 80 divides 160 The order of element 6 is 80. 80 divides 160 The order of element 7 is 80. 80 divides 160 The order of element 8 is 40. 40 divides 160 The order of element 9 is 40. 40 divides 160 The order of element 10 is 16. 16 divides 160 The order of element 12 is 16. 16 divides 160 The order of element 13 is 20. 20 divides 160 The order of element 14 is 80. 80 divides 160 The order of element 15 is 40. 40 divides 160 The order of element 16 is 10. 10 divides 160 The order of element 18 is 10. 10 divides 160 The order of element 19 is 40. 40 divides 160 The order of element 20 is 80. 80 divides 160 The order of element 21 is 4. 4 divides 160 The order of element 23 is 16. 16 divides 160 The order of element 24 is 80. 80 divides 160 The order of element 25 is 40. 40 divides 160 The order of element 26 is 40. 40 divides 160 The order of element 27 is 80. 80 divides 160 The order of element 28 is 80. 80 divides 160 The order of element 29 is 80. 80 divides 160 The order of element 30 is 20. 20 divides 160 The order of element 31 is 80. 80 divides 160 The order of element 32 is 8. 8 divides 160 The order of element 35 is 10. 10 divides 160 The order of element 36 is 40. 40 divides 160 The order of element 37 is 80. 80 divides 160 The order of element 38 is 20. 20 divides 160 The order of element 39 is 80. 80 divides 160 The order of element 40 is 80. 80 divides 160 The order of element 41 is 80. 80 divides 160 The order of element 42 is 40. 40 divides 160 The order of element 43 is 8. 8 divides 160 The order of element 45 is 16. 16 divides 160 The order of element 46 is 80. 80 divides 160 The order of element 47 is 20. 20 divides 160 The order of element 48 is 80. 80 divides 160 The order of element 49 is 40. 40 divides 160 The order of element 50 is 10. 10 divides 160 The order of element 52 is 10. 10 divides 160 The order of element 53 is 40. 40 divides 160 The order of element 54 is 16. 16 divides 160 The order of element 56 is 16. 16 divides 160 The order of element 57 is 80. 80 divides 160 The order of element 58 is 80. 80 divides 160 The order of element 59 is 40. 40 divides 160 The order of element 60 is 40. 40 divides 160 The order of element 61 is 80. 80 divides 160 The order of element 62 is 80. 80 divides 160 The order of element 63 is 80. 80 divides 160 The order of element 64 is 20. 20 divides 160 The order of element 65 is 16. 16 divides 160 The order of element 67 is 2. 2 divides 160 The order of element 69 is 5. 5 divides 160 The order of element 70 is 40. 40 divides 160 The order of element 71 is 80. 80 divides 160 The order of element 72 is 20. 20 divides 160 The order of element 73 is 80. 80 divides 160 The order of element 74 is 80. 80 divides 160 The order of element 75 is 80. 80 divides 160 The order of element 76 is 8. 8 divides 160 The order of element 78 is 16. 16 divides 160 The order of element 79 is 80. 80 divides 160 The order of element 80 is 80. 80 divides 160 The order of element 81 is 20. 20 divides 160 The order of element 82 is 80. 80 divides 160 The order of element 83 is 40. 40 divides 160 The order of element 84 is 10. 10 divides 160 The order of element 86 is 5. 5 divides 160 The order of element 87 is 8. 8 divides 160 The order of element 89 is 4. 4 divides 160 The order of element 90 is 80. 80 divides 160 The order of element 91 is 80. 80 divides 160 The order of element 92 is 80. 80 divides 160 The order of element 93 is 40. 40 divides 160 The order of element 94 is 40. 40 divides 160 The order of element 95 is 80. 80 divides 160 The order of element 96 is 80. 80 divides 160 The order of element 97 is 80. 80 divides 160 The order of element 98 is 4. 4 divides 160 The order of element 100 is 8. 8 divides 160 The order of element 101 is 10. 10 divides 160 The order of element 103 is 5. 5 divides 160 The order of element 104 is 40. 40 divides 160 The order of element 105 is 80. 80 divides 160 The order of element 106 is 20. 20 divides 160 The order of element 107 is 80. 80 divides 160 The order of element 108 is 80. 80 divides 160 The order of element 109 is 16. 16 divides 160 The order of element 111 is 8. 8 divides 160 The order of element 112 is 80. 80 divides 160 The order of element 113 is 80. 80 divides 160 The order of element 114 is 80. 80 divides 160 The order of element 115 is 20. 20 divides 160 The order of element 116 is 80. 80 divides 160 The order of element 117 is 40. 40 divides 160 The order of element 118 is 10. 10 divides 160 The order of element 120 is 2. 2 divides 160 The order of element 122 is 16. 16 divides 160 The order of element 123 is 20. 20 divides 160 The order of element 124 is 80. 80 divides 160 The order of element 125 is 80. 80 divides 160 The order of element 126 is 80. 80 divides 160 The order of element 127 is 40. 40 divides 160 The order of element 128 is 40. 40 divides 160 The order of element 129 is 80. 80 divides 160 The order of element 130 is 80. 80 divides 160 The order of element 131 is 16. 16 divides 160 The order of element 133 is 16. 16 divides 160 The order of element 134 is 40. 40 divides 160 The order of element 135 is 10. 10 divides 160 The order of element 137 is 5. 5 divides 160 The order of element 138 is 40. 40 divides 160 The order of element 139 is 80. 80 divides 160 The order of element 140 is 20. 20 divides 160 The order of element 141 is 80. 80 divides 160 The order of element 142 is 16. 16 divides 160 The order of element 144 is 8. 8 divides 160 The order of element 145 is 40. 40 divides 160 The order of element 146 is 80. 80 divides 160 The order of element 147 is 80. 80 divides 160 The order of element 148 is 80. 80 divides 160 The order of element 149 is 20. 20 divides 160 The order of element 150 is 80. 80 divides 160 The order of element 151 is 40. 40 divides 160 The order of element 152 is 10. 10 divides 160 The order of element 155 is 8. 8 divides 160 The order of element 156 is 80. 80 divides 160 The order of element 157 is 20. 20 divides 160 The order of element 158 is 80. 80 divides 160 The order of element 159 is 80. 80 divides 160 The order of element 160 is 80. 80 divides 160 The order of element 161 is 40. 40 divides 160 The order of element 162 is 40. 40 divides 160 The order of element 163 is 80. 80 divides 160 The order of element 164 is 16. 16 divides 160 The order of element 166 is 4. 4 divides 160 The order of element 167 is 80. 80 divides 160 The order of element 168 is 40. 40 divides 160 The order of element 169 is 10. 10 divides 160 The order of element 171 is 10. 10 divides 160 The order of element 172 is 40. 40 divides 160 The order of element 173 is 80. 80 divides 160 The order of element 174 is 20. 20 divides 160 The order of element 175 is 16. 16 divides 160 The order of element 177 is 16. 16 divides 160 The order of element 178 is 40. 40 divides 160 The order of element 179 is 40. 40 divides 160 The order of element 180 is 80. 80 divides 160 The order of element 181 is 80. 80 divides 160 The order of element 182 is 80. 80 divides 160 The order of element 183 is 20. 20 divides 160 The order of element 184 is 80. 80 divides 160 The order of element 185 is 40. 40 divides 160 The order of element 186 is 2. 2 divides 160 Below is a list of the order of elements g in Z_n [1, 40, 80, 20, 80, 80, 80, 40, 40, 16, 16, 20, 80, 40, 10, 10, 40, 80, 4, 16, 80, 40, 40, 80, 80, 80, 20, 80, 8, 10, 40, 80, 20, 80, 80, 80, 40, 8, 16, 80, 20, 80, 40, 10, 10, 40, 16, 16, 80, 80, 40, 40, 80, 80, 80, 20, 16, 2, 5, 40, 80, 20, 80, 80, 80, 8, 16, 80, 80, 20, 80, 40, 10, 5, 8, 4, 80, 80, 80, 40, 40, 80, 80, 80, 4, 8, 10, 5, 40, 80, 20, 80, 80, 16, 8, 80, 80, 80, 20, 80, 40, 10, 2, 16, 20, 80, 80, 80, 40, 40, 80, 80, 16, 16, 40, 10, 5, 40, 80, 20, 80, 16, 8, 40, 80, 80, 80, 20, 80, 40, 10, 8, 80, 20, 80, 80, 80, 40, 40, 80, 16, 4, 80, 40, 10, 10, 40, 80, 20, 16, 16, 40, 40, 80, 80, 80, 20, 80, 40, 2] g = [2, 8, 9] m = [40, 40, 40] [2, 4, 8, 16, 32, 64, 128, 69, 138, 89, 178, 169, 151, 115, 43, 86, 172, 157, 127, 67, 134, 81, 162, 137, 87, 174, 161, 135, 83, 166, 145, 103, 19, 38, 76, 152, 117, 47, 94, 1] [8, 64, 138, 169, 43, 157, 134, 137, 161, 166, 19, 152, 94, 4, 32, 69, 178, 115, 172, 67, 162, 174, 83, 103, 76, 47, 2, 16, 128, 89, 151, 86, 127, 81, 87, 135, 145, 38, 117, 1] [9, 81, 168, 16, 144, 174, 70, 69, 60, 166, 185, 169, 25, 38, 155, 86, 26, 47, 49, 67, 42, 4, 36, 137, 111, 64, 15, 135, 93, 89, 53, 103, 179, 115, 100, 152, 59, 157, 104, 1] phi_n = 160 = 2^5 * 5 m1 = 2^3 * 5 40 divides 160 m2 = 2^4 * 5 40 divides 160 m3 = 2^2 * 5
Error in lines 47-50 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 3, in <module> IndexError: list index out of range