Juan Luis Varona Malumbres on Tue, 29 Jan 2002 03:10:56 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
A bug with factorint? |
I have the following version of pari (compiled in MacOS X with gcc): GP/PARI CALCULATOR Version 2.1.1 (released) unknown 32-bit version (readline disabled, extended help available) See the following code: // A number with 95 decimal digits:num = 45801029626985382925404507908481835696646386166927151194913778924839351049635266989952015789556;
factorint(num); With (ie, debug=5 an timer on) \g5 #I get the following problem (I abbreviate with ..............................):
Miller-Rabin: testing base 1000288896 IFAC: cracking composite 2245985250729947574851636291387077327663560256121258468591915562897910547539047277367803769 IFAC: checking for pure squareOddPwrs: is 2245985250729947574851636291387077327663560256121258468591915562897910547539047277367803769
...a 3rd, 5th, or 7th power? modulo: resid. (remaining possibilities) 211: 66 (3rd 0, 5th 0, 7th 0) IFAC: trying Pollard-Brent rho method first Rho: searching small factor of 301-bit integer Rho: using X^2+7 for up to 48135 rounds of 32 iterations Rho: time = 5660 ms, 3072 rounds Rho: fast forward phase (1024 rounds of 64)... Rho: time = 2770 ms, 4100 rounds, back to normal mode Rho: time = 1420 ms, 5120 rounds Rho: time = 1490 ms, 6144 rounds .............................. Rho: time = 1520 ms, 46080 rounds Rho: time = 1550 ms, 47104 rounds Rho: time = 1550 ms, 48128 rounds Rho: time = 10 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 38 rounds... ECM: time = 0 ms ECM: dsn = 12, B1 = 1800, B2 = 198000, gss = 128*420 ECM: time = 48550 ms, B1 phase done, p = 1801, setting up for B2 ECM: time = 950 ms, entering B2 phase, p = 2017 ECM: time = 30330 ms ECM: dsn = 14, B1 = 2200, B2 = 242000, gss = 128*420 ECM: time = 57180 ms, B1 phase done, p = 2203, setting up for B2 ECM: time = 840 ms, entering B2 phase, p = 2413 ECM: time = 35890 ms .............................. ECM: dsn = 66, B1 = 540400, B2 = 59444000, gss = 1024*420 ECM: time = 11764820 ms, B1 phase done, p = 540433, setting up for B2 ECM: time = 980 ms, entering B2 phase, p = 540643 ECM: time = 11466770 ms ECM: dsn = 68, B1 = 679500, B2 = 74745000, gss = 1024*420 ECM: time = 14771070 ms, B1 phase done, p = 679501, setting up for B2 ECM: time = 1040 ms, entering B2 phase, p = 679723 ECM: time = 14431410 ms ECM: dsn = 70, B1 = 854100, B2 = 93951000, gss = 1024*420 ECM: time = 18559170 ms, B1 phase done, p = 854111, setting up for B2 ECM: time = 1020 ms, entering B2 phase, p = 854327 ECM: time = 18159360 ms ECM: dsn = 72, B1 = 1073500, B2 = 118085000, gss = 1024*420 ECM: time = 23304890 ms, B1 phase done, p = 1073507, setting up for B2 ECM: time = 1020 ms, entering B2 phase, p = 1073717 ECM: time = 22843530 ms ECM: dsn = 72, B1 = 1073500, B2 = 118085000, gss = 1024*420 ECM: time = 23307740 ms, B1 phase done, p = 1073507, setting up for B2 ECM: time = 1020 ms, entering B2 phase, p = 1073717 ECM: time = 22841520 ms ECM: dsn = 72, B1 = 1073500, B2 = 118085000, gss = 1024*420 ECM: time = 23306030 ms, B1 phase done, p = 1073507, setting up for B2 ECM: time = 1020 ms, entering B2 phase, p = 1073717 ECM: time = 22841090 ms ECM: dsn = 72, B1 = 1073500, B2 = 118085000, gss = 1024*420 ECM: time = 23374350 ms, B1 phase done, p = 1073507, setting up for B2 ECM: time = 960 ms, entering B2 phase, p = 1073717 ....... and it continues in the same way. That is: the eliptic curve method with dsn = 72 appears again and again. We never reach MPQS method.(Moreover, the time for ecm is growing too much, I think. This does not happen
with ubasic, for instance.) Any solution? Yours, Juan L. Varona