Fast modular reduction for primes < 512 bits?

BenR · 2016-03-25, 02:05

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

jasonp · 2016-03-25, 15:55

Quote:

Originally Posted by BenR

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?

If this is intended for elliptic curve discrete logs for the NIST elliptic curves, those primes do have special forms for which custom code may or may not run faster than general modular reduction.

Otherwise Montgomery multiplication would probably outperform Barrett's method for moduli of these sizes.

BenR · 2016-03-27, 00:37

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.

2016-03-25, 02:05	#1
BenR Nov 2014 9₁₀ 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

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	2016-12-11 00:57
Find Mersenne Primes twice as fast?	Derived	Number Theory Discussion Group	24	2016-09-08 11:45
Efficient modular reduction with SSE	fivemack	Computer Science & Computational Number Theory	15	2009-02-19 06:32
Finding primes using modular stacking	goatboy	Math	1	2007-12-07 12:30
Fast calculations modulo small mersenne primes like M61	Dresdenboy	Programming	10	2004-02-29 17:27

2016-03-27, 00:37	#3
BenR Nov 2014 3² 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.