Handin.sagews

p=2^(255)-19 in Primes() #is the number a prime
p

True

F=GF(2^(255)-19) # defines the Galois field with 2^255-19 elements
F

Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949

E=EllipticCurve(F,[0,486662,0,1,0]) # defines the elliptic curve over F - generalized Weierstrass form.
E

Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949

Mod(486664,2^(255)-19).sqrt() # test if A+2 is a quadratic residue, it is if this number is in F_p

9094040566125962849133224048217411091405536248825867518642941381412595940312

P1=E(1,9094040566125962849133224048217411091405536248825867518642941381412595940312)
P2=E(1,-9094040566125962849133224048217411091405536248825867518642941381412595940312) # define the two points which according to vi) c) has order 4
P1;P2
order(P1);order(P2) # check the order is 4

(1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1) (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1) 4 4

orderEM=E.cardinality() # how many points are there on EM
orderEM

57896044618658097711785492504343953926856930875039260848015607506283634007912

orderEM-(2^(255)-19+1) # Hasse-Weil bound compares number of points with 1+ field size
(2*sqrt(2^(255)-19)).round() # compare with the bound

221938542218978828286815502327069187962 481231938336009023090067544955250113854

factor(orderEM) # prime factorisation of #E^M(F_p) to see that there is a large subgroup of prime order.

2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989

P = E.random_point()
Q = E.random_point()
P;Q
order(P);order(Q);order(P+4*Q);order(Q+Q)

(3980255909486115729431466238470315465222264283140390663751037068344245345630 : 11062312781006242602762520426901860549635235664461905989851208966366327992943 : 1) (23842649423595861491870653913225174276031479381479696611264446902319377649849 : 9869974301589369240218079883962905431845537763993462502116669071610231112607 : 1) 28948022309329048855892746252171976963428465437519630424007803753141817003956 57896044618658097711785492504343953926856930875039260848015607506283634007912 28948022309329048855892746252171976963428465437519630424007803753141817003956 28948022309329048855892746252171976963428465437519630424007803753141817003956

E=EllipticCurve([0,0,0,0,1])
E
P=E(0,1)
P
2*P
3*P
Ep = plot(E);
show(Ep);

(25777294156659235732199671163573219621458032847619334937999053569633511275360 : 24662337916705369239682235634342474749920240120407655801057743698250868055487 : 1) (31994311698234441291142477153218505866352581953004396035988389752939827157801 : 37425202978014804301746966719410724182340300401175464346042313303031565682116 : 1) 7237005577332262213973186563042994240857116359379907606001950938285454250989 57896044618658097711785492504343953926856930875039260848015607506283634007912 57896044618658097711785492504343953926856930875039260848015607506283634007912 Elliptic Curve defined by y^2 = x^3 + 1 over Rational Field (0 : 1 : 1) (0 : -1 : 1) (0 : 1 : 0)