Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Practical question - ECM factoring

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... Hash: SHA1 Unless I m missing something, any differences between these runs should be based on the speed of the large-integer arithmetic code in GMP and
    Message 1 of 2 , Mar 31, 2003
    • 0 Attachment
      -----BEGIN PGP SIGNED MESSAGE-----
      Hash: SHA1

      Unless I'm missing something, any differences between these runs should be
      based on the speed of the large-integer arithmetic code in GMP and nothing
      else. At first I thought about hitting a threshold where GMP switches between
      basecase multiplication and Karatsuba, but looking at the gmp-mparam.h files,
      it seems the smallest threshold for switching to Karatsuba multiplication is
      512 bits or ~155 digits, so I rule that out. It can probably be regarded as a
      flaw: it's just a piece of code that happens to run faster inside the
      processor for a reason or another. You should try the same experiment on a
      computer with a different CPU and see if you get the same results.

      Asymptotically speaking, performing arithmetic on the two smaller integers is
      supposed to be faster, so this phenomenom is only likely to happen at small
      sizes.

      Décio

      On Monday 31 March 2003 18:26, jbrennen wrote:
      > There was something that I've been wondering about lately,
      > so today I tried it out...
      >
      > I generated four random 25-digit primes, call them A, B, C, and D.
      >
      > The interesting thing I found was that it seems to be faster to
      > run GMP-ECM on the integer A*B*C*D, compared to running GMP-ECM
      > (twice) on the integers A*B and C*D. Not amazingly faster, but
      > just a bit faster: on a 350 MHz P-II, I get 8.600 seconds to
      > run a curve against A*B*C*D (B1=50000), compared to 8.725 seconds
      > (combined) to run against A*B and C*D separately.
      >
      > But on the other hand, multiplying eight random 25-digit primes
      > together, I get a time of 22.195 seconds, so there's no gain to
      > be found at that level.
      >
      > Is this phenomenon known? Does anyone know how far this can be
      > taken? I suppose I'm looking to find the point at which GMP-ECM
      > has the best ratio of elapsed time divided by the log of the
      > input number. Obviously the answer may be dependent on the B1 &
      > B2 bounds for ECM. The result may permit faster factorizations
      > where a whole set of relatively small (< 100 digits) numbers must
      > each be factored.
      >
      > So before I go investigate this further, has anyone been
      > down this road before?
      >
      > Jack
      >
      -----BEGIN PGP SIGNATURE-----
      Version: GnuPG v1.2.1 (GNU/Linux)

      iD8DBQE+iOdbce3VljctsGsRAkusAKCADlEMbpZ2bIm+EcQi5Vd88uYSUwCdEztX
      CkGnE9rDemk2epyh23TLqZw=
      =0LqA
      -----END PGP SIGNATURE-----
    Your message has been successfully submitted and would be delivered to recipients shortly.