coreutils
[Top][All Lists]

## Re: factor and large prime numbers

 From: Torbjorn Granlund Subject: Re: factor and large prime numbers Date: Mon, 22 Jul 2013 18:14:39 +0200 User-agent: Gnus/5.11 (Gnus v5.11) Emacs/22.3 (berkeley-unix)

```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.

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).

--
Torbjörn

```