// Purpose: Example of the use of SLPs.mag
// Author: Pierrick Gaudry

load "SLPs.mag";

//**** Build a random discrete log problem over a prime field
p := NextPrime(10^50);
a := Random(GF(p));
b := Random(GF(p));
E := EllipticCurve([a,b]);
P := Random(E);
n := Order(P);  // takes some time to compute (SEA algorithm)
lambda := Random(1,n);
Q := lambda*P;

//**** Lift if to p-adics
prec := 20;   // the wanted precision
K := pAdicField(p, prec);
A := K!a; B := K!b;  // arbitrary lift of E to K
xP := K!P[1];
k := 1;
while k lt prec do
  xP := xP - SLPDivisionPolynomial(A, B, xP, n) /
    SLPDiffXDivisionPolynomial(A, B, xP, n);
  k := 2*k;
end while;
yP := SquareRoot(xP^3 + A*xP + B);
if Valuation(yP - K!P[2]) ne 1 then
  yP := -yP;
end if;
	
xQ := K!Q[1];
k := 1;
while k lt prec do
  xQ := xQ - SLPDivisionPolynomial(A, B, xQ, n) /
    SLPDiffXDivisionPolynomial(A, B, xQ, n);
  k := 2*k;
end while;
yQ := SquareRoot(xQ^3 + A*xQ + B);
if Valuation(yQ - K!Q[2]) ne 1 then
  yQ := -yQ;
end if;
	    
//**** Here (xP:yP:1) and (xQ:yQ:1) are points of order n on the lifted curve
//**** and are the second is lambda times the first.
//****
//**** Unfortunately, the group law does not work on non-exact fields in
//**** Magma, so to do the checking, one should use hand-made group formulae.