Re: factor and large prime numbers

[Pádraig Brady]

On 07/22/2013 04:01 PM, Sami Kerola wrote:
> Hello,
> 
> I were curious how quickly factor will process prime numbers, and
> found something rather strange. For example these five can be computed
> quite quickly.
> 
> time factor 10333147966386144929666651337523199999999
> time factor 371993326789901217467999448150835199999999
> time factor 13763753091226345046315979581580902399999999
> time factor 523022617466601111760007224100074291199999999
> time factor 20397882081197443358640281739902897356799999999
> 
> But much smaller numbers will take ages to give results (to be honest
> I gave up).
> 
> time factor 8683317618811886495518194401279999999
> time factor 295232799039604140847618609643519999999
> 
> Any idea what is going on?

Quantifying...

$ time factor-8.10 10333147966386144929666651337523199999999
10333147966386144929666651337523199999999: 37 71 
3933440413546305645095794190149676437
real    0m0.014s
$ time factor-8.10 8683317618811886495518194401279999999
8683317618811886495518194401279999999: 8683317618811886495518194401279999999
real    0m0.006s

$ time factor-8.21 10333147966386144929666651337523199999999
10333147966386144929666651337523199999999: 37 71 
3933440413546305645095794190149676437
real    0m0.356s
$ time factor-8.21 8683317618811886495518194401279999999
8683317618811886495518194401279999999: 8683317618811886495518194401279999999
real    1m44.693s

So the new factor is slower in both cases.
The difference between the two numbers in factor-8.21
is due to different code paths (GMP and not).
Note GMP is unexpectedly faster in this case.

Now I previously asked about slowdowns in the new factor code.
http://lists.gnu.org/archive/html/coreutils/2012-10/msg00030.html
There it was mentioned that factor now enables prime proving by default.
This sometimes takes a lot of time as it needs to factor p-1 for
each factor p found.  Each factor of p-1 is also proven prime, recursively.

If I compile with "prime proving" disabled we get:

$ time factor 10333147966386144929666651337523199999999
10333147966386144929666651337523199999999: 37 71 
3933440413546305645095794190149676437
real    0m0.004s
$ time factor 8683317618811886495518194401279999999
8683317618811886495518194401279999999: 8683317618811886495518194401279999999
real    0m0.004s

So nice and fast.

So I have questions too at this stage.

1. I get that prime proving takes longer, though is the above 1m44s 
reasonable/expected?
2. "Proving" is done in the GMP case too. Why is that faster? Is it a weaker 
check?

thanks,
Pádraig.