mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2016-03-25, 02:05   #1
BenR
 
BenR's Avatar
 
Nov 2014

118 Posts
Default 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
BenR is offline   Reply With Quote
Old 2016-03-25, 15:55   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

Quote:
Originally Posted by BenR View Post
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.
jasonp is offline   Reply With Quote
Old 2016-03-27, 00:37   #3
BenR
 
BenR's Avatar
 
Nov 2014

32 Posts
Default

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.
BenR is offline   Reply With Quote
Reply

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 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

All times are UTC. The time now is 02:08.


Tue Nov 30 02:08:20 UTC 2021 up 129 days, 20:37, 0 users, load averages: 1.00, 0.99, 1.08

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.