d_log.magma

// Discrete logarithm for points at infinity
load "utils.magma";

function d_log(P, Q, E, p)
	n := 0;
	S := mul(P, n, E); // Guess point
	i := 0;

	Pi := P; // p^0P
	while S ne Q do 
		assert Pi ne [0,1,0];
		mi := Degree(TrailingTerm(Pi[1]));
		dff := add(mul(S, -1, E), Q, E);
		
		cD := Coefficient(dff[1], mi);
		cPi := Coefficient(Pi[1], mi);
		bi := Integers()!( cD * cPi^-1 ); // Get bi
		
		// Update sums
		n +:= bi * (p^i);
		S := add(S, mul(Pi, bi, E), E);
		
		i +:= 1;
		Pi := mul(Pi, p, E);
	end while;

	return n;

end function;



for p in [2..11] do
	if not IsPrime(p) then continue; end if;
	printf "p: %o... ",p; 
	// Define the parameters: R_k = F_{p^e}[X]/<X^k>
	k := p^2+2; e := 2; 
	// Construct R_k
	q := p^e;

	Fq<gamma> := GF(q); // gamma is the primitive element of Fq
	F<eps> := PolynomialRing(Fq);
	I := ideal<F | eps^k>;
	Rk<eps> := F/I;
	
	for crv in [1..10] do // 10 random curves
		E := RandomCurve(Rk); 
		
		for pnt in [1..30] do // 30 random points for each curve
			// Points over O
			P := [Rk | 0, 1, 0];
			while P eq [0,1,0] do
				P := RandomLift(P, E, k);
			end while;
			
			// Check order of p
			ordp := 1;
			nP := P;
			while nP ne [0,1,0] do 
				nP := mul(nP, p, E);
				ordp *:= p;
			end while;

			n := Random([1..ordp-1]);
			Q := mul(P, n, E);

			// Now discrete log
			dlog := d_log(P, Q, E, p);
			
			assert dlog eq n; 
		end for;
	end for;
	printf "ok\n";

end for;