(* You should be able to copy and paste this text file directly into Mathematica.  These notes will be interpreted as commented code. *)


(* ********* Here are the numbers from the problems ******** *)

problem1aN := 5686741440097
problem1bN := 1032899106233
problem1cN := 1626641013131




(* ******* Here is code for primality testing ******* *)


PollardPminus1IntegerList[B_, a_, n_] := Table[PowerMod[a, k!, n], {k, 1, B}]

(* This will compute the list of a^(k!) mod n, for k up to the bound B *)


PollardPminus1IntegerGCDList[B_, a_, n_] := GCD[n, PollardPminus1IntegerList[B, a, n] - 1]

(* This will compute gcd(a^(k!)-1, n) for k up to the bound B *)


PollardPminus1DivisorFind[B_, a_, n_] := GCD[PowerMod[a, B!, n] - 1, n]

(* This will compute gcd(a^(B!)-1, n): it is the last value used *)


PollardPminus1IntegerGCDList[B_, a_, n_]
PollardPminus1DivisorFind[11, 2, 1242301]

(* This is the example from the notes, and should give the nontrivial divisor 281 at the 10th step *)



PollardRhoXList[B_, a_, n_] := PollardRhoXList[B, a, n] = NestList[Mod[#^2 + 1, n] &, a, B]
PollardRhoYList[B_, a_, n_] := PollardRhoYList[B, a, n] = NestList[Mod[(#^2 + 1)^2 + 1, n] &, a, B]

(* These compute the list of values x_i and y_i = x_2i mod n, for i between 0 and B, where the iterating function is p(x)=x^2+1 *)

PollardRhoGCDList[B_, a_, n_] := GCD[PollardRhoXList[B, a, n] - PollardRhoYList[B, a, n], n]

(* These compute gcd(x_i-y_i, n), again for use in the Pollard rho algorithm *)


PollardRhoFactorFind[B_, a_, n_] := 
 Module[{x = a, y = a, q = 1, i = 0}, While[(q < 2) && (i < B),
   i = i + 1;
   x = Mod[x^2 + 1, n];
   y = Mod[(y^2 + 1)^2 + 1, n];
   q = GCD[n, x - y]];
  q]

(* This will run the Pollard rho algorithm until it either finds a divisor of n that is >1 or iterates B times *)




(* ******* Here are some commands for computing quotients and remainders ******* *)

(7+I) / (3-2I)

(* This will evaluate (7+i) / (3-2i).  Mathematica's notation for i = sqrt(-1) is a capital I *)

N[(7+I) / (3-2I)]

(* The command N will compute a numerical approximation to whatever argument it is given. *)



QuotientRemainder[11,3]

(* This will compute the quotient and remainder when dividing 11 by 3 *)

QuotientRemainder[7+I, 3-2I]

(* This will compute the quotient and remainder when dividing 7+i by 3-2i.  Mathematica will understand to do its arithmetic in Z[i] if you give QuotientRemainder two Gaussian integers *)



PolynomialQuotientRemainder[x^3 - x^2 + 1, x^2 + x, x]

(* This will compute the quotient and remainder when dividing x^3 - x^2 + 1 by x^2 + x, where the variable is x.  The default assumption is that coefficients are rational, real, or complex numbers. *)

PolynomialQuotientRemainder[x^3 - x^2 + 1, x^2 + x, x, Modulus -> 3]

(* This will compute the quotient and remainder upon dividing the first polynomial by the second one, where x is the variable, and the coefficients are considered modulo 3 *)