Bill Allombert on Wed, 11 Apr 2018 11:25:54 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Elliptic group generators in PARI library


On Mon, Apr 02, 2018 at 05:56:36PM +0200, Bill Allombert wrote:
> 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

Another way would be to use addprimes.
If F is the list of large primes factors of the order, you can do
addprimes(F);
before the computation to let PARI know about the factors.

Cheers,
Bill.