PARI/GP Bug report logs - #2441
ellgroup() crashes with "impossible inverse" error

Toggle useless messages

Message #5 received at submit@pari.math.u-bordeaux.fr (full text, mbox, reply):

Package: pari
Version: 2.15.1

Example:
  z = ffgen(41^16);
  E = ellinit([z,z]);
  ellgroup(E);

Result:
  ***   at top-level: ellgroup(E)
  ***                 ^-----------
  *** ellgroup: impossible inverse in Fl_inv: Mod(31, 31).

This was discovered by a random test in Sage:
  https://trac.sagemath.org/ticket/34537#comment:145

Message #10 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Mon, Jan 09, 2023 at 11:01:09PM +0800, Lorenz Panny wrote:
> Package: pari
> Version: 2.15.1
> 
> Example:
>   z = ffgen(41^16);
>   E = ellinit([z,z]);
>   ellgroup(E);
> 
> Result:
>   ***   at top-level: ellgroup(E)
>   ***                 ^-----------
>   *** ellgroup: impossible inverse in Fl_inv: Mod(31, 31).

Hello Lorenz,

Thanks for reporting this bug.

The first bad commit is this one:

commit 05f58ba657ab931d412b005ae72ea221f337f2aa (refs/bisect/bad)
Author: Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>
Date:   Mon Oct 3 22:03:20 2016 +0200

    ellsea: Use BMSS algorithm for isogeny kernel.

There are several ways to fix this.

Cheers,
Bill

Message #15 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

Hello,
without a patch for this, we cannot proceed with getting Pari 2.15 into
Sage.

Best,
Dima

Message #20 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

[Message part 1 (text/plain, inline)]

On Sat, Jan 14, 2023 at 03:04:06PM +0000, dima.pasechnik@cs.ox.ac.uk wrote:
> Hello,
> without a patch for this, we cannot proceed with getting Pari 2.15 into
> Sage.

Well, you can change the test. the bug happens very rarely. 
If you really want a patch now, here is one.

Cheers,
Bill.

[patch (text/plain, attachment)]

Message #25 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

[Message part 1 (text/plain, inline)]

On Mon, Jan 09, 2023 at 11:33:42PM +0100, Bill Allombert wrote:
> On Mon, Jan 09, 2023 at 11:01:09PM +0800, Lorenz Panny wrote:
> > Package: pari
> > Version: 2.15.1
> > 
> > Example:
> >   z = ffgen(41^16);
> >   E = ellinit([z,z]);
> >   ellgroup(E);
> > 
> > Result:
> >   ***   at top-level: ellgroup(E)
> >   ***                 ^-----------
> >   *** ellgroup: impossible inverse in Fl_inv: Mod(31, 31).
> 
> Hello Lorenz,
> 
> Thanks for reporting this bug.
> 
> The first bad commit is this one:
> 
> commit 05f58ba657ab931d412b005ae72ea221f337f2aa (refs/bisect/bad)
> Author: Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>
> Date:   Mon Oct 3 22:03:20 2016 +0200
> 
>     ellsea: Use BMSS algorithm for isogeny kernel.
> 
> There are several ways to fix this.

This bug is very strange. This comes from the use of Atkin-type modular equations,
whose leads to extra j-invariants to be considered. There is a pseudoprobalistic 
test to remove the wrong j-invariant, which hs a small chance to fail.
In this example I would expect it naïvely to fail with probability 41^-16. 
However the test fails actually 4 time in a row on this example (so we are at 41^-64)
and further I found a lot of non-isomorphic curves triggering the same bug.

However what is strange is that it only seems to occur with fields of characteristic 41
and only with level 31 Atkin-type modular equation.

Anyway, I join a new patch that should be better than the previous one.

Cheers,
Bill.

[patch (text/plain, attachment)]

