[Top][All Lists]

[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.
  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 
  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 
  2. "Proving" is done in the GMP case too. Why is that faster? Is it a weaker 
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).


reply via email to

[Prev in Thread] Current Thread [Next in Thread]