Modular Inversion Bottleneck

[Sam Kennedy]

I finally got my MPQS code working, it's much faster than my QS implementation, but it's still pretty slow once the numbers get up to around 70 digits.

I have experimented with smaller blocks which can fit into the CPU cache, as well as one large block, and many large blocks, I've found for my implementation using one large sieve array of around 500k values gives the best performance.

I've profiled my code and the bottleneck is calculating the modular inverse of A mod each prime in the factor base.

I'm using the GMP library's mpz_invert function, would I have any chance of writing a faster function myself?

Are there any optimisations to limit the number of times mpz_invert() is called? (I know SIQS would be one of them, but the MPQS is about as far as I want to go.)

Or is there a way of quickly calculating the inverse?

Thank You

[Prime95]

You can try doing fewer modular inverses.

It is easy to calculate 1/a and 1/b with one modular inversion of a*b.

[fivemack]

Originally Posted by Sam Kennedy

I've profiled my code and the bottleneck is calculating the modular inverse of A mod each prime in the factor base.

I'm using the GMP library's mpz_invert function, would I have any chance of writing a faster function myself?

I expect you will be able to write a faster function yourself because the primes in the factor base are small so you can do everything in 64-bit integers whilst mpz_invert is using bignums.

[jasonp]

The slowness of modular inversion is the reason the fastest QS variant is the self-initializing quadratic sieve; in that case the cost of computing modular inverses is amortized over many changes of polynomial.

[Sam Kennedy]

Originally Posted by fivemack

I expect you will be able to write a faster function yourself because the primes in the factor base are small so you can do everything in 64-bit integers whilst mpz_invert is using bignums.

Would the extended Euclidean algorithm suffice? Or would I have to use something more advanced?