Re: Elliptic group generators in PARI library

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

On Mon, Apr 02, 2018 at 04:36:07PM +0300, Aleksandr Lenin wrote:
> Hello,
> 
> the functions that search for elliptic group generators,
> ellgenerators(GEN E) and ellff_get_gens(GEN E), work very slowly in the
> case of elliptic curves of cryptographic sizes (i.e., 1600-bit base
> field).

Hello Aleksandr,

Usually elliptic curves used in cryptography have about 256 bit, not 1600bit,
and the cardinal has a single large prime factor, so is easy to factor.

> I think that these functions try to factor the elliptic group
> cardinality, which is infeasible.

Indeed.

> It also seems that these functions do
> not accept the factorization matrix of the elliptic group cardinality as
> the second argument (in case it is known) to speed up calculations. 

Well, there is no second argument!

> Is
> there any other recommended way to search for elliptic group generators
> in elliptic curves over big prime fields?

If the group is cyclic, you can use ellorder():
F=[ellcard(E),factor(ellcard(E))];until(ellorder(E,P,F)==ellcard(E),P=random(E));P

It is also possible to set the factorisation in E directly, but this is
not documented (probably set E[16][4] to F).

In any case, there is a bug: doellgens should use ellff_get_o to get the
factorisation of d1 which is stored in E.

Cheers,
Bill.