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
Interact: please open in CoCalc