| 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