Re: factor and large prime numbers

[Torbjorn Granlund]

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