\\\ base point compututation

sage: prime = 2^252 + 27742317777372353535851937790883648493

sage: A = 346598

sage:  def findBasepoint(prime, A):
F = GF(prime)
E = EllipticCurve(F, [0, A, 0, 1, 0])
for uInt in range(1, 1e3):
u = F(uInt)
v2 = u^3 + A*u^2 + u
if not v2.is_square():
v = v2.sqrt()
point = E(u, v)
pointOrder = point.order()
if pointOrder > 8 and pointOrder.is_prime():
Q=u^3 + A*u^2 + u
return u, Q, sqrt(Q), point

sage: res = findBasepoint(prime, A)

sage: res

(17,

 100171752,

 1014685013428497365422144808165958100622560545891891747637198454693655077041,

 (17 : 1014685013428497365422144808165958100622560545891891747637198454693655077041 : 1))



/// Computation of edwards points in twisted format to produce (X:Y:T:Z) from given X value.
/// Using a manipulated version of the Edwards equation,
/// written below, allows for the computation.
/// a*x^2+y^2 = 1+d*x^2*y^2
/// a = -1, d = -86649/86650
/// In fractions in the mod l need to be `inverse_mod`, calculated for d as below:

sage: p = 2^252 + 27742317777372353535851937790883648493
sage: d = -(86649)/(86650)
sage: d = ((-86649)*inverse_mod(86650,p))%p
sage: d
1201935917638644956968126114584555454358623906841733991436515590915937358637

/// For use in the equation y^2 will be written as y, as sage will attempt to compute the square root.
/// For arbitrarlily chosen x = 23

sage: x = 23
sage: y = (-(x)^2-1)*inverse_mod(d*(x)^2-1,p)%p
sage: y

6536923810004159332831702809452452174451353762940761092345538667656658715568

/// It needs to be checked if the y here is a quadratic residue in p,
/// using the legendre symbol [http://people.bath.ac.uk/masgks/XX10190/legendresymbol.pdf],
/// if confirmed as QR in p, then tonelli-shanks is used to find the corresponing Y coordinates.

sage: legendre_symbol(y,p)
1
sage:         z += 1
....:     c = pow(z, q, p)
....:
....:     # Search for a solution
....:     x = pow(a, (q + 1)/2, p)
....:     t = pow(a, q, p)
....:     m = s
....:     while t != 1:
....:         # Find the lowest i such that t^(2^i) = 1
....:         i, e = 0, 2
....:         for i in xrange(1, m):
....:             if pow(t, e, p) == 1:
....:                 break
....:             e *= 2
....:
....:         # Update next value to iterate
....:         b = pow(c, 2**(m - i - 1), p)
....:         x = (x * b) % p
....:         t = (t * b * b) % p
....:         c = (b * b) % p
....:         m = i
....:
....:     return [x, p-x]
....:
sage: prime_mod_sqrt(y,p)
[5464794816676661649783249706827271879994893912039750480019443499440603127256,
1772210760655600564189936856215722360862222447340157125982507438844851123733]

/// Using formulae from (http://eprint.iacr.org/2008/522), Section 3.1., compute T.
/// Set initial Z = 1

Y = 177221076065560056418993685621572236086222244734015712598250743884485123733
sage: T = (X*Y)%p
sage: T
4575819608417501906502614877746643095545534491924075867587916402004304590914
sage: print X, Y, T, Z
23,
1772210760655600564189936856215722360862222447340157125982507438844851123733,
4575819608417501906502614877746643095545534491924075867587916402004304590914,
 1

///Using formulae from (http://eprint.iacr.org/2008/522), Section 3.1.
/// We can perform addition for twisted edwards on two points computed
/// using the aforementioned method. Addition requires two points, P and Q.

X3 = (X1Y2 + Y1X2)(Z1Z2 − d*T1T2),
Y3 = (Y1Y2 − a*X1X2)(Z1Z2 + d*T1T2),
T3 = (Y1Y2 − a*X1X2)(X1Y2 + Y1X2),
Z3 = (Z1Z2 − d*T1T2)(Z1Z2 + d*T1T2)
///all of the above operations are to be performed in modp

