Closed GiacomoPope closed 11 months ago
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]
Just to keep this updated with Pari, 2.15.3 is the latest stable release and the bug still remains.
git bisect
says this was fixed in ea6992e38d.
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?
it's ok to use the upstream patch as is
Reported upstream https://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=2469
Waiting for a proper fix before proceeding with #35302
Upstream patch is now available.
Is there an existing issue for this?
Did you read the documentation and troubleshoot guide?
Environment
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 asMod(2, p).sqrt()
orZmod(p)(2).sqrt()
, as they rely onfactor()
under the hood. Note that it does not affectGF(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:
If we set the verbosity to be high we get the following (truncated) output
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()
: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.