mersenneforum.org Modular Inversion Bottleneck
 Register FAQ Search Today's Posts Mark Forums Read

 2013-01-25, 11:41 #1 Sam Kennedy     Oct 2012 1228 Posts Modular Inversion Bottleneck 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
 2013-01-25, 14:30 #2 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 41·193 Posts You can try doing fewer modular inverses. It is easy to calculate 1/a and 1/b with one modular inversion of a*b.
2013-01-25, 15:33   #3
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

33·239 Posts

Quote:
 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.

 2013-01-25, 15:56 #4 jasonp Tribal Bullet     Oct 2004 1101110110012 Posts 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.
2013-01-25, 16:50   #5
Sam Kennedy

Oct 2012

2·41 Posts

Quote:
 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post Dubslow Hardware 5 2017-11-16 19:50 R. Gerbicz Math 1 2015-02-10 10:56 flouran Math 2 2009-05-24 03:15 Numbers Math 27 2005-11-30 15:41 Prime95 Hardware 31 2003-09-17 06:54

All times are UTC. The time now is 16:47.

Tue Jul 5 16:47:07 UTC 2022 up 82 days, 14:48, 1 user, load averages: 2.46, 1.72, 1.43