# Jordan Jones # SM473B # Worksheet Group Theory print("Jordan Jones" + "\n" + "SM473B" + "\n" + "Worksheet: Group Theory \n") P = Primes() p = [] q = [] for i in range(3,1000): if(i in P): p.append(i) for k in range(3,1000): if(k in P): q.append(k) @interact def MYRSAWK(p=selector(p),q=selector(q)): # Pick two primes from the drop box, these will assign p and q # Question 1 print("Question 1 \n") # Compute n = p*q n = p*q print("We start with p = " + str(p) + " and q = " + str(q) + " so n = " + str(n)) # Let A be the set of invertible elements in Zmodn A = [] # Let B be the set of non-invertible elments in Zmodn B = [] # Compute the sets elements for i in range(1,n+1): if(gcd(i,n) == 1): A.append(i) else: B.append(i) print("The number of invertible elements in n is " + str(len(A)) + ", so we will name this Q. \n") Q = (p-1)*(q-1) print("The elements that are invertible are:") print(A) print("\n") print("The elements that are not invertible are:") print(B) print("\n") # Question 2 print ("Question 2 \n") # Let C be the set of (a,b). This is all invertible elements and their # respective order such that a is the element and b is the order in the set Zmodn C = [] for z in A: for k in range(1,Q): if(power_mod(z,k,n) == 1): C.append((z,k)) break print("The length of C is " + str(len(C)) + " where C is the set of ordered pairs representing an invertable element and its order: \n") print("C =") print(C) print("\n") D = [] for a in C: if(mod(a[1],Q) != a[1]): D.append(a[0]) print("There are " + str(len(D)) + " elements whose order does not divide Q" + "\n") # Question 3 print("Question 3 \n") # Choose elements a = 52, b = 70, and c = 86 with orders 77, 4, and 22 respectively # For simplicity we will keep them in the form (52,77), (70,4) and (86,22) # We will display the cyclic groups generated by these elements def random_between(j,k): a = int(random()*(k-j+1))+j return a a,b,c = random_between(1,Q),random_between(1,Q),random_between(1,Q) a,b,c = C[a],C[b],C[c] print("We pick three random invertible elements from the set C: a = " + str(a) +" b = "+ str(b) + " c = " + str(c) + "\n") d = [a,b,c] for i in d: X = [] Y = 0 for k in range(0,i[1]): Y = power_mod(i[0], k, n) X.append(Y) print("The cyclic subgroup generated by " + str(i[0]) + " is: ") print("<" + str(i[0]) + "> = " ) print(X) print("\n") print("NOTE: There are " + str(i[1]) + " elements in this set.") print("\n") # We set F equal to the form of Q factored F = factor(Q) print("The factorization of Q is " + str(F) + "\n") print("We confirm that the order of element a, b, and c divide Q: \n" ) for i in d: print("The order of " + str(i[0]) + " is " + str(i[1]) + " so we see that: \n") r = Q/i[1] print(str(Q) + "\\" + str(i[1]) + " = " + str(r) + "\n") # We will now observe why the RSA decryption system works print("We will now observe why the RSA decryption system works. For each choosen element we see that: \n") for i in d: m = power_mod(i[0],i[1],n) print(str(i[0]) + "^" + str(i[1]) + " is equivalent to " + str(m) + " mod " + str(n)) print("This means that any element in the cyclic groups of the invertible elements can be decrypted. \n") # We select a random element in Zmodn that is not invertible and name this element y print("\n") w = len(B) y = random_between(1,w) y = B[y] Y = [] for i in range(1,20): t = power_mod(y,i,n) Y.append(t) print("We pick a random element, " + str(y) + ", and compute the set of its first 20 powers: \n") print(str(y) + " creates the set:") print(Y) print("\n") print("We observe that the identity element is not in this set, so the set repeats itself.") print("This means that any non-invertible element cannot be decrypted. \n") # Now run the program and click on the 2 prime numbers that you would like to use.

Jordan Jones
SM473B
Worksheet: Group Theory

Interact: please open in CoCalc