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 square
OddPwrs: 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