#OK to post homework #Joseph Koutsoutis, 04-07-2024, Assignment 21 read `C21.txt`: #1 done #2 done #3 RandPt := proc(a,b,p) local x,y,ra: ra := rand(0..p-1): x := ra(): y := SqrtF(x^3 + a*x + b,p,1000): while y = FAIL do: x := ra(): y := SqrtF(x^3 + a*x + b,p,1000): od: [x,y]: end: #4 AliceToBobEC := proc(a,b,p,g) local A: A := rand(1..p-1)(): [A, Mul(g,A,a,b,p)]: end: BobToAliceEC := proc(a,b,p,g) local B: B := rand(1..p-1)(): [B, Mul(g,B,a,b,p)]: end: # TestSameKey checks that Alice and Bob end up with the same key by generating # K random points on the curve y^2=x^3+a*x+b mod p and confirming that ABg=BAg. TestSameKey := proc(a,b,p,K) local i,g,Alice,Bob,ABg,BAg: for i from 1 to K do: g := RandPt(a,b,p): Alice := AliceToBobEC(a,b,p,g): Bob := BobToAliceEC(a,b,p,g): ABg := Mul(Bob[2],Alice[1],a,b,p): BAg := Mul(Alice[2],Bob[1],a,b,p): if ABg <> BAg then return(FAIL): fi: od: return(SUCCESS): end: #5 Hasse := proc(a,b,K) local N,k,p,minimal_points,minimal_set,maximal_points,maximal_set: p := 3: N := nops(EC(a,b,p)): k := evalf((N - (p+1)) / sqrt(p)): minimal_points := k: maximal_points := k: minimal_set := {p}: maximal_set := {p}: while nextprime(p) <= K do: p := nextprime(p): N := nops(EC(a,b,p)): k := evalf((N - (p+1)) / sqrt(p)): if k = minimal_points then: minimal_set := minimal_set union {p}: elif k < minimal_points then: minimal_points := k: minimal_set := {p}: elif k = maximal_points then: maximal_set := maximal_set union {p}: elif k > maximal_points then: maximal_points := k: maximal_set := {p}: fi: od: minimal_points,minimal_set,maximal_points,maximal_set: end: # Now we run Hasse(a,b,500) for 1<=a<=10. RunHasse := proc() local a,b,minimal_points,minimal_set,maximal_points,maximal_set: for a from 1 to 10 do: for b from 1 to 10 do: minimal_points,minimal_set,maximal_points,maximal_set := Hasse(a,b,500): print(`#`, a, b, minimal_points, minimal_set, maximal_points, maximal_set): od: od: end: # Here is our table of the outputs of RunHasse() # a b minimal_points minimal_set maximal_points, maximal_set # 1, 1, -1.857175758, {167}, 1.958151124, {163} # 1, 2, -1.835325871, {19}, 1.777565025, {457} # 1, 3, -1.676687158, {461}, 1.966156610, {149} # 1, 4, -1.857175758, {167}, 1.729994960, {281} # 1, 5, -1.965365346, {233}, 1.681992660, {433} # 1, 6, -1.830395593, {431}, 1.912649431, {79} # 1, 7, -1.928425889, {409}, 1.858425272, {227} # 1, 8, -1.956702650, {251}, 1.907996184, {89} # 1, 9, -1.896244889, {47}, 1.943861565, {271} # 1, 10, -1.940482496, {307}, 1.796053021, {31} # 2, 1, -1.664100588, {13}, 1.883115891, {271} # 2, 2, -1.900457352, {443}, 1.862985731, {461} # 2, 3, -1.952184321, {127}, 1.898850653, {71} # 2, 4, -1.811169436, {239}, 1.911541889, {263} # 2, 5, -1.954127875, {419}, 1.876629726, {23} # 2, 6, -1.907165331, {397}, 1.774713019, {127} # 2, 7, -1.948515994, {487}, 1.747408113, {131} # 2, 8, -1.868809013, {331}, 1.797624545, {337} # 2, 9, -1.902202554, {283}, 1.953092302, {151} # 2, 10, -1.951074435, {269}, 1.792052941, {227} # 3, 1, -1.876629726, {23}, 1.940482496, {307} # 3, 2, -1.797754210, {401}, 1.879586847, {137} # 3, 3, -1.977872706, {409}, 1.881293974, {191} # 3, 4, -1.849195789, {379}, 1.956135018, {461} # 3, 5, -1.966156610, {149}, 1.896244889, {47} # 3, 6, -1.789649958, {281}, 1.769263451, {307} # 3, 7, -1.941983636, {223}, 1.847229349, {359} # 3, 8, -1.676687158, {461}, 1.908959956, {281} # 3, 9, -1.769836444, {461}, 1.970658557, {103} # 3, 10, -1.881441736, {113}, 1.788854382, {5} # 4, 1, -1.927880584, {293}, 1.898850653, {71} # 4, 2, -1.883409481, {307}, 1.839514069, {383} # 4, 3, -1.879586847, {137}, 1.792516319, {61} # 4, 4, -1.876629726, {23}, 1.747408113, {131} # 4, 5, -1.875018684, {223}, 1.802310226, {149} # 4, 6, -1.872125629, {103}, 1.852423300, {197} # 4, 7, -1.969710516, {499}, 1.881441736, {113} # 4, 8, -1.958151124, {163}, 1.808936514, {191} # 4, 9, -1.916086663, {353}, 1.809068067, {11} # 4, 10, -1.852006680, {421}, 1.982455801, {229} # 5, 1, -1.931384279, {367}, 1.953092302, {151} # 5, 2, -1.793844223, {179}, 1.941709295, {383} # 5, 3, -1.736579053, {191}, 1.890570661, {101} # 5, 4, -1.917899106, {457}, 1.940482496, {307} # 5, 5, -1.792516319, {61}, 1.835325871, {19} # 5, 6, -1.850292082, {229}, 1.915408523, {157} # 5, 7, -1.875018684, {223}, 1.868587732, {179} # 5, 8, -1.868054217, {241}, 1.668115313, {23} # 5, 9, -1.835412072, {499}, 1.832541665, {67} # 5, 10, -1.984867374, {199}, 1.871348584, {257} # 6, 1, -1.835412072, {499}, 1.824686211, {173} # 6, 2, -1.822644754, { 59}, 1.824686211, {173} # 6, 3, -1.881441736, {113}, 1.871520952, {193} # 6, 4, -1.947567060, {401}, 1.829532253, {409} # 6, 5, -1.907165331, {397}, 1.884233418, {149} # 6, 6, -1.871520952, {193}, 1.975756680, {83} # 6, 7, -1.857175758, {167}, 1.693297563, {113} # 6, 8, -1.824686211, {173}, 1.940538682, {239} # 6, 9, -1.931384279, {367}, 1.932564780, {181} # 6, 10, -1.780172487, {71}, 1.876629726, {23} # 7, 1, -1.757848729, {311}, 1.954127875, {419} # 7, 2, -1.835325871, {19}, 1.774713019, {127} # 7, 3, -1.883115891, {271}, 1.889822365, {7} # 7, 4, -1.889822365, {7}, 1.829982844, {43} # 7, 5, -1.788854382, {5}, 1.871520952, {193} # 7, 6, -1.929157714, {97}, 1.829982844, {43} # 7, 7, -1.933472978, {107}, 1.923047895, {53} # 7, 8, -1.941709295, {383}, 1.849879248, {263} # 7, 9, -1.850292082, {229}, 1.835412072, {499} # 7, 10, -1.965022613, {137}, 1.919028982, {479} # 8, 1, -1.718128361, {229}, 1.982102548, {449} # 8, 2, -1.852945919, {443}, 1.969710516, {499} # 8, 3, -1.943861565, {271}, 1.710411617, {443} # 8, 4, -1.780172487, {71}, 1.907996184, {89} # 8, 5, -1.912649431, {79}, 1.950834538, {139} # 8, 6, -1.876629726, {23}, 1.811169436, {239} # 8, 7, -1.932564780, {181}, 1.852098016, {337} # 8, 8, -1.850304098, {491}, 1.883115891, {271} # 8, 9, -1.871121079, {457}, 1.874085142, {41} # 8, 10, -1.781196752, {139}, 1.941709295, {383} # 9, 1, -1.834340989, {233}, 1.953092302, {151} # 9, 2, -1.952184321, {127}, 1.803638554, {241} # 9, 3, -1.849195789, {379}, 1.700878869, {271} # 9, 4, -1.943331240, {179}, 1.932581258, {347} # 9, 5, -1.824686211, {173}, 1.871520952, {193} # 9, 6, -1.756599647, {397}, 1.970334259, {433} # 9, 7, -1.809068067, {11}, 1.879586847, {137} # 9, 8, -1.905431591, {463}, 1.874085142, {41} # 9, 9, -1.623279550, {137}, 1.796053021, {31} # 9, 10, -1.878979071, {409}, 1.926732203, {431} #10, 1, -1.824686211, {173}, 1.879586847, {137} #10, 2, -1.984867374, {199}, 1.881441736, {113} #10, 3, -1.907996184, {89}, 1.829132283, {269} #10, 4, -1.927963122, {311}, 1.921793624, {313} #10, 5, -1.781955484, {479}, 1.952833664, {59} #10, 6, -1.822644754, {59}, 1.671258044, {29} #10, 7, -1.915652570, {109}, 1.895433466, {491} #10, 8, -1.927599495, {211}, 1.856953382, {29} #10, 9, -1.949480715, {421}, 1.947567060, {401} #10, 10, -1.793844223, {179}, 1.656897194, {373} #6 RepeatedSquaringHelper := proc(p,a,n) local x,y,omega,b,d,pow,S: x := a: y := 1: pow := (p+1)/2: S := 1: #S is the number of bits in pow while 2^(S+1) - 1 < pow do: S += 1: od: while S <> 0 do: if MmaTranslator[Mma]:-BitAnd(2^(S-1), pow) = 0 then: x,y := (x^2+y^2 * (a^2-n)) mod p, ((x+y)^2 - x^2 - y^2) mod p: else: d := (x + y*a) mod p: b := n*y mod p: x,y := (a*d^2 - b*(x+d)) mod p, d^2 - b*y mod p: fi: S -= 1: od: x: end: SqrtF := proc(n,p,K) local a,i,ra,x,j: ra:=rand(1..p-1): if n&^((p-1)/2) mod p=p-1 then RETURN(FAIL): fi: for i from 1 to K do a:=ra(): if (a^2-n mod p)&^((p-1)/2) mod p=p-1 then: return(RepeatedSquaringHelper(p,a,n)): fi: od: FAIL: end: # TestSqrtF creates K random primes with d digits and chooses a random # n from 1 to p-1 and checks to see if SqrtF(n,p,100) outputs a value whose # square is n. We also print out the fraction of values that did not have a square. TestSqrtF := proc(d,K) local i,ra,p,n,x,cnt: ra := rand(10^(d-1)..10^d-1): cnt := 0: for i from 1 to K do: p := nextprime(ra()): n := rand(1..p-1)(): x := SqrtF(n,p,100): if x <> FAIL and x^2 mod p <> n then return(FAIL): fi: if x = FAIL then cnt += 1: fi: od: print(cnt/K): SUCCESS: end: # I did a little testing and my implementation of SqrtF is slower than NumberTheory:-ModularSquareRoot