Editing Elliptic-curve cryptography (section)

=== Fast reduction (NIST curves) ===
Reduction modulo ''p'' (which is needed for addition and multiplication) can be executed much faster if the prime ''p'' is a [[pseudo-Mersenne prime]], that is <math>p \approx 2^d</math>; for example, <math>p = 2^{521} - 1</math> or <math>p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1.</math> Compared to [[Barrett reduction]], there can be an order of magnitude speed-up.<ref>{{Cite book |first1=M. |last1=Brown |first2=D. |last2=Hankerson |first3=J. |last3=Lopez |first4=A. |last4=Menezes  |title=Topics in Cryptology — CT-RSA 2001 |chapter=Software Implementation of the NIST Elliptic Curves over Prime Fields |series=Lecture Notes in Computer Science |year=2001 |volume=2020 |pages=250–265 |doi=10.1007/3-540-45353-9_19 |isbn=978-3-540-41898-6 |url=http://cr.yp.to/bib/2000/brown-prime.ps |citeseerx=10.1.1.25.8619 }}</ref> The speed-up here is a practical rather than theoretical one, and derives from the fact that the moduli of numbers against numbers near powers of two can be performed efficiently by computers operating on binary numbers with [[bitwise operation]]s.

The curves over <math>\mathbb{F}_p</math> with pseudo-Mersenne ''p'' are recommended by NIST. Yet another advantage of the NIST curves is that they use ''a''&nbsp;=&nbsp;−3, which improves addition in Jacobian coordinates.

According to Bernstein and Lange, many of the efficiency-related decisions in NIST FIPS 186-2 are suboptimal. Other curves are more secure and run just as fast.<ref>{{ cite web | author = Daniel J. Bernstein | author2 = Tanja Lange|author2-link=Tanja Lange | name-list-style = amp | title = SafeCurves: choosing safe curves for elliptic-curve cryptography | url = https://safecurves.cr.yp.to/ | access-date = 1 December 2013 }}</ref>