#OK to post homework
#Lucy Martinez, 01-26-2024, Assignment 3

with(numtheory):
with(NumberTheory):

Help:=proc() :
 print(`EstimateProbGCD(N,K), MakeRSAkeyG(D1,g)`):
end:


# Problem 2: Look at the Maple procedure EAnew(m,n) that I added after class,
# and compare it with Maple's gcd(m,n) and EA(m,n). Why is EAnew better?
# Also run several times, in a Maple session (once you read C3.txt):
# a:=rand(10^50000..10^50001)(): b:=rand(10^50000..10^50001)(): 
# time(gcd(a,b)); time(EAnew(a,b));
# Who is faster? Why?

# Answer: time(gcd(a,b)); outputs 0.
# time(EAnew(a,b)); outputs 1.656 seconds
# time(EA(a,b)); outputs 1.781 seconds
# Maple's procedure is faster



# Problem 3: Write a procedure EstimateProbGCD(N,K)
# that estimates the probability (given in floating point) that two randomly chosen 
# integers between 1 and N are relatively prime, by doing the experiment K times.
# What did you get for EstimateProbGCD(10^10,10^4)
# Run it several times, and see whether the answers are close.
EstimateProbGCD:=proc(N,K) local co,i,p,q:
co:=0:
for i from 1 to K do 
 p:=rand(1..N)():
 q:=rand(1..N)():
 if gcd(p,q)=1 then
  co:=co+1:
 fi:
od:
evalf(co/K):
end:

# [seq(EstimateProbGCD(10^10,10^4),i=1..22)];
# outputs
# [ 0.6050000000, 0.6032000000, 0.5962000000, 0.6120000000, 0.6039000000, 0.6141000000,
#   0.6025000000, 0.6122000000, 0.6027000000, 0.6129000000, 0.6096000000, 0.6121000000,
#   0.6083000000, 0.6060000000, 0.6132000000, 0.6094000000, 0.5993000000, 0.6042000000,
#   0.6105000000, 0.6003000000, 0.6082000000]
# which are all relatively close to each other



# Problem 5: Write a procedure MakeRSAkeyG(D1,g);
# that takes n (the modulus) to be a product of g distinct primes (MakeRSAkeyG(D1,2) 
# should do the same as MakeRSAkey(D1)) 
MakeRSAkeyG:=proc(D1,g) local i,n, d, m, p, q, S,e,S1,j:
S1:=[]:
n:=1:
for i from 1 to g do
 S1:=[op(S1),nextprime(rand(10^(D1-1)..10^D1-1)())]:
 n:=n*S1[i]:
od:

if nops(S1)<>g then
 return(FAIL):
fi:

m:=1:
for j from 1 to nops(S1) do
 m:=m*(S1[j]-1): 
od:

# e is public
S:=rand(m/2..m-1)():

# keep looking for a relatively prime e to m
for e from S to m-1 while gcd(e,m)>1 do
od:

# d is private
d:= e&^(-1) mod m:

[n,e,d]:

end:

# Why is, for example, MakeRSAkey(D1,3) less secure?
#
# Answer: MakeRSAkey(D1,3) is less secure because it is "easier" to find one out of three
#  prime factors than one out of two. Once you find one of the prime factors,
#  dividing the modulus by it will reduced the modulus by a lot.
#  It also has to do with how much faster you can find each of the factors.




######### From C3.txt
#EAnew(m,n): inputs m>n and outputs the gcd(m,n) using iteration rather than recursion
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: