SharedRSA Practice WS.sagewsOpen in CoCalc
RSA Worksheet
# I choose primes 101 and 61
p=11
q=17
n=p*q
n
phi=(p-1)*(q-1)
phi
#questions 1/3
for a in range(1,n):
if gcd(a,n)==1:
print "g = " + str(a)
#This is 2/3 #1/C Miller helped me with my double for loop and my print statements
for m in range(1, phi):
if power_mod(a, m, n)==1:
print "m = " +str(m)
if phi % m ==0: #This is checking Lagrang's theorem
print str(m) + "divides" + str(phi)
break
#This is for 3/3
print "the cyclic group for g=4 is: "
for x in range( 1,(20+1)): #sage loops stop at one before so I need to go end loop at 25, because last number in loop should equal 1
power_mod(4, x, n)
print "the cyclic group for g=5 is:"
for y in range( 1,(80+1)): #sage loops stop at one before so I need to go end loop at 25, because last number in loop should equal 1
power_mod(5, y, n)
print "the cyclic group for g=8 is:"
for z in range( 1,(40+1)): #sage loops stop at one before so I need to go end loop at 25, because last number in loop should equal 1
power_mod(8, z, n)
print"This is the factorization of phi:"
factor(phi)
print "This is the factorization of m=20:"
factor(20)
print"This shows that m=20 divides phi:"
phi%20
print "This is the factorization of m=80:"
factor(80)
print"This shows that m=80 divides phi:"
phi%80
print "This is the factorization of m=40:"
factor(40)
print"This shows that m=40 divides phi:"
phi%40

#This is teh reason why the RSA decryption works
power_mod(4,20,n)
power_mod(5,80,n)
power_mod(8,40,n)

power_mod(4,phi,n)
power_mod(5,phi,n)
power_mod(8,phi,n)

#Let g=11 because there is no inverse mod n
for z in range(1,20):
power_mod(11,z,n)
#from this for loop I notice that there is a cycle with the numbers

