Re: Elliptic curve arithmetic in the Montgomery representation

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Sun, Nov 17, 2013 at 09:50:55PM +0000, Richard Heylen wrote:
> I have some calculations I would like to do with points on an elliptic
> curve over a ring without having the benefit of knowing the y
> coordinate. I believe the best way of dealing with this problem is
> using the Montgomery representation which is probably implemented in
> pari at some level due to the presence of ECM factoring routines.

In GP your best bet is to use elliptic curve in short Weierstrass form
and use a formal Y

Somethink like
Y;X; \\ Very important! We want Y to have higher priority than X.
E=ellinit([0,0,0,a,b]);
P=ellmul(E,[X,Mod(Y,Y^2-(X^3+a*X+b))],3);
lift(P[1])

(of course neither a,b and X need to be formal).

Cheers,
Bill.