20160325, 02:05  #1 
Nov 2014
3^{2} Posts 
Fast modular reduction for primes < 512 bits?
Hi,
I'm working on an implementation of Pollard's Rho for elliptic curves over prime fields. Currently it's using the Barrett Reduction but I'm wondering if there is anything faster for general primes (no special form) in the 128 to 512 bit range? Thanks 
20160325, 15:55  #2  
Tribal Bullet
Oct 2004
2·5^{2}·71 Posts 
Quote:
Otherwise Montgomery multiplication would probably outperform Barrett's method for moduli of these sizes. 

20160327, 00:37  #3 
Nov 2014
11_{8} Posts 
It's actually for any prime, not just the NIST ones :)
I'll look into Montgomery multiplication. The downside is that even the distinguished points would need to be stored in Montgomery form. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Do normal adults give themselves an allowance? (...to fast or not to fast  there is no question!)  jasong  jasong  35  20161211 00:57 
Find Mersenne Primes twice as fast?  Derived  Number Theory Discussion Group  24  20160908 11:45 
Efficient modular reduction with SSE  fivemack  Computer Science & Computational Number Theory  15  20090219 06:32 
Finding primes using modular stacking  goatboy  Math  1  20071207 12:30 
Fast calculations modulo small mersenne primes like M61  Dresdenboy  Programming  10  20040229 17:27 