#George Spahn
#1/28/2024
#OK TO POST

#2
#The new version is better because maple has a low max recursion depth.
#Fewer function calls will also be faster than more, so a single loop performs better than a big recursion tree.

#EAnew is still slightly slower than gcd. Since we don't know what maple is doing under the hood, it's hard to say why.
#Probably maple just has better low level optimization for built in functions.

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

#EstimateProbGCD(10^10,10^4) came out to 0.609, 0.601, 0.614

#3
#Probability that two numbers are both divisible by p is 1/p^2

# Let Pn be the probability that they share a prime factor that is smaller than the n^th prime
# P1 = 1/2^2 = 1/4
# P2 = P1 + (1-P1)/3^2 = 1/9 +  P1*8/9 =  1/9 + 2/9 = 1/3
# P3 = 1/25 + 24/25 * 1/3 = 9/25

#PN = 1/pn^2 + P(N-1) * (1 - 1/pn^2)

EstimateTheory := proc(K)
local V,p,i:
V := 1/4:
p := 3:
for i from 1 to K do
V := V*(1-1/p^2) + 1/p^2:
p := nextprime(p):
od:
evalf(1-V):
end:

# EstimateTheory(100) came out to 0.608
# This is also 6/pi^2 but I don't remember the  proof

#6

MakeRSAkey:=proc(D1) local n,d,S,m,p,q,e:
p:=NextPrime1(rand(10^(D1-1)..10^D1-1)()):
q:=NextPrime1(rand(10^(D1-1)..10^D1-1)()):
if p=q then
  RETURN(FAIL):
fi:
n:=p*q:
m:=(p-1)*(q-1):
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:

signature := proc(n,d,m)
m&^d mod n:
end:

verif := proc(n,e,s)
s&^e mod n:
end: