PARI/GP Bug report logs - #2469
regression in factor() in pari 2.15.3

Display info messages

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

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

Package: pari-stable
Version: 2.15.3

Calling factor() on a large prime leads to a hang. With 2.13.4, the
following completes almost instantly:

$ echo "factor(2^2203-1)" | gp -qf

[... output omitted ...]

With pari 2.15.3 and 2.15.2, it keeps running seemingly forever, >10
minutes for sure.


This is apparently fixed as a by-product of 
 > 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

but this is not a good idea to simply apply this, as Bill says.

---
Best,
Dima

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

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

On Tue, Mar 28, 2023 at 03:36:03PM +0100, dima.pasechnik@cs.ox.ac.uk wrote:
> Package: pari-stable
> Version: 2.15.3
> 
> Calling factor() on a large prime leads to a hang. With 2.13.4, the
> following completes almost instantly:
> 
> $ echo "factor(2^2203-1)" | gp -qf
> 
> [... output omitted ...]
> 
> With pari 2.15.3 and 2.15.2, it keeps running seemingly forever, >10
> minutes for sure.
> 
> This is apparently fixed as a by-product of 
>  > 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

Also the first bad commit is 

commit 22373e45d14f6e4848567569f559f2c6f39913f2 (HEAD, refs/bisect/bad)
Author: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
Date:   Sun Jun 13 18:56:36 2021 +0200

    ifactor_sign: fix tuning parameters for avoiding ispsp test

so what happens is probably that ifactor_sign does not detect that the number is prime.

Cheers,
Bill.

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

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

On Wed, Mar 29, 2023 at 12:00:37PM +0200, Bill Allombert wrote:
> On Tue, Mar 28, 2023 at 03:36:03PM +0100, dima.pasechnik@cs.ox.ac.uk wrote:
> > Package: pari-stable
> > Version: 2.15.3
> > 
> > Calling factor() on a large prime leads to a hang. With 2.13.4, the
> > following completes almost instantly:
> > 
> > $ echo "factor(2^2203-1)" | gp -qf
> > 
> > [... output omitted ...]
> > 
> > With pari 2.15.3 and 2.15.2, it keeps running seemingly forever, >10
> > minutes for sure.
> > 
> > This is apparently fixed as a by-product of 
> >  > 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
> 
> Also the first bad commit is 
> 
> commit 22373e45d14f6e4848567569f559f2c6f39913f2 (HEAD, refs/bisect/bad)
> Author: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
> Date:   Sun Jun 13 18:56:36 2021 +0200
> 
>     ifactor_sign: fix tuning parameters for avoiding ispsp test
> 
> so what happens is probably that ifactor_sign does not detect that the number is prime.

I join a patch, which I hope is correct. This is difficult to test.

Cheers,
Bill.

[patch (text/plain, attachment)]

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

On Mon, Apr 03, 2023 at 02:13:23PM +0200, Bill Allombert wrote:
> I join a patch, which I hope is correct. This is difficult to test.

Dear Dima,

I have made a snapshot of pari 2.15.4 available that should be released in two
weeks:
https://pari.math.u-bordeaux.fr/pub/pari/snapshots/pari-2.15.4-pre1.tar.gz

Could you test that it works with sagemath ?

Cheers,
Bill

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

On Tue, Jun 27, 2023 at 09:16:26PM +0200, Bill Allombert wrote:
> On Mon, Apr 03, 2023 at 02:13:23PM +0200, Bill Allombert wrote:
> > I join a patch, which I hope is correct. This is difficult to test.
> 
> Dear Dima,
> 
> I have made a snapshot of pari 2.15.4 available that should be released in two
> weeks:
> https://pari.math.u-bordeaux.fr/pub/pari/snapshots/pari-2.15.4-pre1.tar.gz
> 
> Could you test that it works with sagemath ?

I have released 2.15.4 so I close this bug report.
Thanks for reporting this bug!

Cheers,
Bill

Send a report that this bug log contains spam.