sage: print x1, y1, t1, z1
23,
1772210760655600564189936856215722360862222447340157125982507438844851123733,
4575819608417501906502614877746643095545534491924075867587916402004304590914,
1

sage: print x2, y2, t2, z2
68,
6722994147421810355074918120635103299205518608170642973077643906654710567163,
1232250652750584664783678731478387171976934714669542991156876540536700754777,
1

sage: print a,d  
-1, 1201935917638644956968126114584555454358623906841733991436515590915937358637

sage: print p
7237005577332262213973186563042994240857116359379907606001950938285454250989

sage: x3 = ((x1*y2+y1*x2)*(z1*z2-d*t1*t2))%p
sage: y3 = ((y1*y2-a*x1*x2)*(z1*z2+d*t1*t2))%p
sage: t3 = ((y1*y2-a*x1*x2)*(x1*y2+y1*x2))%p
sage: z3 = ((z1*z2-d*t1*t2)*(z1*z2+d*t1*t2))%p
sage: print x3, y3, t3, z3
5716093817471997596236026932228317319339266616230545169450778020455623314124,
2922311631722687852972831246290075112720003409719168932531360774072286467480,
422634893364951130045115947563923244206657266381713914399200643293129456692,
4564064750933739854564870382990948102627624283547710710613250295960634201043

///Using formulae from (http://eprint.iacr.org/2008/522), Section 3.1.
/// We can perform doubling for twisted edwards on two points computed
/// using the aforementioned method. Doubling requires only one point, P.

X3 = 2X1Y1(2*Z1^2-Y1^2-a*X1^2)
Y3 = (Y1^2+a*X1^2)(Y1^2-a*X1^2)
T3 = 2X1Y1(Y1^2-a*X1^2)
Z3 = (Y1^2+a*X1^2)(2*Z1^2-Y1^2-a*X1^2)

sage: print x1, y1, t1, z1
23,
1772210760655600564189936856215722360862222447340157125982507438844851123733,
4575819608417501906502614877746643095545534491924075867587916402004304590914,
1
sage: print a,d  
-1, 1201935917638644956968126114584555454358623906841733991436515590915937358637
sage: print p
7237005577332262213973186563042994240857116359379907606001950938285454250989
 
 sage: x3 = (2*x1*y1)*(2*z1^2-y1^2-a*x1^2)%p
sage: y3 = (y1^2+a*x1^2)*(y1^2-a*x1^2)%p
sage: t3 = ((2*x1*y1)*(y1^2-a*x1^2))%p
sage: z3 = (y1^2+a*x1^2)*(2*z1^2-y1^2-a*x1^2)%p
sage: print x3, y3, t3, z3
4786833661965518289883133091128976602215197782057516237893206558029211645975,
3718542954294836140733079139795222604215590342980856956446128967840175305597,
5600268135239418985563599817185097446639119887287038611877259326873279017434,
6843363720471380102505544610701588054816158807034229591959761747323798690259



/// For scalar multiplication, where the input is a random chosen
/// scalar - denoted by k. A random point P is computed k times,
/// to achieve a new output. First define constants and algorithm
/// then perform computation and check.

sage: x = 2^252 + 27742317777372353535851937790883648493
sage: F = GF(x)
sage: E = EllipticCurve(F,[0,346598,0,1,0])
sage: def mult(P,k):
....:         if k == 0:
....:              return E(0)
....:          elif k%2 ==1:
....:             return P + mult(P+P,k//2)
....:          else:
....:             return mult(P+P,k//2)
....:    
sage: P = E.random_element();P
(4932580570842190779556137943050936723025546081053585787732570965549340610321 :
995625395479854882233066076699402226516910529515031426749313889481496026045 :
1)
sage: mult(P,8)
(3012434081252490883720793432586906597396722518220480427411338820396043491530 :
5421024907462425194431432698771735833199405480590836541920601262546746110363 :
1)
sage: 8*P
(3012434081252490883720793432586906597396722518220480427411338820396043491530 :
5421024907462425194431432698771735833199405480590836541920601262546746110363 :
1)