Message #30 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Thu, Jan 19, 2023 at 11:35:14PM +0100, Bill Allombert wrote:
> Anyway, I join a new patch that should be better than the previous one.
It what sense it's "better" ? In the sense that the previous patch
does not do the job? Or it's just an efficiency issue?

Dima

Message #35 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

reassign 2441 pari-stable
quit
On Tue, Jan 24, 2023 at 12:52:46PM +0000, dima.pasechnik@cs.ox.ac.uk wrote:
> On Thu, Jan 19, 2023 at 11:35:14PM +0100, Bill Allombert wrote:
> > Anyway, I join a new patch that should be better than the previous one.
> It what sense it's "better" ? In the sense that the previous patch
> does not do the job? Or it's just an efficiency issue?

The thing is, I did not know at the time, but after doing lots of tests, now I know!

The previous patch fixes this example but not other similar ones.

The new patch should fix all instances of this bug, is much simpler and sounder
but introduce a minor slowdown that seems to be below noise level in practice,
so probably below 1%.

I applied the patch to the GIT master branch. I will backport it to pari 2.15.3 at
some point. 

Cheers,
Bill.

Message #44 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Tue, Jan 24, 2023 at 02:30:44PM +0100, Bill Allombert wrote:
> reassign 2441 pari-stable
> quit
> On Tue, Jan 24, 2023 at 12:52:46PM +0000, dima.pasechnik@cs.ox.ac.uk wrote:
> > On Thu, Jan 19, 2023 at 11:35:14PM +0100, Bill Allombert wrote:
> > > Anyway, I join a new patch that should be better than the previous one.
> > It what sense it's "better" ? In the sense that the previous patch
> > does not do the job? Or it's just an efficiency issue?
> 
> The thing is, I did not know at the time, but after doing lots of tests, now I know!
> 
> The previous patch fixes this example but not other similar ones.
as far as I can see, the change you committed:
https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=commitdiff;h=6f556664be
does not add any tests except the one in this issue (although I might be
wrong)

What extra tests would you recommend?

Dima

Message #49 received at 2441@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Fri, Jan 27, 2023 at 11:55:25AM +0000, Dmitrii Pasechnik wrote:
> On Tue, Jan 24, 2023 at 02:30:44PM +0100, Bill Allombert wrote:
> > reassign 2441 pari-stable
> > quit
> > On Tue, Jan 24, 2023 at 12:52:46PM +0000, dima.pasechnik@cs.ox.ac.uk wrote:
> > > On Thu, Jan 19, 2023 at 11:35:14PM +0100, Bill Allombert wrote:
> > > > Anyway, I join a new patch that should be better than the previous one.
> > > It what sense it's "better" ? In the sense that the previous patch
> > > does not do the job? Or it's just an efficiency issue?
> > 
> > The thing is, I did not know at the time, but after doing lots of tests, now I know!
> > 
> > The previous patch fixes this example but not other similar ones.
> as far as I can see, the change you committed:
> https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=commitdiff;h=6f556664be
> does not add any tests except the one in this issue (although I might be
> wrong)
> 
> What extra tests would you recommend?

Try other curves with the same field, I guess.

This one for example
z=ffgen([41,13]); E = ellinit([z^28]);ellcard(E)

It depends what you want to achieve.

Cheers,
Bill

Message #54 received at 2441-done@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Fri, Jan 27, 2023 at 11:55:25AM +0000, Dmitrii Pasechnik wrote:
> On Tue, Jan 24, 2023 at 02:30:44PM +0100, Bill Allombert wrote:
> > reassign 2441 pari-stable
> > quit
> > On Tue, Jan 24, 2023 at 12:52:46PM +0000, dima.pasechnik@cs.ox.ac.uk wrote:
> > > On Thu, Jan 19, 2023 at 11:35:14PM +0100, Bill Allombert wrote:
> > > > Anyway, I join a new patch that should be better than the previous one.
> > > It what sense it's "better" ? In the sense that the previous patch
> > > does not do the job? Or it's just an efficiency issue?
> > 
> > The thing is, I did not know at the time, but after doing lots of tests, now I know!
> > 
> > The previous patch fixes this example but not other similar ones.
> as far as I can see, the change you committed:
> https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=commitdiff;h=6f556664be

