# OK to post homework
# Alex Varjabedian, 23-Jan-2024, Homework 2

Help := proc() print(`VerifyEuler(n)\nMyIfactor(n)`) end:

###########################
# ----------------------- #
# PART 1 - Maple examples #
# ----------------------- #
###########################

# 4.1 - Sequences
seq(f(i), i = 1..6);
seq(i^2, i = 1..5);
x$7;
L := a + b + 2*c + 3*d;
op(%);
nops(L);
op(3, L);

# 4.2 - Sets
a := {1, 2, 3, 4};
b := {2, 4, 6, 8};
a union b;
a intersect b;
a minus b;
member(2, a);
member(10, b);
b[2];

# 4.3 - Lists
L1 := [a1, b1, c1, d1];
L2 := [e1, f1, g1];
L := [op(L1), op(L2)];

# 4.4 - Tables
S := table([1 = A, D = B + C, 5 = A*B*C]);
S[D];

# 4.5 - Arrays
A := array(1..2, 1..2);
A[1, 1] := 5;
A[1, 2] := 3;
A[2, 1] := 9;
A[2, 2] := 8;
op(A);

# 5.1 - Defining functions
f := x -> x^2 - 3*x + 5;
g := (x, y) -> (x+y)*(3*x - y^2);
X := [8, 4, 6, 2, 1, 2, 3];
Y := map(f, X);

# 5.2 - Composition of functions
evalf((sin@cos)(4));
cos(4);
sin(%);
evalf(%);

# 5.3 - Summation and product
Sum(i^2, i = 1..10);
value(%);
sum(i^2, i = 1..10);
Product(i + 1, i = 1..10);
value(%);
product(i + 1, i = 1..10);

# 5.4 - Limits
Limit((x^2 - 4)/(x - 2), x = 2);
value(%);

# 5.5 - Differentiation
f := sin(cos(x + 5*sqrt(x))/ln(arctan(x)))^(e*sec(x^2));
diff(f, x);
diff(f, x$4);

# 5.6 - Extrema
maximize(sin(x) + cos(x));

# 5.7 - Integration
Int(x^2/sqrt(1-x^3), x);
value(%);
with(student):
Int(x^4 / sqrt(1 - x^10), x);
G := value(%);
G2 := changevar(u = x^5, G, u);
subs(u = x^5, G2);
diff(%, x);
Int(x*cos(3*x), x);
intparts(%, x);
value(%);

# 5.8 - Taylor and series expansions
y := 1/sqrt(1-x);
taylor(y, x = 0, 5);
J := product(1 - x^'i', 'i' = 1..50):
taylor(J^3, x = 0, 20);
coeff(%, x, 15);

##########################
# ---------------------- #
# PART 2 - RSA Exercises #
# ---------------------- #
##########################

with(NumberTheory):

# Exercise similar to Problem 16.1
# Verifying Euler's Theorem for n from 1 to 1500
# Accepts n, returns 0 for success and 1 for failure

VerifyEuler := proc(n): local A, phi_n, i, a:
A := {}:

for i from 1 to (n - 1) do
 if AreCoprime(i, n) then
  A := A union {i}:
 fi:
od:

phi_n := nops(A):

for a in A do
 if (a^phi_n mod n) <> 1 then
  return 1;
 fi:
od:

return 0;

end:

status := SUCCESS:
print(`Verifying Euler's Theorem for n from 1 to 1500`);
for i from 1 to 1500 do
 if VerifyEuler(i) = 1 then
  status := FAILURE:
  break;
 fi:
od:
print(status);


# Exercise similar to Problem 16.2
print(`Encryption and decryption process`);

# First, we generate two large prime numbers p, q, and an encryption key e (cannot be too large or else Maple overflows)
p := nextprime(rand(10^35..10^36-1)());
q := nextprime(rand(10^35..10^36-1)());
n := p*q;
phi_n := Totient(n);
e := nextprime(max(p, q));

# Next, we find d such that de = 1 (mod phi_n)
x := 'x': y := 'y':
d := e&^(-1) mod phi_n;

# Finally, generate a valid encrypted message and decrypt it
ciphertext := rand(0..n)():
while (not AreCoprime(ciphertext, n)) do
 ciphertext := rand(0..n)():
od:
ciphertext := ciphertext; # for display purposes
message := ciphertext&^d mod n;

print(`We can verify that our function is bijective by computing message^e mod n`);
encrypted_message := message&^e mod n;

################################
# ---------------------------- #
# PART 3 - Prime Factorization #
# ---------------------------- #
################################

# I decided to program this iteratively because recursion is slow

MyIfactor := proc(n) local p, pfactors, i, n_:
n_ := n:
pfactors := []:
while (n_ <> 1) do
 p := 0:
 while (p = 0 or n_ mod p <> 0) do
  p := nextprime(p):
 od:
 pfactors := [op(pfactors), p]:
 n_ := n_ / p:
od:
return pfactors;
end:

# Testing

print(`MyIfactor testing for i from 1 to 10000`);
mytime := 0: mapletime := 0:

for i from 1 to 10000 do
 mytime := mytime + time(MyIfactor(i)):
 mapletime := mapletime + time(ifactor(i)):
od:

printf("My time: %f\nMaple time: %f\nMy function takes %f units more of time than Maple's function", mytime, mapletime, mytime - mapletime);