[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: factor and large prime numbers
From: |
Pádraig Brady |
Subject: |
Re: factor and large prime numbers |
Date: |
Mon, 22 Jul 2013 17:49:11 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130110 Thunderbird/17.0.2 |
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.