#OK to post homework 
#Natalya Ter-Saakov, Jan 28, 2024, Assignment 3
read "C3.txt":

#Problem 2
#Since EAnew doesn't use a level of recursion for every step in the Euclidean Algorithm, it cannot throw a level of recursion error. 

#a:=rand(10^50000..10^50001)(): b:=rand(10^50000..10^50001)(): time(gcd(a,b)); time(EAnew(a,b)); 
#runs gcd in about 0.02 seconds and EAnew in about 9 seconds

#Problem 3

#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

EstimateProbGCD:=proc(N,K) local a,b,count,i,r:
count:=0:
for i from 1 to K do
	r:=rand(1..N):
	a:=r():
	b:=r():
	if gcd(a,b)=1 then
		count+=1:
	fi:
od:
evalf(count/N):
end:

#Running EstimateProbGCD(10^10,10^4) multiple times, I get approximately 6*10^(-7) each time.

#Problem 4
#Optional, have not done yet

#Problem 5

#MakeRSAkeyG(D1,g): that takes n (the modulus) to be a product of g distinct primes

MakeRSAkeyG:=proc(D1,g) local n,d,S,m,p,r,e, i:
n:=1:
m:=1:
r:=rand(10^(D1-1)..10^D1-1):
for i from 1 to g do
	p:=nextprime(r()):
	while 0=n mod p do
	p:=nextprime(r()):
	od:
	n:=n*p:
	m:=m*(p-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:

#The more factors n has, in theory, the easier it is to factor. However, this is based on the thought that the factors will be smaller. Since we are specifying a size for the primes, instead of a size for n, it should be just as easy to factor, but the n's will be larger.

#Problem 6
#Optional, have not done yet