Re: BigInteger enhancing

According to Dmitriy Melnik <mitro.usenet@xxxxxxxxx>:
I've already considered delegating. But my new BigInteger is to be
used heavily. So invoking two methods instead of one could decrease
the speed.

If you are after factorization with quadratic sieve, then you will
probably want to have your own notion of "big integers", plausibly
something mutable instead of the immutable BigInteger. You may want
to look at:
http://www.alpertron.com.ar/ECM.HTM

It features a Java applet which performs such factorization with
elliptic curves, but switching to quadratic sieve for big numbers.
The source code is available; it is quite ugly but it works. The
author apparently used his own code for big integers.

I have not implemented quadratic sieve, but I tried ECM, both with
BigInteger, and with some custom code where big integers are held in
arrays of int. The custom code was about twice faster, mostly because I
could keep the numbers in Montgomery representation, for faster modular
multiplications.


--Thomas Pornin
.

Relevant Pages

  • Re: implementing the quadratic sieve
    ... rossum wrote: ... >>I am trying to write a toy implementation of the quadratic sieve. ... the factorization having the exponent 0, and, voila, f is smooth. ... Call the square root of the product of the prime factors y. ...
    (comp.programming)
  • uRe: implementing the quadratic sieve
    ... > I am trying to write a toy implementation of the quadratic sieve. ... requirement is really only required for optimizing the algorithm. ... of the exponents of the primes in the factor base. ... You should be able to figure out q from the factorization ...
    (comp.programming)
  • Re: BigInteger enhancing
    ... If you are after factorization with quadratic sieve, ... something mutable instead of the immutable BigInteger. ... The custom code was about twice faster, ... public MPInteger add; ...
    (comp.lang.java.programmer)