PARI 2.15.3 has been released with a fix for this bug, so I close this report.

Thanks for reporting this issue!
Cheers,
Bill

Message #55 received at 2441-done@pari.math.u-bordeaux.fr (full text, mbox, reply):

Hi Bill,

it seems that you make releases without taking all the bug fixes you
have, so this one we'll need to patch (with your patch from Nov 2022),
just as well.  Namely, with

> From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
> Date: Wed, 16 Nov 2022 13:33:21 +0100
> Subject: [PATCH] Keep product of prime numbers to use in Z_factor_limit

That's a bit unfortunate.

Cheers,
Dima


On Tue, Mar 14, 2023 at 10:40:46PM +0100, Bill Allombert wrote:
> On Fri, Jan 27, 2023 at 11:55:25AM +0000, Dmitrii Pasechnik wrote:
> > On Tue, Jan 24, 2023 at 02:30:44PM +0100, Bill Allombert wrote:
> > > reassign 2441 pari-stable
> > > quit
> > > On Tue, Jan 24, 2023 at 12:52:46PM +0000, dima.pasechnik@cs.ox.ac.uk wrote:
> > > > On Thu, Jan 19, 2023 at 11:35:14PM +0100, Bill Allombert wrote:
> > > > > Anyway, I join a new patch that should be better than the previous one.
> > > > It what sense it's "better" ? In the sense that the previous patch
> > > > does not do the job? Or it's just an efficiency issue?
> > > 
> > > The thing is, I did not know at the time, but after doing lots of tests, now I know!
> > > 
> > > The previous patch fixes this example but not other similar ones.
> > as far as I can see, the change you committed:
> > https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=commitdiff;h=6f556664be
> 
> PARI 2.15.3 has been released with a fix for this bug, so I close this report.
> 
> Thanks for reporting this issue!
> Cheers,
> Bill

Message #56 received at 2441-done@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Tue, Mar 28, 2023 at 12:19:23PM +0100, Dmitrii Pasechnik wrote:
> Hi Bill,
> 
> it seems that you make releases without taking all the bug fixes you
> have, so this one we'll need to patch (with your patch from Nov 2022),
> just as well.  Namely, with
> 
> > From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
> > Date: Wed, 16 Nov 2022 13:33:21 +0100
> > Subject: [PATCH] Keep product of prime numbers to use in Z_factor_limit
> 
> That's a bit unfortunate.

Not at all, this patch is for the development branch only, I will not backport it
to 2.15. It is not a bug fix and it changes the ABI and the interface. 
Also, alone, it introduces subtle bugs that are fixed by subsequent commits.

I am not sure why you feel a need to apply it.

In any case, I plan to do a release 2.15.4 once I am confident 2.15.3 did not
introduce regressions.

Cheers,
Bill.

Message #57 received at 2441-done@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Tue, Mar 28, 2023 at 02:00:19PM +0200, Bill Allombert wrote:
> On Tue, Mar 28, 2023 at 12:19:23PM +0100, Dmitrii Pasechnik wrote:
> > Hi Bill,
> > 
> > it seems that you make releases without taking all the bug fixes you
> > have, so this one we'll need to patch (with your patch from Nov 2022),
> > just as well.  Namely, with
> > 
> > > From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
> > > Date: Wed, 16 Nov 2022 13:33:21 +0100
> > > Subject: [PATCH] Keep product of prime numbers to use in Z_factor_limit
> > 
> > That's a bit unfortunate.
> 
> Not at all, this patch is for the development branch only, I will not backport it
> to 2.15. It is not a bug fix and it changes the ABI and the interface. 

The regression I am referring to is that factor() started to hang while trying
to factorise biggish primes, e.g. on Pari 2.15.3 

   factor(2^2203-1)

