/* Quick and dirty implementation of the deterministic point construction algorithm for elliptic curves over finite fields by Christiaan van de Woestijne, Proceedings ANTS VII (Berlin, 2006), LNCS 4076, Springer. Implementation for MAGMA: Christiaan van de Woestijne, July 2006. E-mail author: c.vandewoestijne@tugraz.at. Better version would use the machinery of algebraic geometry in MAGMA to define the surface, the threefold, the maps between them, etc. Also, to one point on the threefold may correspond multiple points on the elliptic curve; one might want to find these, but for this it is necessary to "engineer" the SelectiveRoot routine, or manually construct the required elements using DeterministicTonelliShanks. Functions: ThreefoldPointFinder := function( a, b, c, u, t ) If the elliptic curve is given by y^2 = x^3 + ax^2 + bx + c, over some finite field F, then for ANY CHOICE (well, almost any) of parameters u and t in the base field F the function will construct an F-rational point on the threefold f(x1)f(x2)f(x3) = y^2 (f = x^3 + ax^2 + bx + c) . ThreefoldToCurve := function( P, a, b, c ) If P=[x1,x2,x3,y] is a point on the threefold V given by f(x1)f(x2)f(x3)=y^2 then return some point on the elliptic curve f(x)=y^2. In particular, if either one of the f(x_i)=0, the function returns a 2-torsion point. */ ThreefoldPointFinder := function( a, b, c, u, t ) F := Parent( a ); if Type( F ) ne FldFin then error "Expecting a finite field element"; end if; if Characteristic( F ) lt 5 then // Difficult cases error "Characteristic 2 or 3 not implemented yet"; end if; coef3 := - (u^3 + a*u^2 + b*u + c); if coef3 eq 0 then return [ u, 0 ]; // Two-torsion point end if; coef2 := 3/4*u^2 + 1/2*a*u + b - a^2/4; if coef2 eq 0 then error "Wrong value of u-parameter (quadratic form degenerates)."; end if; // We now consider the quadratic equation z^2 + coef2 y^2 = coef3. basepoint := RepresentationByDiagonalForm( [1,coef2], coef3, 2 ); if basepoint[1]^2 + coef2*basepoint[2]^2 ne coef3 then error "Wrong solution to quadratic form."; end if; /* Now parametrise the rational curve. Let basepoint=(z0,y0); we draw lines through this point, using the slope t as parameter. The general point on such a line is (z0+d,y0+td); substitute this into the equation and solve for d. Get (z0+d)^2 + coef2 (y0+td)^2 = z0^2 + 2dz0 + d^2 + coef2(y0^2+2tdy0+t^2d^2) = z0^2 + coef2 y0^2 + d( 2z0 + d + 2coef2 ty0 + coef2 t^2d ); so we need (1 + coef2 t^2)d + 2z0 + 2coef2 ty0 = 0. */ if coef2*t^2 eq -1 then error "Infinite value encountered"; end if; d := -( 2*basepoint[1] + 2*coef2*t*basepoint[2] ) / ( 1 + coef2*t^2 ); pointoncurve := [ basepoint[1]+d, basepoint[2]+t*d ]; if pointoncurve[1]^2 + coef2*pointoncurve[2]^2 ne coef3 then error "Wrong parametrisation of quadratic form."; end if; if pointoncurve[2] eq 0 then error "Infinite value encountered"; end if; pointonsurface := [ u, pointoncurve[1]/pointoncurve[2] - u/2 - a/2, pointoncurve[2] ]; v := pointonsurface[2]; huv := u^2 + u*v + v^2 + a*(u+v) + b; if pointonsurface[3]^2*huv ne coef3 then error "Point not on surface."; end if; fuy2 := (u+pointonsurface[3]^2)^3 + a*(u+pointonsurface[3]^2)^2 + b*(u+pointonsurface[3]^2) + c; pointonthreefold := [ pointonsurface[2], -a-u-pointonsurface[2], u+pointonsurface[3]^2, coef3 * fuy2 / pointonsurface[3]^3 ]; fv := v^3 + a*v^2 + b*v + c; auv := pointonthreefold[2]; fauv := auv^3 + a*auv^2 + b*auv + c; if fv * fauv * fuy2 ne pointonthreefold[4]^2 then error "Point not on threefold."; end if; // [u,v,y] -> [ v, -a-u-v, u+y^2, -f(u+y^2)f(u)/y^3 ] return pointonthreefold; end function; ThreefoldToCurve := function( P, a, b, c ) // If P=[x1,x2,x3,y] is a point on the threefold V given by // f(x1)f(x2)f(x3)=y^2 // then return some point on the elliptic curve f(x)=y^2. fx1 := P[1]^3 + a*P[1]^2 + b*P[1] + c; fx2 := P[2]^3 + a*P[2]^2 + b*P[2] + c; fx3 := P[3]^3 + a*P[3]^2 + b*P[3] + c; // Cases with 2-torsion points: if fx1 eq 0 then return [ P[1],0 ]; end if; if fx2 eq 0 then return [ P[2],0 ]; end if; if fx3 eq 0 then return [ P[3],0 ]; end if; // Now we know that y ne 0. // if we know that abc=d^2, then can we apply SRE to some numbers? // first guess: a/b, a/c, d^2/bc // second guess: a,ab,abc // sqrt(a/(ab))= sqrt(1/b), happy. // sqrt(a/(abc))=sqrt(1/(bc))=sqrt(a/d^2), happy. // sqrt(ab/(abc))=sqrt(1/c), happy. i,j,rt := SelectiveRoot( [fx1*fx2*fx3,fx1*fx2,fx1], 2 ); if [i,j] eq [1,2] then // sqrt of fx3 found return [ P[3],rt ]; else if [i,j] eq [2,3] then // sqrt of fx2 found return [ P[2],rt ]; else // [i,j] eq [1,3], sqrt of fx2*fx3 found // rt^2 = fx2*fx3 = y^2/fx1, so fx1 = (y/rt)^2 return [ P[1],P[4]/rt ]; end if; end if; end function; /* F := FiniteField( 10061 ); Fabc := RationalFunctionField( F, 3 ); Fx := PolynomialRing( Fabc ); f := xx^3 + a*xx^2 + b*xx + c; FourSpace := AffineSpace( Fabc, 4 ); drievoud := Scheme( FourSpace, Evaluate( f,x1 )*Evaluate( f, x2 ) * Evaluate( f, x3 ) - y^2; SS3 := SingularSubscheme( drievoud ); Dimension( SS3 ); // 1 ThreeSpace := AffineSpace( Fabc, 3); h := u^2+u*v+v^2+a*(u+v)+b; oppervlak := Scheme( ThreeSpace, yy^2*h+Evaluate( f,u) ); mp := map< oppervlak -> threefold | [ v,-a-u-v,u+yy^2,Evaluate(f,u)* Evaluate(f,u+yy^2)*(-1)/yy^3 ] >; */