Re: factor and large prime numbers

[Pádraig Brady]

On 07/22/2013 05:14 PM, Torbjorn Granlund wrote:
> Pádraig Brady <address@hidden> writes:
> 
>   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.
>   
> I dont think this is related to the use of GMP for the larger number.

Oh right of course.  If I force GMP with the smaller number,
we get a longer time:

$ time factor 8683317618811886495518194401279999999
8683317618811886495518194401279999999: 8683317618811886495518194401279999999
real    5m51.967s

>   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?
>   
> The time difference is due to the time to (recursively) factor n-1 for
> each assumed prime number n and assumed prime factor n.  For the slower
> number above, n-1 has two huge factors (of 61 and 62 bits each).

Right 8683317618811886495518194401279999998 is the issue here specifically.
Using that in isolation with the older factor takes an even longer time:

$ time factor-8.10 8683317618811886495518194401279999998
8683317618811886495518194401279999998: 2 1570143494597312303 2765135049341098033
real    6m36.754s

thanks for the clarifications,
Pádraig.