Big integer division efficiency

[Marian Kechlibar]

Hi Alexander,

this is a copy of my message that somehow ended out of the thread.
I also added some comment regarding 2-large variation.

1. Thank you.

2. Yes. Not now, but in the future. And here are the reasons why:
@
    2.1   The last time that SIQS was used to achieve a factoring record
was,
I believe, in 1994. That time, MPQS with a single-large variation was used,
and the factored number had about 440 bits.

             Since then, MPQS has significant development (SIQS), and some
extra improvements like Carrier-Wagstaff method for generating better
leading coefficients, but no one tried them on a really big number.
Also, double-large prime variation could prove important in such setting.
It seems that it is the most effective in the realm of 120+ decimal numbers.

    2.2   I believe that we can setup reasonably sized network of at least
1000 machines with much higher computation power than back in 1994.
We are working on a decent implementation of distributed sieving for that
purpose.

    2.3   This is not a university-funded project, though it is developed by
the university. Our investor would definitely like to see the highest
possible
number factored. If 512 bits is infeasible, what about 480 ...

Finally, I believe that by developing MPQS/SIQS as fast as possible,
we can ease the work of people who need to factor numbers about 90-100
digits large.

Best regards

Marian Kechlibar


Alexander Kruppa napsal(a):
> Marian Kechlibar wrote:
>
>
>> (Anyway, this is not the *only* bottleneck in the program. We are
>> already quite
>> fast, for example faster than Scott Contini's implementation of SIQS.
>> But we are
>> still not "the fastest on Earth". And we need to be, if we wish to break
>> a 512-bit
>> modulus in reasonable time with SIQS :-)
>
>
> 1. You really want to look into "resieving".
>
> 2. Are you really trying to factor a 512 bit number with SIQS?
>
> Alex