187 160 g = 1 m = 1 1divides160 g = 2 m = 40 40divides160 g = 3 m = 80 80divides160 g = 4 m = 20 20divides160 g = 5 m = 80 80divides160 g = 6 m = 80 80divides160 g = 7 m = 80 80divides160 g = 8 m = 40 40divides160 g = 9 m = 40 40divides160 g = 10 m = 16 16divides160 g = 12 m = 16 16divides160 g = 13 m = 20 20divides160 g = 14 m = 80 80divides160 g = 15 m = 40 40divides160 g = 16 m = 10 10divides160 g = 18 m = 10 10divides160 g = 19 m = 40 40divides160 g = 20 m = 80 80divides160 g = 21 m = 4 4divides160 g = 23 m = 16 16divides160 g = 24 m = 80 80divides160 g = 25 m = 40 40divides160 g = 26 m = 40 40divides160 g = 27 m = 80 80divides160 g = 28 m = 80 80divides160 g = 29 m = 80 80divides160 g = 30 m = 20 20divides160 g = 31 m = 80 80divides160 g = 32 m = 8 8divides160 g = 35 m = 10 10divides160 g = 36 m = 40 40divides160 g = 37 m = 80 80divides160 g = 38 m = 20 20divides160 g = 39 m = 80 80divides160 g = 40 m = 80 80divides160 g = 41 m = 80 80divides160 g = 42 m = 40 40divides160 g = 43 m = 8 8divides160 g = 45 m = 16 16divides160 g = 46 m = 80 80divides160 g = 47 m = 20 20divides160 g = 48 m = 80 80divides160 g = 49 m = 40 40divides160 g = 50 m = 10 10divides160 g = 52 m = 10 10divides160 g = 53 m = 40 40divides160 g = 54 m = 16 16divides160 g = 56 m = 16 16divides160 g = 57 m = 80 80divides160 g = 58 m = 80 80divides160 g = 59 m = 40 40divides160 g = 60 m = 40 40divides160 g = 61 m = 80 80divides160 g = 62 m = 80 80divides160 g = 63 m = 80 80divides160 g = 64 m = 20 20divides160 g = 65 m = 16 16divides160 g = 67 m = 2 2divides160 g = 69 m = 5 5divides160 g = 70 m = 40 40divides160 g = 71 m = 80 80divides160 g = 72 m = 20 20divides160 g = 73 m = 80 80divides160 g = 74 m = 80 80divides160 g = 75 m = 80 80divides160 g = 76 m = 8 8divides160 g = 78 m = 16 16divides160 g = 79 m = 80 80divides160 g = 80 m = 80 80divides160 g = 81 m = 20 20divides160 g = 82 m = 80 80divides160 g = 83 m = 40 40divides160 g = 84 m = 10 10divides160 g = 86 m = 5 5divides160 g = 87 m = 8 8divides160 g = 89 m = 4 4divides160 g = 90 m = 80 80divides160 g = 91 m = 80 80divides160 g = 92 m = 80 80divides160 g = 93 m = 40 40divides160 g = 94 m = 40 40divides160 g = 95 m = 80 80divides160 g = 96 m = 80 80divides160 g = 97 m = 80 80divides160 g = 98 m = 4 4divides160 g = 100 m = 8 8divides160 g = 101 m = 10 10divides160 g = 103 m = 5 5divides160 g = 104 m = 40 40divides160 g = 105 m = 80 80divides160 g = 106 m = 20 20divides160 g = 107 m = 80 80divides160 g = 108 m = 80 80divides160 g = 109 m = 16 16divides160 g = 111 m = 8 8divides160 g = 112 m = 80 80divides160 g = 113 m = 80 80divides160 g = 114 m = 80 80divides160 g = 115 m = 20 20divides160 g = 116 m = 80 80divides160 g = 117 m = 40 40divides160 g = 118 m = 10 10divides160 g = 120 m = 2 2divides160 g = 122 m = 16 16divides160 g = 123 m = 20 20divides160 g = 124 m = 80 80divides160 g = 125 m = 80 80divides160 g = 126 m = 80 80divides160 g = 127 m = 40 40divides160 g = 128 m = 40 40divides160 g = 129 m = 80 80divides160 g = 130 m = 80 80divides160 g = 131 m = 16 16divides160 g = 133 m = 16 16divides160 g = 134 m = 40 40divides160 g = 135 m = 10 10divides160 g = 137 m = 5 5divides160 g = 138 m = 40 40divides160 g = 139 m = 80 80divides160 g = 140 m = 20 20divides160 g = 141 m = 80 80divides160 g = 142 m = 16 16divides160 g = 144 m = 8 8divides160 g = 145 m = 40 40divides160 g = 146 m = 80 80divides160 g = 147 m = 80 80divides160 g = 148 m = 80 80divides160 g = 149 m = 20 20divides160 g = 150 m = 80 80divides160 g = 151 m = 40 40divides160 g = 152 m = 10 10divides160 g = 155 m = 8 8divides160 g = 156 m = 80 80divides160 g = 157 m = 20 20divides160 g = 158 m = 80 80divides160 g = 159 m = 80 80divides160 g = 160 m = 80 80divides160 g = 161 m = 40 40divides160 g = 162 m = 40 40divides160 g = 163 m = 80 80divides160 g = 164 m = 16 16divides160 g = 166 m = 4 4divides160 g = 167 m = 80 80divides160 g = 168 m = 40 40divides160 g = 169 m = 10 10divides160 g = 171 m = 10 10divides160 g = 172 m = 40 40divides160 g = 173 m = 80 80divides160 g = 174 m = 20 20divides160 g = 175 m = 16 16divides160 g = 177 m = 16 16divides160 g = 178 m = 40 40divides160 g = 179 m = 40 40divides160 g = 180 m = 80 80divides160 g = 181 m = 80 80divides160 g = 182 m = 80 80divides160 g = 183 m = 20 20divides160 g = 184 m = 80 80divides160 g = 185 m = 40 40divides160 g = 186 m = 2 2divides160 the cyclic group for g=4 is: 4 16 64 69 89 169 115 86 157 67 81 137 174 135 166 103 38 152 47 1 the cyclic group for g=5 is: 5 25 125 64 133 104 146 169 97 111 181 157 37 185 177 137 124 59 108 166 82 36 180 152 12 60 113 4 20 100 126 69 158 42 23 115 14 70 163 67 148 179 147 174 122 49 58 103 141 144 159 47 48 53 78 16 80 26 130 89 71 168 92 86 56 93 91 81 31 155 27 135 114 9 45 38 3 15 75 1 the cyclic group for g=8 is: 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 This is the factorization of phi: 2^5 * 5 This is the factorization of m=20: 2^2 * 5 This shows that m=20 divides phi: 0 This is the factorization of m=80: 2^4 * 5 This shows that m=80 divides phi: 0 This is the factorization of m=40: 2^3 * 5 This shows that m=40 divides phi: 0 1 1 1 1 1 1 11 121 22 55 44 110 88 33 176 66 165 132 143 77 99 154 11 121 22