#OK to post homework
#GLORIA LIU, Jan 22 2024, Assignment 2

#=====================================#
#1. Read and do all the examples, plus make up similar ones, in pages 30-60 of Frank Garvan's awesome Maple booklet

#Chapter 4
s:=seq(i^2, i = 1..100):
s[4]:
a:{1,2,3,4}: b:={2,4,6,8}:
a union b:
S:=table([(2)=D,(4)=E,(6)=D*E*F]):
F:=array(1..2,1..3,[[1,2,3],[5,9,7]]):
F[1,2]:=10:
s:='s': a:='a': b:='b': S:='S': F:='F':

#Chapter 5
g:=(x,y)->x*y/(1+x^2+y^2):
simplify(g(sin(t),cost(t))):
X:=[seq(evalf(-4+i/10,4),i=0..10)]:
Y:=map(H,X):
Product(1-3^'i','i'=1..5):
f:=x->(x^2-4)/(x-2):
Limit(f,x=infinity):
z:exp(x*y)(1+sqrt(x^2+3*y^2-x)):
diff(z,x):
with(student):
G:=Int(x^4/sqrt(1-x^10),x):
G2:=changevar(u=x^5,G,u):
G:=Int(x*cos(3*x),x):
intparts(G,x):
y:=1/sqrt(1-x):
taylor(y,x=0,5):
g:='g': X:='X': Y:='Y': f:='f': z:='z': G:='G': G2:='G2': y:='y':

#=====================================#
#2. Read and understand this lecture note. Make up similar excercises but with much bigger number, and use Maple as a "calculator".

#16.1 Checking Euler's theorem
with(NumberTheory):
#A function to check whether a, coprime to n, satisfies Euler's Theorem
CheckEulerThm:=proc(a,n) local t, a1:
t:=Totient(n):
a1:=a&^t mod n:
a1 mod n:
end:
#Try for various large numbers
results := [0 $ 50]:
for i from 51 to 100 do:
 n1:=rand(10^(i-1)..10^i-1)():
 S:=rand(10^(i-2)..n1-1)():
 #print(S);
 for a2 from S to n1-1 while gcd(a2,n1)>1 do od: 
 #print(a2, n1, gcd(a2, n1));
 results[i-50] := CheckEulerThm(a2, n1):
od:
results;
n1:='n1': i:='i':

#16.2 Finding the deciphering key d for given p, q, and public key e, and decipher message m
FindSolution:=proc(p,q,e,m) local t,d,m1:
t:=(p-1)*(q-1):
if gcd(e, t)>1 then
 RETURN(FAIL):
fi:
d:=e&^(-1) mod t:
if gcd(m, p*q)>1 then
 RETURN(FAIL):
fi:
m1:=m&^d mod (p*q):
#ME1(m,d,p*q):
m1 mod (p*q):
end:

#Try for various large numbers
originalMessages:=[0$50]:
decodedMessages:=[0$50]:
for i from 51 to 100 do:
 p1:=nextprime(rand(10^(i-1)..10^i-1)()):
 q1:=nextprime(rand(10^(i-1)..10^i-1)()):
 n1:=p1*q1:
 n2:=(p1-1)*(q1-1):
 S:=rand(n2/2..n1-1)():
 for m2 from S to n1-1 while gcd(m2,n1)>1 do od:
 originalMessages[i-50]:=m2:
 for e1 from S to n2-1 while gcd(e1,n2)>1 do od:
 m3:=FindSolution(p1, q1, e1, m2&^(e1) mod (p1*q1)):
 decodedMessages[i-50]:=m3:
od:
originalMessages;
decodedMessages;
p1:='p1': q1:='q1': n1:='n1': n2:='n2': S:='S': m2:='m2': e1:='e1': m3:='m3': i:='i':

#=====================================#
#3.
#I. Write a procedure
#MyIfactor(n)
#that inputs a positive integer and outputs a list of its prime factors (with repetition), in weakly increasing order. For example, MyIfactor(100) should output [2,2,5,5].
with(numtheory):
MyIfactor:=proc(n) local L,p,i,a,j,n1:
n1:=n:
L:=[]:
if n=1 then
 L:=[]:
elif isprime(n) then
 L:=[n]:
else
i:=1:
for a from 1 to n while n1>1 do
 for j from i to n while n1 mod ithprime(j) > 0 do od:
 p:=ithprime(j):
 i:=j:
 print(p);
 L:=[op(L),p]:
 n1:=n1/p:
od:
fi:
L:
end:

time(MyIfactor(100));
time(ifactor(100));
#Both time 0 for the small number.
m:=rand(10^(9)..10^(10)-1)();
time(ifactor(m));
time(MyIfactor(m));
#For a random 10 and 20 digit number, there was a .009s and .041s difference, MyIfactor was slower each time