Re: Why does factorint() take 128ms for 1853 decimal digit prime, while isprime() takes 16:45min/2min cpu/real time?

[Aurel Page <aurel.page@normalesup.org>]

Dear Hermann,

That is because by default, factor does not prove that the factors are 
prime. They are only guaranteed to be pseudoprimes.

? p = randomprime(10^300);
? ispseudoprime(p);
cpu time = 6 ms, real time = 6 ms.
? factor(p);
cpu time = 8 ms, real time = 11 ms.
? isprime(p)
cpu time = 2,414 ms, real time = 1,124 ms.

You can use default(factor_proven, 1) to change this behaviour.

Best,
Aurel

On 2/23/26 22:25, hermann@stamm-wilbrandt.de wrote:
> 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.