SharedGroups_WS.sagewsOpen in CoCalc

# 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