| Hosted by CoCalc | Download
#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]