Re: Suspicious average timing of isprime() (maybe a bug?!)

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Sep 21, 2024 at 11:46:31AM -0700, Ilya Zakharevich wrote:
> THE METHOD: run isprime() on all pseudoprimes in an interval of length
>     	    20M.  Inspect the timing.
> 
> THE RESULT:
> 
> # Start     Time       Checked primes
> 1e19    118.700	  457665

This one make sense.

> 2e19    5323.600        449605
> 4e19    6414.950        443260
> 8e19    8459.400        437461
> 1e20    8443.400        434090
> 2e20    8546.700        427974
> 4e20    8610.000        422382
> 8e20    16720.000       415756
> 1e21    16717.400       414056
> 2e21    17102.800       408566

> 4e21    8673.450        401265
> 8e21    8743.950        396126
> 1e22    8885.250        393752
> 2e22    9042.050        389569
> 4e22    9118.450        384823
> 8e22    9209.950        379336
> 1e23    9168.000        377295
> 2e23    9203.750        372843
> 4e23    14615.250       368239
> 8e23    14644.800       363116

In this range, PARI mostly tries to factor p-1.
There is a difference of a factor 100 between the easiest
and the hardest.
? for(i=1,10000,isprime(1754548210235787604097))
  ***   last result computed in 379 ms.
? for(i=1,10000,isprime(1400469602433071578631))
  ***   last result computed in 29,469 ms.

? for(i=1,10000,factor(1754548210235787604097-1))
  ***   last result computed in 185 ms.
? for(i=1,10000,factor(1400469602433071578631-1))
  ***   last result computed in 2,475 ms.

You can force APRCL to be used with ,2:

? for(i=1,10000,isprime(1754548210235787604097,2))
  ***   last result computed in 28,236 ms.
? for(i=1,10000,isprime(1400469602433071578631,2))
  ***   last result computed in 28,538 ms.

So maybe compute the standard deviation for each batchs ?

Cheers,
Bill.