Big integer division efficiency

[Marian Kechlibar]

Dear Paul,

I think we both talk about the same part of the algorithm, but I will
describe it more
details anyway, since you are obviously acquainted with the algorithms.

Our bottleneck is in the situation when you already "almost know for
sure" that
some value of Q(x) is smooth or partially smooth, because enough
logarithms have
aggregated for that x. We even know the precise primes from the factor base
that divide Q(x): they are precisely those primes, for which their
sieving indices
collide with the offset of x within the sieving block. So, currently, I
just walk
through the FB, identify those primes whose sieving indices collide with
the offset
of x, and divide Q(x) with those primes. And it is precisely this
process of division
that is the bottleneck.

Do you think that the algorithm described in the paper you point to
solves this
problem?

(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 :-)

Best regards

Marian Kechlibar


Paul Zimmermann napsal(a):
>        Dear Marian,
>
>   
>> One of the main bottlenecks in our code is a loop that needs to call the
>> function
>>
>> *mpz_fdiv_qr_ui* 
>>
>> very often (more than million times a second).
>>     
>
> I guess your problem lies in the "refactoring" part of MPQS or NFS.
> I suggest you consider alternative methods for factoring out small
> primes in a given integer, for example http://cr.yp.to/papers.html#smoothparts
> and the references herein.
>
> If your car is slow, instead of trying to speed it up, buy a faster one!
>
> Paul Zimmermann
>