Failure to handle large prime input with Pari's factor()

[GiacomoPope]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**: MacOS
- **Sage Version**: Version 9.8

Steps To Reproduce

When working with large primes, Pari no longer seems to properly handle factor(large_prime) and hangs indefinitely. This affects other functionality such as Mod(2, p).sqrt() or Zmod(p)(2).sqrt(), as they rely on factor() under the hood. Note that it does not affect GF(p)(2).sqrt(), as Sage already knows the modulus is prime in this case.

For example, defining a large prime and attempting to factor it hangs:

sage: p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
sage: %timeit p.is_prime()
12.4 s ± 477 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit p.is_prime(proof=False)
8.71 ms ± 166 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %time factor(p, proof=False)

If we set the verbosity to be high we get the following (truncated) output

sage: %time factor(p, proof=False, verbose=8)
IFAC: cracking composite
	30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
IFAC: checking for pure square
OddPwrs: examining 2048-bit integer

OddPwrs: not a power
IFAC: trying Pollard-Brent rho method
Rho: searching small factor of 2048-bit integer
Rho: using X^2+1 for up to 49152 rounds of 32 iterations
Rho: time =   3278 ms,	24576 rounds
Rho: fast forward phase (8192 rounds of 64)...
Rho: time =   1480 ms,	32772 rounds, back to normal mode
Rho: time =    852 ms,	40960 rounds
Rho: time =    872 ms,	Pollard-Brent giving up.
IFAC: trying Shanks' SQUFOF, will fail silently if input
      is too large for it.
IFAC: trying Lenstra-Montgomery ECM
ECM: working on 64 curves at a time; initializing for up to 912 rounds...
ECM: time =      0 ms
ECM: B1 = 1800,	B2 = 198000,	gss =  128*420
ECM: time =   2996 ms, B1 phase done, p = 1801, setting up for B2
	(got [2]Q...[10]Q)
	(got [p]Q, p = 1811 = prc210_rp[29] mod 210)
	(got initial helix)
ECM: time =     55 ms, entering B2 phase, p = 2017
ECM: finishing curves 60...63
#
# TRUNCATED
#

Note, if we supply an integer which is composite with a very large prime factor, Pari seems to work as expected, so the issue may be that there is no primality check at the beginning of the Pari function factor():

sage: %time factor(2 * p, proof=False)
CPU times: user 20.7 ms, sys: 87 µs, total: 20.7 ms
Wall time: 20.7 ms
2 * 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

Expected Behavior

For prime input to be tested for primality before applying various factoring algorithms

Actual Behavior

Pari seems to attempt to factor the large integer without checking first that the input is prime and hangs indefinitely as no factors of the prime will be found

Additional Information

SageMath 9.8 included the ticket #34537, which upgraded PARI to version 2.15.2. Potentially, the factoring error was introduced in this new version.

[GiacomoPope]

Running the same factoring using gp, I find that for version 2.13.3, factoring works as intended. For GP/Pari 2.15.2 factoring 2*p works, but hangs indefinitely for factor(p). For 2.16.0, the bug seems to have been removed.

The only fix for SageMath is to either update to 2.16.0 o or rollback to the previously supported version

Output example for 2.13.3

                                                        GP/PARI CALCULATOR Version (released)
                                                amd64 running linux (x86-64/GMP-6.2.1 kernel) 64-bit version
                                            compiled: Oct 25 2021, gcc version 11.2.0 (Ubuntu 11.2.0-10ubuntu1)
                                                                 threading engine: pthread
                                                       (readline v8.1 enabled, extended help enabled)

                                                           Copyright (C) 2000-2020 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?17 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000, nbthreads = 16
? p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
%1 = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
? #
   timer = 1 (on)
? factor(2*p)
cpu time = 31 ms, real time = 26 ms.
%2 =
[2 1]

[30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161 1]

? factor(p)
cpu time = 16 ms, real time = 23 ms.
%3 =
[30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161 1]

[GiacomoPope]

Just to keep this updated with Pari, 2.15.3 is the latest stable release and the bug still remains.

[yyyyx4]

git bisect says this was fixed in ea6992e38d.

[yyyyx4]

Cherry-picking the commit mentioned above on top of 2.15.3 merges cleanly, and it seems to fix the issue — but we should probably try to find a more minimal patch?

[dimpase]

it's ok to use the upstream patch as is

[dimpase]

Reported upstream https://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=2469

Waiting for a proper fix before proceeding with #35302

[yyyyx4]

Upstream patch is now available.