mersenneforum.org Fast modular reduction for primes < 512 bits?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-03-25, 02:05 #1 BenR     Nov 2014 32 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
2016-03-25, 15:55   #2
jasonp
Tribal Bullet

Oct 2004

1101110110012 Posts

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.

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

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 35 2016-12-11 00:57 Derived Number Theory Discussion Group 24 2016-09-08 11:45 fivemack Computer Science & Computational Number Theory 15 2009-02-19 06:32 goatboy Math 1 2007-12-07 12:30 Dresdenboy Programming 10 2004-02-29 17:27

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

Sun Jul 3 08:45:10 UTC 2022 up 80 days, 6:46, 0 users, load averages: 1.62, 1.52, 1.46

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