#OK to post homework
#Lucy Martinez, 01-24-2024, Assignment 2

with(numtheory):

Help:=proc() :
 print(`MyIfactor(n)`):
end:


# Problem 2: Read and understand this lecture note. 
# Make up similar excercises but with much bigger number, and use Maple as a "calculator"
# Let p=1299709, q=2750159
# Then, using Maple, n=3574406403731, phi(n):=3574402353864
# Let e=346573853 which was found by running
# for i from 346573842 while gcd(phii,i)>1 and i<phii do nextprime(i); od;
# indeed, gcd(e,phii)=1
# now, d=e^(-1) mod phii = 137
# Say we want to encrypt c=65
# Then, we will send message= c&^e mod n = 1564
# The receiver gets 1564 and decodes it:
# originalmessage:=message&^d mod n = 65


# Problem 3, Part 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].
#  [Hint, If n=1 the output is the empty list. Now find the smallest
#  prime divisible by n (by either using nextprime, or ithprime in the
#  numtheory Maple package). Call it p. Then recursively
#  find the output of MyIfactor(n/p), getting some list,
#  and then output a longer list where the first entry is p 
#  followed by the entries of the output of MyIfactor(n/p)]
MyIfactor:=proc(n) local i,p,L:
L:=[]:
if n=1 then 
 return []:
else
 p:=2:
 while p<=n do
  if n mod p = 0 then
   L:=[op(L),p]:
   return [op(L), op(MyIfactor(n/p))]:
  fi:
  p:=nextprime(p):
 od:
fi:
L:
end:

# Problem 3, Part II:
# Test your home-made procedure against Maple ifactor.
# Using the time() command, find out who is better (probably Maple's ifactor), 
# and by how much.

# Answer: time(MyIfactor(899393932939)); outputs 0.031
# meanwhile, 
# time(PrimeFactors(899393932939)); outputs 0.
# Maple's own procedure is faster