(* 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 ******** *)

problem1N := 1085444233
problem1a := 277891194
problem1c := 878460400



problem2N := 3189493285075919531948989803351695476743251123
problem2e := 65537
problem2c := 0810123674887735803471951879021843942677716907



problem3NB := 49703407978872135768369150951737194603841663052986938247511157126794635921277619
problem3NC := 48394585785126752760098222942433754518772506574482068079987934034981215730453293
problem3ND := 37048466581842421945081537172098726013070671280095643279361407260434395186752267

problem3cB := 25784565262357725797733361623964330387404886537460006803720876638565346256861433
problem3cC := 08591142161833783340323034144110437060699871009667449419814424711743005011401597
problem3cD := 14041334591568148205935644845370596206044644642402170720554240913633363302351503



problem4N1 := 147451228887363586625323456966525905720989842312760509775958662775459536677624741
problem4N2 := 181724486732607374235034401344439931270145141565372874381350646276632766328969281
problem4N3 := 258424126740178352128100370736889906817607518086806632752038758788555704304604649
problem4N4 := 324234657928347051123113232023409710234012389751239847120398471917665655581200339
problem4N5 := 408869971164328247524265450583823930434406844303142816841351879439544818685702841
problem4N6 := 542408184634943257672698834917404611542248228873337459368210624910406937582942097



problem5N  := 488419441734583556321985415212612123740359939381088965700730231638206554681394177
problem5s2 := 364578471930898294925524638136447727960007605573204140075455802888652544203808336

problem5u12:= 419987940537002829673554859623446087647247049378701209589622515994832674140645748
problem5u22:= 270893145623915322344834242328268768371424519375297223857305039560421032101793802
problem5u32:= 001204179001250513038323769136188667129468312291612708387897338022926559640599640
problem5u42:= 295360259330799676568102779994887111797263481168605647699269117672956353312755331
problem5u52:= 076085193608240660534079611034851894964763400993326547711532912132418924025617595

problem5v1 := 368836285783665928691160226566669484193845816214794656578305054442600293140251910
problem5v2 := 061162076090849776429311938634702834494489117638106960807555056103441302535633013
problem5v3 := 187951496312843107888323763535831510839656637929611417672687000373287147716755997
problem5v4 := 174908257541270590422202403049766598633440061550219493518183063157021792026188460
problem5v5 := 018020803226473941195493125743250937332254656547401271200890367477647082876441426



problem8b  := 843156784620274963828079044664499378320177127026840734436833335222593049312927235387489615873




(* ******* Here is code for decoding a number string ******* *)

NumbersToString[list_] := StringJoin[FromLetterNumber[list + 1]]

NumberStringList[n_] := 
 PadLeft[IntegerDigits[n], 2*Ceiling[Length[IntegerDigits[n]]/2]]

NumberListConvert[list_] := 
 Table[FromDigits[list[[2 i - 1 ;; 2 i]]], {i, 1, Length[list]/2}]

NumberToString2[n_] := 
 NumbersToString[NumberListConvert[NumberStringList[n]]]

(*This will convert an integer into its corresponding letter string,where a=00,b=01,...,z=25*)


NumberToString2[0704111114]

(*This should return the string "hello"*)





(* ******* Here is code for Miller-Rabin ******* *)

v2[n_] := If[IntegerQ[n/2], 1 + v2[n/2], 0]
MillerRabinList[a_, n_] := Table[Mod[1 + PowerMod[a, (n - 1)/2^(v2[n - 1] - k), n], n] - 1, {k, 0, v2[n - 1]}]

(* This function with the helper function above generates the Miller-Rabin list for n with base a.  It also marks -1 as -1 rather than n-1 mod n, to make it easier to identify when -1 shows up on the list. *)

MillerRabinList[2, 561]

(* This is the first Miller-Rabin example from the notes: it should return the list {263, 166, 67, 1, 1}. *)





(* ********* Here are some useful commands for powers mod m ******** *)

Mod[100,6]

(* This will compute 100 modulo 6, yielding 2 *)


PrimeQ[201]

(* This will test whether 201 is prime, which it is not *)


FactorInteger[143]

(* This will factor the integer 143, which is 11 times 13 *)
(* Mathematica's factorization algorithm knows how to do trial division, Pollard p-1, Pollard rho, quadratic sieving, and elliptic curve factorization, and is typically fairly fast on numbers with less than 50 digits *)



largeval := 2^128 + 1

Timing[PrimeQ[largeval]]

Timing[FactorInteger[largeval]]

(* Note that you can also apply functions directly to named variables.  The above allows you to see how much faster primality testing is compared to factorization *)



PowerMod[2, 10, 99]

(* This will compute 2^10 modulo 99.  PowerMod is efficient and will use successive squaring *)
(* Mod will often also recognize if you give it a power and internally call PowerMod, but it is better to use PowerMod directly *)



PowerMod[2, -1, 99]

(* This will compute 2^(-1) modulo 99, which is to say, the multiplicative inverse of 2 modulo 99. *)



EulerPhi[40]

(* This will compute phi(40). *)



ChineseRemainder[{1,2,3},{4,5,9}]

(* This will compute the smallest positive integer solution to x = 1 mod 4, x = 2 mod 5, x = 3 mod 9 *)


CubeRoot[64]

(* This will compute the cube root of 64.  You can also obtain this as 64^(1/3), but fractional powers can sometimes behave unexpectedly because of how Mathematica handles complex numbers. *)




(* ********* Here are some useful other commands ******** *)

GCD[180, 250]

(* This computes the GCD of 180 and 250 *)



ExtendedGCD[180, 250]

(* This performs the extended Euclidean algorithm, and computes the GCD = 10 along with integers {x,y} such that 180x + 250y = 10 *)



PrimitiveRoot[25]

(* This calculates the smallest primitive root modulo 25 *)



MultiplicativeOrder[7, 25]

(* This calculates the order of 7 modulo 25 *)



Solve[x^3 == 1, x, Modulus -> 49]

(* This calculates all of the numbers x satisfying the equation x^3 = 1 modulo 49 *)


Reduce[x^3 == 1, Modulus -> 49]

(* This simplifies the equation x^3 = 1 modulo 49, which here will give a list of all the solutions *)