hangs (well, it doesn't return anything for 10 minutes of wall-clock
time, while occupying 100% of one CPU), while on 2.13.4 it almost instantly returns the factorisation
(well, the only factor).

The patch in question is fixing this.

Do you think this ought to be fixed in 2.15?

Best,
Dima

> Also, alone, it introduces subtle bugs that are fixed by subsequent commits.
> 
> I am not sure why you feel a need to apply it.
> 
> In any case, I plan to do a release 2.15.4 once I am confident 2.15.3 did not
> introduce regressions.
> 
> Cheers,
> Bill.

Message #58 received at 2441-done@pari.math.u-bordeaux.fr (full text, mbox, reply):

On Tue, Mar 28, 2023 at 02:06:10PM +0100, Dmitrii Pasechnik wrote:
> On Tue, Mar 28, 2023 at 02:00:19PM +0200, Bill Allombert wrote:
> > On Tue, Mar 28, 2023 at 12:19:23PM +0100, Dmitrii Pasechnik wrote:
> > > Hi Bill,
> > > 
> > > it seems that you make releases without taking all the bug fixes you
> > > have, so this one we'll need to patch (with your patch from Nov 2022),
> > > just as well.  Namely, with
> > > 
> > > > From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
> > > > Date: Wed, 16 Nov 2022 13:33:21 +0100
> > > > Subject: [PATCH] Keep product of prime numbers to use in Z_factor_limit
> > > 
> > > That's a bit unfortunate.
> > 
> > Not at all, this patch is for the development branch only, I will not backport it
> > to 2.15. It is not a bug fix and it changes the ABI and the interface. 
> 
> The regression I am referring to is that factor() started to hang while trying
> to factorise biggish primes, e.g. on Pari 2.15.3 
> 
>    factor(2^2203-1)
> 
> hangs (well, it doesn't return anything for 10 minutes of wall-clock
> time, while occupying 100% of one CPU), while on 2.13.4 it almost instantly returns the factorisation
> (well, the only factor).

Well, could you open a new bug for this issue ?

Cheers,
Bill

Message #59 received at 2441-done@pari.math.u-bordeaux.fr (full text, mbox, reply):

[Message part 1 (text/plain, inline)]

On Tue, Mar 28, 2023 at 03:38:03PM +0200, Bill Allombert wrote:
> On Tue, Mar 28, 2023 at 02:06:10PM +0100, Dmitrii Pasechnik wrote:
> > On Tue, Mar 28, 2023 at 02:00:19PM +0200, Bill Allombert wrote:
> > > On Tue, Mar 28, 2023 at 12:19:23PM +0100, Dmitrii Pasechnik wrote:
> > > > Hi Bill,
> > > > 
> > > > it seems that you make releases without taking all the bug fixes you
> > > > have, so this one we'll need to patch (with your patch from Nov 2022),
> > > > just as well.  Namely, with
> > > > 
> > > > > From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
> > > > > Date: Wed, 16 Nov 2022 13:33:21 +0100
> > > > > Subject: [PATCH] Keep product of prime numbers to use in Z_factor_limit
> > > > 
> > > > That's a bit unfortunate.
> > > 
> > > Not at all, this patch is for the development branch only, I will not backport it
> > > to 2.15. It is not a bug fix and it changes the ABI and the interface. 
> > 
> > The regression I am referring to is that factor() started to hang while trying
> > to factorise biggish primes, e.g. on Pari 2.15.3 
> > 
> >    factor(2^2203-1)
> > 
> > hangs (well, it doesn't return anything for 10 minutes of wall-clock
> > time, while occupying 100% of one CPU), while on 2.13.4 it almost instantly returns the factorisation
> > (well, the only factor).
> 
> Well, could you open a new bug for this issue ?
OK, will do.
> 
> Cheers,
> Bill

[signature.asc (application/pgp-signature, inline)]

Send a report that this bug log contains spam.