#Homework January 25th, 2024
#Ok to post

Help := proc(): print('EAnew(m,n), EstimateProbGCD(N,K), MakeRSAKeyG(D_,g)') : end:
with(NumberTheory):

# Comparing the time it takes using EAnew(m,n) and the built-in gcd(m,n)
#-----------------------------------------
EAnew:=proc(m,n) local m1,n1,m1new:
  m1:=m:
  n1:=n:

  while n1>0 do
    m1new:=n1:
    n1:=m1 mod n1:
    m1:=m1new:
  od:
end:

EAnew_time := 0: gcd_time := 0:
a := rand(10^50000..10^50001)(): b := rand(10^50000..10^50001)():

EAnew_time := time(EAnew(a,b)): gcd_time := time(gcd(a,b)):

printf("EAnew() time: %f\n gcd() time: %f\n", EAnew_time, gcd_time);

# Estimating the probability that two randomly chosen integers between 1 and N are relatively prime, by doing experiment K times
#------------------------------------------
EstimateProbGCD := proc(N,K) local i, prob, count, num1, num2:
  count := 0:
  prob := 0:

  for i from 1 to K do
    num1 := rand(1..N)():
    num2 := rand(1..N)():

    if gcd(num1, num2)=1 then
      count := count + 1:
    fi:
  od:

  prob := (count/K):

  return prob;

end:

tot_prob := 0:
N := 10000:
for i from 1 to N do
  prob := EstimateProbGCD(10^10, 10^4):
  tot_prob := tot_prob + prob:
od:

printf("The average probability is %f\n", tot_prob/N);
print(`I don't know the significance of 0.68, but that will be the limit of this probability as N approaches infinity.`);

#Write a procedure MakeRSAkeyG(D1,g); that takes n (the modulus) to be a product of g distinct primes
#-------------------------------------------
MakeRSAKeyG := proc(D_, g) local d, e, i, n, m, S, primes:
  primes := []: 
  for i from 1 to g do
    primes := [op(primes), nextprime(rand(10^D_..10^(D+1)-1)())]
  od:

  if nops(primes) <> nops(convert(primes, set)) then 
    return FAIL 
  fi:
  
  n := 1: m := 1:
  for i from 1 to nops(primes) do
    n := n*primes[i]: m := m*primes[i] - 1:
  od:
  
  S := rand(m/2..m-1)():
  for e from S to m-1 while gcd(e,m)>1 do od:
  d:=e&^(-1) mod m:

  [n,e,d]:

end:

RSA_key := MakeRSAKeyG(200, 2):

do
  text := rand(0..RSA_key[1])():
until AreCoprime(text, RSA_key[1]):

ciphertext := text&^(RSA_key[2]) mod RSA_key[1];
message := ciphertext&^(RSA_key[3]) mod RSA_key[1];

print(`A greater value of g (> 2) is considered less secure than g = 2 because it reduces the time complexity of a brute force attack to O(n^(1/g)), making the attack more efficient. In contrast, smaller values of g are deemed more secure as they increase the time required for a brute force attack.`);