Browse Groups

• ## Re: [PrimeNumbers] Practical question - ECM factoring

(2)
• NextPrevious
• ... 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
View Source
-----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
>
> Jack
>
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)