# OK to post

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

# sequences
x:=1,2,3,4,5;
y:=6,7,8,9,10;
x,y;
x:='x';
y:='y';

seq(i^3+i^2+i, i=1..10);

L:=a+b+c;
op(L);
nops(L);

a:={1,2,3,4};
b:={3,4,5,6};
a union b;
a intersect b;
a minus b;
member(2, a);

# tables
T:=table([(2)=A, (4)=B]);
T;

# arrays
A:=array(1..2, 1..2);
A[1,1]:=5;
A;

# functions
f:=(x,y)->(x^2+5*x)/(xy);
g:=x^3+7*x^2;
g:=unapply(g,x);
evalf(f(1,2));

h:=sqrt(x);
(h@g)(x);
(g@h)(x);

# sum/product
Sum(1/i^2, i=1..100);
value(%);

sum(i^3, i=1..n);

Product(i, i=1..10);

# limits
Limit((x^2-4)/(x-2),x=2);

# differentiation
f:=ln(cos(x));
diff(f,x);
diff(f,x$3);

# extrema
maximize(sin(x)*cos(x));
minimize(x^3-x^2+x, {x}, {x=0..3});

# integration
Int(1/x/sqrt(x^2-1), x=1..2/sqrt(3));
value(%);

# PART 2: EXERCISES FROM LECTURE NOTE:
# -----------------------

# problem 16.1 (check eulers thm)
CheckEuler:=proc(a) local n:
    {seq(if gcd(a,n) = 1 then a&^(NumberTheory:-Totient(n)) mod n else 1 fi, n=10..10^3)}; # the if statement just removes non-coprime pairs
end;

CheckEuler(7);
CheckEuler(10); # these all should return the singleton set {1}
CheckEuler(6); 
CheckEuler(123123);

# problem 16.2 (check rsa keys)
CheckRSA:=proc(p, q, e, c) local n, totientN, d, a: # c is the ciphertext msg
    n:=p*q;
    totientN:=(p-1)*(q-1); # since p and q are prime

    # part (i), checking that e is coprime to phi(n):
    if gcd(totientN, e) > 1 then
        return FAIL;
    fi;

    # part (ii), finding d
    d:=e&^(-1) mod totientN;
    print(d);

    # part (iii), checking ciphertext is valid and decrypting it
    if gcd(n, c) > 1 then
        return FAIL;
    fi;

    a:=c&^d mod n;
    print(a);
end;

CheckRSA(3,5,5,11); # same as in lecture notes, should succeed
CheckRSA(ithprime(123),ithprime(1000),112341234,554363456); # unless we are very lucky, should fail
CheckRSA(5161255409, 1581869309, 7095968358397273089, 1442672333133107366); # generated from MakeRSAKey(), should succeed

# PART 3: PRIME FACTORIZATION:
# -----------------------

MyIFactor:=proc(n) local p:
    if n = 1 then
        return [];
    fi;

    p:=2;
    while gcd(n, p) = 1 do 
        p:=nextprime(p);
    od;

    return [p, op(MyIFactor(n / p))];
end;

# it seems overall that foir numbers which are products of large primes, my procedure is much slower than maple's
# maple likely uses a more clever algorithm than my brute-force approach

time(MyIFactor(12));
time(ifactor(12));

time(MyIFactor(100));
time(ifactor(100));

time(MyIFactor(12345678));
time(ifactor(12345678));

time(MyIFactor(10^20));
time(ifactor(10^20));

time(MyIFactor(ithprime(3000)*ithprime(4000)));
time(ifactor(ithprime(3000)*ithprime(4000)));