mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Fast modular reduction for primes < 512 bits? (https://www.mersenneforum.org/showthread.php?t=21144)

BenR 2016-03-25 02:05

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

jasonp 2016-03-25 15:55

[QUOTE=BenR;430006]
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?
[/QUOTE]
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.


All times are UTC. The time now is 13:52.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.