# OK to post

# PART 1: EXAMPLES FROM TUTORIAL BOOK:
# -----------------------

# taylor series
taylor(1/sqrt(1-x),x=0,5);

# solving differential equations
f:='f';
y:=f(x);
dy:=diff(y,x);
ddy:=diff(dy,x);
dsolve(ddy+5*dy+6*y=sin(x)*exp(-3*x),y);
y:='y';

# plotting
plot(sin(x),x=-2*Pi..2*Pi);
plot([cos(t),1/2*sin(t),t=0..2*Pi]);

with(plots):
polarplot(cos(5*t),t=0..2*Pi);
plot3d(exp(-(x^2+y^2-1)^2),x=-2..2,y=-2..2);

with(plots):
spacecurve([cos(t),sin(t),t],t=0..4*Pi,numpoints=200);

with(plots):
implicitplot3d(y^2-x^2=x,x=-2..2,y=-2..2,z=-4..4);

# linear algebra:
with(linalg):
v:=vector([1,2,3]);
A:=matrix(2,2,[1,2,3,4]);
B:=matrix(2,2,[-1,-2,-3,-4]);
evalm(A+B);
evalm(%);

# PART 2: COMPARING EA AND EAnew:
# -----------------------

#m>n m=n*q+r (r= m mod n)
#gcd(m,n)=gcd(n,r)  
#gcd(n,0)=n
#EA(m,n): inputs m>n and outputs the gcd(m,n)
EA:=proc(m,n) local q,r:
if n=0 then
 RETURN(m):
fi:
r:=m mod n:
EA(n,r):
end:

#added after class:
#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:

# BEFORE TESTING; i think EAnew should be faster as it removes the overhead incurred by recursion.
# function calls require a few exrta CPU instructions as well as more memory.
# since it does not require any extra memory, it should also be able to work on much larger numbers

for i from 1 to 3 do
    a:=rand(10^50000..10^50001)(): b:=rand(10^50000..10^50001)(): 
    time(EAnew(a,b));
    time(gcd(a,b));
od;

# gcd() is MUCH faster than EAnew, it must use a much more clever algorithm (or is just much better optimized)

# PART 3: EstimateProbGCD PROCEDURE:
# -----------------------

EstimateProbGCD:=proc(n,k) local s, i, a, b:
    s:=0; # number successes (relatively prime nums)

    for i from 1 to k do
        a:=rand(1..n)();
        b:=rand(1..n)();

        if gcd(a,b) = 1 then
            s:=s+1;
        fi;
    od;

    return evalf(s/k);
end;

for i from 1 to 3 do
    EstimateProbGCD(10^10,10^4)
od;

# PART 5: MakeRSAkeyG PROCEDURE:
# -----------------------

MakeRSAkeyG:=proc(digits, g) local L,i,j,n,p,d,e,m,s:
    L:=[]; # list of primes
    n:=1;
    m:=1;

    for i from 1 to g do:
        p:=rand(10^(digits-1)..10^digits-1)();
        p:=nextprime(p);

        if member(p, L) then
            return FAIL;
        fi;

        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;

MakeRSAkey:=proc(digits):
    MakeRSAkeyG(digits, 2)
end;

# MakeRSAkey(D1,3) is less secure since it makes n easier to factor (for the same number of digits).
# thus, it is possible to break the encryption with a brute-force attack more quickly

# PART 6: DIGITAL SIGNATURE CHALLENGE:
# -----------------------
encrypt:=proc(a,n,e):
    a&^e mod n;
end;

decrypt:=proc(c,n,d):
    c&^d mod n;
end;

SendMessage:=proc(a, sN, sD, rN, rE) local t: # takes in plaintext, sender's private key, and recipient's public key
    t:=decrypt(a, sN, sD);
    return encrypt(t, rN, rE);
end;

ReceiveMessage:=proc(c, rN, rD, sN, sE) local t: # takes in signed ciphertext, recipient's private key, and sender's public key
    t:=decrypt(c, rN, rD);
    return encrypt(t, sN, sE);
end;

# testing:
alice:=MakeRSAkey(100);
bob:=MakeRSAkey(100);

message:=123456789;

sentMessage:=SendMessage(message, alice[1], alice[3], bob[1], bob[2]);
receivedMessage:=ReceiveMessage(sentMessage, bob[1], bob[3], alice[1], alice[2]);
print(receivedMessage); # should be 123456789

# the message is signed since only alice could have used her decryption procedure !!!