[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## 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.
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).
--
Torbjörn