Why does factorint() take 128ms for 1853 decimal digit prime, while isprime() takes 16:45min/2min cpu/real time?
[email protected] Mon, 23 Feb 2026 22:25:54 +0100
| Newsgroups | gmane.comp.mathematics.pari.user |
|---|---|
| Message-ID | <[email protected]> |
Gist 3710.gp
https://gist.github.com/Hermann-SW/ffc3d818a2867e9e40bdeeedc022bfea sets
3710 decimal digits Carmichael number N=P*Q*R for primes P, Q and R.
Why does isprime(R) take so much longer than factorint(R), which
identifies R as squarefree and having single prime factor, which means R
is prime?
hermann@7950x:~$ gp -q 3710.gp
? #
timer = 1 (on)
? F=factorint(R);
cpu time = 128 ms, real time = 128 ms.
? #digits(R)
1853
? isprime(R)
cpu time = 16min, 44,590 ms, real time = 1min, 59,408 ms.
1
? #F~[,1]
1
? #F[1,2]
1
? F[1,1]==R
1
? isprime(Q)
cpu time = 79 ms, real time = 79 ms.
1
? isprime(P)
cpu time = 79 ms, real time = 79 ms.
1
? kronecker(5,N)
-1
? N==P*Q*R
1
? lift(Mod(5,N)^(N-1))
cpu time = 223 ms, real time = 223 ms.
1
?
Regards,
Hermann.