SharedWorksheetRSA2.sagewsOpen in CoCalc
#Devin Nathan
#Received help from Jade Miller

#Question 1
p = 17 #find two large primes
q= 23 #this is the other large prime
n = p*q #n is equal to these large primes multiplied together
invertible = [] #create an empty array L
not_invertible = [] #create an empty array M
for a in range(n): #establish a for loop to run up to "n" times
    if gcd(a,n) == 1: #if the gcd of a and n is 1...
        invertible.append(a) #add a to the list L
        #print(a)
    else: # or else...
        not_invertible.append(a) #add a to the list M
        #print(a)
#print invertible
phi_n = (p-1)*(q-1) #create phi_n

if phi_n == len(invertible): #ensure phi_n is the same length as the array l
    print"yay" #if this happens print yay because its right

#Question 2
#we are trying to find g^m = 1 mod n
#create two separate for loops to go through the numbers g then through m
order = []
for g in range(0, phi_n): #create a for loop that counts for g to go up to n
    for m in range(1, n):#create a for loop that counts for m to go up to n
        if (power_mod(invertible[g], m, n) == 1): #if the power mod is equal to 1 we know we have a match
            order.append(m)
            # print str(g) + " has order of " + str(m)
            #if phi_n % m != 0: #if phi_n and m have remainder 0 we know they divide
                #print "m does not divide phi_n"
            break #use a break to break out of this for loop and begin a new g. We only want the minimal amount of times for the order of each g.
#print order
for z in range (0, phi_n):
    if phi_n%order[z] != 0:
        print "bad"
#question 3
g1 = []
g2 = []
g3 = []

g = [invertible[2], invertible[8], invertible[16]]
print str(g)

m = [order[2], order[8], order[16]]
print str(m)

for a in range(1, m[0]+1):
    g1.append(power_mod(g[0],a,n))
for b in range(1, m[1]+1):
    g2.append(power_mod(g[1],b,n))
for c in range(1, m[2]+1):
    g3.append(power_mod(g[2],c,n))
print str(g1)
print str(g2)
print str(g3)
# #
Fphi = factor(phi_n); Fphi
Fm1 = factor(m[0]); Fm1
Fm2 = factor(m[1]); Fm2
Fm3 = factor(m[2]); Fm3

for f in range(0, 3):
    if phi_n%m[f] !=0:
        print "you gonna have a bad time"

for h in range(0, 3):
    print str(g[h]) + "^" + str(m[h]) + " mod(391) " + str(power_mod(g[h], m[h], n))
    print str(g[h]) + "^" + str(phi_n) + " mod(391) " + str(power_mod(g[h], phi_n, n))

    
g = 17 #it is never going to be 1 because it is a factor so it just repaeats itself.
j = []
for k in range (1, 50):
    j.append(power_mod(g,k,n))
print str(j)
yay [3, 9, 18] [176, 88, 11] [3, 9, 27, 81, 243, 338, 232, 305, 133, 8, 24, 72, 216, 257, 380, 358, 292, 94, 282, 64, 192, 185, 164, 101, 303, 127, 381, 361, 301, 121, 363, 307, 139, 26, 78, 234, 311, 151, 62, 186, 167, 110, 330, 208, 233, 308, 142, 35, 105, 315, 163, 98, 294, 100, 300, 118, 354, 280, 58, 174, 131, 2, 6, 18, 54, 162, 95, 285, 73, 219, 266, 16, 48, 144, 41, 123, 369, 325, 193, 188, 173, 128, 384, 370, 328, 202, 215, 254, 371, 331, 211, 242, 335, 223, 278, 52, 156, 77, 231, 302, 124, 372, 334, 220, 269, 25, 75, 225, 284, 70, 210, 239, 326, 196, 197, 200, 209, 236, 317, 169, 116, 348, 262, 4, 12, 36, 108, 324, 190, 179, 146, 47, 141, 32, 96, 288, 82, 246, 347, 259, 386, 376, 346, 256, 377, 349, 265, 13, 39, 117, 351, 271, 31, 93, 279, 55, 165, 104, 312, 154, 71, 213, 248, 353, 277, 49, 147, 50, 150, 59, 177, 140, 29, 87, 261, 1] [9, 81, 338, 305, 8, 72, 257, 358, 94, 64, 185, 101, 127, 361, 121, 307, 26, 234, 151, 186, 110, 208, 308, 35, 315, 98, 100, 118, 280, 174, 2, 18, 162, 285, 219, 16, 144, 123, 325, 188, 128, 370, 202, 254, 331, 242, 223, 52, 77, 302, 372, 220, 25, 225, 70, 239, 196, 200, 236, 169, 348, 4, 36, 324, 179, 47, 32, 288, 246, 259, 376, 256, 349, 13, 117, 271, 93, 55, 104, 154, 213, 353, 49, 50, 59, 140, 87, 1] [18, 324, 358, 188, 256, 307, 52, 154, 35, 239, 1] 2^5 * 11 2^4 * 11 2^3 * 11 11 3^176 mod(391) 1 3^352 mod(391) 1 9^88 mod(391) 1 9^352 mod(391) 1 18^11 mod(391) 1 18^352 mod(391) 1 [17, 289, 221, 238, 136, 357, 204, 340, 306, 119, 68, 374, 102, 170, 153, 255, 34, 187, 51, 85, 272, 323, 17, 289, 221, 238, 136, 357, 204, 340, 306, 119, 68, 374, 102, 170, 153, 255, 34, 187, 51, 85, 272, 323, 17, 289, 221, 238, 136]