# Okay to post homework
# Ryan Badi, January 28, 2024, Homework #2

with(NumberTheory):

Help := proc():
  printf("Available processes: MyIfactor(n) VerifyEuler(m, n)\n"):
end:

# Task 2
# Accepts two positive integers m and n
# Returns an evaluation of Euler's theorem on integers m and n
VerifyEuler := proc(m, n):
  if not AreCoprime(m, n) then return true fi:
  if m^phi(n) mod n = 1 then return true else return false fi:
end:

# Task 3
# Accepts a positive integer n
# Returns a list containing n's prime factorization in weakly increasing order
MyIfactor := proc(n) local p, n_, k, P:
  p := 2:
  n_ := n:
  k := 1:
  while n_ > 1 do:
    if n_ mod p = 0 then:
      P[k] := p:
      k := k + 1:
      n_ := n_ / p:
    else 
      p := nextprime(p):
    fi:
  od:
  return P:
end:

printf("Testing Task 2.16.1\n"):
for i from 1 to 1000 do:
  if not VerifyEuler(rand(10^4..10^5)(), rand(10^4..10^5)()) then printf("BAD RESULT\n") fi:
od:
printf("VerifyEuler(rand(10^4..10^5)(), rand(10^4..10^5)())\n%a\n", VerifyEuler(rand(10^4..10^5)(), rand(10^4..10^5)())):
printf("\n"):

printf("Testing Task 2.16.2.i\n"):
p := nextprime(rand(10^4..10^5)()):
q := nextprime(rand(p..10^5)()):
n := p * q:
e := nextprime(q):
if gcd(e, phi(n)) = 1 then printf("gcd(e, phi(n)) = 1\ntrue\n") else printf("gcd(e, phi(n)) = 1\nfalse\n") fi:
printf("\n"):

printf("Testing Task 2.16.2.ii\n"):
d := e&^(-1) mod phi(n):
printf("e&^(-1) mod phi(n)\n%a\n", d):
printf("\n"):

printf("Testing Task 2.16.2.ii\n"):
encrypted_message := rand(10^4..10^5)():
printf("gcd(n, encrypted_message)\n%a\n", gcd(n, encrypted_message)):
decrypted_message := encrypted_message&^d mod n:
printf("Decrypted message\n%a\n", decrypted_message):

MyT := 0:
T := 0:
for i from 1 to 100 do:
  t1 := time():
  MyP := MyIfactor(765432188):
  t2 := time():
  P := ifactor(765432188):
  t3 := time():
  MyT := MyT + (t2 - t1):
  T := T + (t3 - t2):
od:

Help():
printf("\n"):
printf("Testing Task 3\n"):
printf("MyP := MyIfactor(765432188)\nMyP[1] = %a, MyP[2] = %a, MyP[3] = %a, MyP[4] = %a, MyP[5] = %a\n", MyP[1], MyP[2], MyP[3], MyP[4], MyP[5]):
printf("MyIfactor(765432188) takes an average of %a seconds\nifactor(765432188) takes an average of %a seconds\n", MyT / 100, T / 100);