Elliptic curve point multiplication

Point operations

There are three commonly defined operations for elliptic curve points: addition, doubling and negation.

Point at infinity

Point at infinity ⁠${\displaystyle \mathcal{O}}$⁠ is the identity element of elliptic curve arithmetic. Adding it to any point results in that other point, including adding point at infinity to itself. That is:

${\displaystyle \begin{array}{c}\mathcal{O}+\mathcal{O}=\mathcal{O}\\ \mathcal{O}+P=P\end{array}}$

Point at infinity is also written as 0.

Point negation

Point negation is finding such a point, that adding it to the given point will result in point at infinity (⁠${\displaystyle \mathcal{O}}$⁠).

${\displaystyle \begin{array}{c}P+(-P)=\mathcal{O}\end{array}}$

For elliptic curves of the form E: y² = x³ + ax + b, negation is a point with the same x coordinate but negated y coordinate:

${\displaystyle \begin{array}{cc}(x,y)+(-(x,y))& =\mathcal{O}\\ (x,y)+(x,-y)& =\mathcal{O}\\ (x,-y)& =-(x,y)\end{array}}$

Point addition

With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R.

${\displaystyle \begin{array}{cc}P+Q& =R\\ (x_p,y_p)+(x_q,y_q)& =(x_r,y_r)\end{array}}$

Assuming the elliptic curve, E, is given by y² = x³ + ax + b, this can be calculated as:

${\displaystyle \begin{array}{cc}\lambda & =\frac{y_q-y_p}{x_q-x_p}\\ x_r& ={\lambda }^2-x_p-x_q\\ y_r& =\lambda (x_p-x_r)-y_p\end{array}}$

These equations are correct when neither point is the point at infinity, ⁠${\displaystyle \mathcal{O}}$⁠, and if the points have different x coordinates (they're not mutual inverses). This is important for the ECDSA verification algorithm where the hash value could be zero.

Point doubling

Where the points P and Q are coincident (at the same coordinates), addition is similar, except that there is no well-defined straight line through P, so the operation is closed using a limiting case, the tangent to the curve, E, at P.

This is calculated as above, taking derivatives (dE/dx)/(dE/dy):

${\displaystyle \lambda =\frac{3x_p^2+a}{2y_p}}$

where a is from the defining equation of the curve, E, above.

Point multiplication

The straightforward way of computing a point multiplication is through repeated addition. However, there are more efficient approaches to computing the multiplication.

Double-and-add

The simplest method is the double-and-add method, similar to square-and-multiply in modular exponentiation. The algorithm works as follows:

To compute sP, start with the binary representation for s: ⁠${\displaystyle s=s_0+2s_1+2^2{s}_2+\cdots +2^{n-1}{s}_{n-1}}$⁠, where ⁠${\displaystyle s_0..s_{n-1}\in \{0,1\},n=\lceil {\log }_{2}s\rceil }$⁠.

• Iterative algorithm, index increasing:

<b id="mwfg">let</b> bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s <b id="mwfw">let</b> res = <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt32" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\begin{align}\\mathcal{O}\\end{align}"}}' id="mwgA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\begin{aligned}{\mathcal {O}}\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">O</mi> </mrow> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\mathcal {O}}\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4a2f16235398da00ab404883a89b261bf8b55b56" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.601ex; height:2.843ex;" alt="{\displaystyle {\begin{aligned}{\mathcal {O}}\end{aligned}}}"/></span> # point at infinity <b id="mwgQ">let</b> temp = P # track doubled P val <b id="mwgg">for</b> bit <b id="mwgw">in</b> bits: <b id="mwhA">if</b> bit == 1: res = res + temp # point add temp = temp + temp # double <b id="mwhQ">return</b> res

• Iterative algorithm, index decreasing:

<b id="mwiQ">let</b> bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s <b id="mwig">let</b> i = length(bits) - 2 <b id="mwiw">let</b> res = P <b id="mwjA">while</b> (i >= 0): # traversing from second MSB to LSB res = res + res # double <b id="mwjQ">if</b> bits[i] == 1: res = res + P # add i = i - 1 <b id="mwjg">return</b> res

Note that both of the iterative methods above are vulnerable to timing analysis. See Montgomery Ladder below for an alternative approach.

• Recursive algorithm:

<b id="mwkw">algorithm</b> f(P, d) <b id="mwlA">is</b> <b id="mwlQ">if</b> d = 0 <b id="mwlg">then</b> <b id="mwlw">return</b> 0 # computation complete <b id="mwmA">else if</b> d = 1 <b id="mwmQ">then</b> <b id="mwmg">return</b> P <b id="mwmw">else if</b> d mod 2 = 1 <b id="mwnA">then</b> <b id="mwnQ">return</b> point_add(P, f(P, d - 1)) # addition when d is odd <b id="mwng">else</b> <b id="mwnw">return</b> f(point_double(P), d / 2) # doubling when d is even

where f is the function for multiplying, P is the coordinate to multiply, d is the number of times to add the coordinate to itself. Example: 100P can be written as 2(2[P + 2(2[2(P + 2P)])]) and thus requires six point double operations and two point addition operations. 100P would be equal to f(P, 100).

This algorithm requires log₂(d) iterations of point doubling and addition to compute the full point multiplication. There are many variations of this algorithm such as using a window, sliding window, NAF, NAF-w, vector chains, and Montgomery ladder.

Windowed method

In the windowed version of this algorithm, one selects a window size w and computes all ${\displaystyle 2^w}$ values of ${\displaystyle dP}$ for ${\displaystyle d=0,1,2,\dots ,2^w-1}$. The algorithm now uses the representation ${\displaystyle d=d_0+2^w{d}_1+2^{2w}{d}_2+\cdots +2^{mw}{d}_m}$ and becomes

Q ← 0 <b id="mwuA">for</b> i from m to 0 <b id="mwuQ">do</b> Q ← point_double_repeat(Q, w) <b id="mwug">if</b> d<sub id="mwuw">i</sub> <span typeof="mw:Entity" id="mwvA">></span> 0 <b id="mwvQ">then</b> Q ← point_add(Q, d<sub id="mwvg">i</sub>P) # using pre-computed value of d<sub id="mwvw">i</sub>P <b id="mwwA">return</b> Q

This algorithm has the same complexity as the double-and-add approach with the benefit of using fewer point additions (which in practice are slower than doubling). Typically, the value of w is chosen to be fairly small making the pre-computation stage a trivial component of the algorithm. For the NIST recommended curves, ${\displaystyle w=4}$ is usually the best selection. The entire complexity for a n-bit number is measured as ${\displaystyle n+1}$ point doubles and ${\displaystyle 2^w-2+\frac{n}{w}}$ point additions.

Sliding-window method

In the sliding-window version, we look to trade off point additions for point doubles. We compute a similar table as in the windowed version except we only compute the points ${\displaystyle dP}$ for ${\displaystyle d=2^{w-1},2^{w-1}+1,\dots ,2^w-1}$. Effectively, we are only computing the values for which the most significant bit of the window is set. The algorithm then uses the original double-and-add representation of ${\displaystyle d=d_0+2d_1+2^2{d}_2+\cdots +2^m{d}_m}$.

Q ← 0 <b id="mwzg">for</b> i from m downto 0 <b id="mwzw">do</b> <b id="mw0A">if</b> d<sub id="mw0Q">i</sub> = 0 <b id="mw0g">then</b> Q ← point_double(Q) <b id="mw0w">else</b> t ← extract j (up to w − 1) additional bits from d (including d<sub id="mw1A">i</sub>) i ← i − j <b id="mw1Q">if</b> j < w <b id="mw1g">then</b> Perform double-and-add using t <b id="mw1w">return</b> Q <b id="mw2A">else</b> Q ← point_double_repeat(Q, w) Q ← point_add(Q, tP) <b id="mw2Q">return</b> Q

This algorithm has the benefit that the pre-computation stage is roughly half as complex as the normal windowed method while also trading slower point additions for point doublings. In effect, there is little reason to use the windowed method over this approach, except that the former can be implemented in constant time. The algorithm requires ${\displaystyle w-1+n}$ point doubles and at most ${\displaystyle 2^{w-1}-1+\frac{n}{w}}$ point additions.

w-ary non-adjacent form (wNAF) method

In the non-adjacent form we aim to make use of the fact that point subtraction is just as easy as point addition to perform fewer (of either) as compared to a sliding-window method. The NAF of the multiplicand ${\displaystyle d}$ must be computed first with the following algorithm

i ← 0 <b id="mw5A">while</b> (d <span typeof="mw:Entity" id="mw5Q">></span> 0) <b id="mw5g">do</b> <b id="mw5w">if</b> (d mod 2) = 1 <b id="mw6A">then</b> d<sub id="mw6Q">i</sub> ← d mods 2<sup id="mw6g">w</sup> d ← d − d<sub id="mw6w">i</sub> <b id="mw7A">else</b> d<sub id="mw7Q">i</sub> = 0 d ← d/2 i ← i + 1 <b id="mw7g">return</b> (d<sub id="mw7w">i−1</sub>, d<sub id="mw8A">i-2</sub>, ..., d<sub id="mw8Q">0</sub>)

Where the signed modulo function mods is defined as

<b id="mw9Q">if</b> (d mod 2<sup id="mw9g">w</sup>) <span typeof="mw:Entity" id="mw9w">></span>= 2<sup id="mw-A">w−1</sup> <b id="mw-Q">return</b> (d mod 2<sup id="mw-g">w</sup>) − 2<sup id="mw-w">w</sup> <b id="mw_A">else</b> <b id="mw_Q">return</b> d mod 2<sup id="mw_g">w</sup>

This produces the NAF needed to now perform the multiplication. This algorithm requires the pre-computation of the points ${\displaystyle \{1,3,5,\dots ,2^{w-1}-1\}P}$ and their negatives, where ${\displaystyle P}$ is the point to be multiplied. On typical Weierstrass curves, if ${\displaystyle P=\{x,y\}}$ then ${\displaystyle -P=\{x,-y\}}$. So in essence the negatives are cheap to compute. Next, the following algorithm computes the multiplication ${\displaystyle dP}$:

Q ← 0 <b id="mwAQY">for</b> j ← i − 1 downto 0 <b id="mwAQc">do</b> Q ← point_double(Q) <b id="mwAQg">if</b> (d<sub id="mwAQk">j</sub> != 0) Q ← point_add(Q, d<sub id="mwAQo">j</sub>P) <b id="mwAQs">return</b> Q

The wNAF guarantees that on average there will be a density of ${\displaystyle \frac{1}{w+1}}$ point additions (slightly better than the unsigned window). It requires 1 point doubling and ${\displaystyle 2^{w-2}-1}$ point additions for precomputation. The algorithm then requires ${\displaystyle n}$ point doublings and ${\displaystyle \frac{n}{w+1}}$ point additions for the rest of the multiplication.

One property of the NAF is that we are guaranteed that every non-zero element ${\displaystyle d_i}$ is followed by at least ${\displaystyle w-1}$ additional zeroes. This is because the algorithm clears out the lower ${\displaystyle w}$ bits of ${\displaystyle d}$ with every subtraction of the output of the mods function. This observation can be used for several purposes. After every non-zero element the additional zeroes can be implied and do not need to be stored. Secondly, the multiple serial divisions by 2 can be replaced by a division by ${\displaystyle 2^w}$ after every non-zero ${\displaystyle d_i}$ element and divide by 2 after every zero.

It has been shown that through application of a FLUSH+RELOAD side-channel attack on OpenSSL, the full private key can be revealed after performing cache-timing against as few as 200 signatures performed.

Montgomery ladder

The Montgomery ladder approach computes the point multiplication in a fixed number of operations. This can be beneficial when timing, power consumption, or branch measurements are exposed to an attacker performing a side-channel attack. The algorithm uses the same representation as from double-and-add.

R<sub id="mwASg">0</sub> ← 0 R<sub id="mwASk">1</sub> ← P <b id="mwASo">for</b> i from m downto 0 <b id="mwASs">do</b> <b id="mwASw">if</b> d<sub id="mwAS0">i</sub> = 0 <b id="mwAS4">then</b> R<sub id="mwAS8">1</sub> ← point_add(R<sub id="mwATA">0</sub>, R<sub id="mwATE">1</sub>) R<sub id="mwATI">0</sub> ← point_double(R<sub id="mwATM">0</sub>) <b id="mwATQ">else</b> R<sub id="mwATU">0</sub> ← point_add(R<sub id="mwATY">0</sub>, R<sub id="mwATc">1</sub>) R<sub id="mwATg">1</sub> ← point_double(R<sub id="mwATk">1</sub>) // invariant property to maintain correctness <b id="mwATo">assert</b> R<sub id="mwATs">1</sub> == point_add(R<sub id="mwATw">0</sub>, P) <b id="mwAT0">return</b> R<sub id="mwAT4">0</sub>

This algorithm has in effect the same speed as the double-and-add approach except that it computes the same number of point additions and doubles regardless of the value of the multiplicand d. This means that at this level the algorithm does not leak any information through branches or power consumption.

However, it has been shown that through application of a FLUSH+RELOAD side-channel attack on OpenSSL, the full private key can be revealed after performing cache-timing against only one signature at a very low cost.

Longer chains

Using Lucas chains provides an optimized sequence of doubling and adds compared to the Montgomery ladder, which is faster on larger multiples (longer chains). This method is called "PRAC". PRAC is also published by Montgomery, with the "reference implementation" being GMP-ECM. DJ Bernstein mentions a number of such schemes in 2017.

Constant time Montgomery ladder

The security of a cryptographic implementation is likely to face the threat of the so-called timing attacks which exploits the data-dependent timing characteristics of the implementation. Machines running cryptographic implementations consume variable amounts of time to process different inputs and so the timings vary based on the encryption key. To resolve this issue, cryptographic algorithms are implemented in a way which removes data dependent variable timing characteristic from the implementation leading to the so-called constant-time implementations. Software implementations are considered to be constant-time in the following sense as stated in: “avoids all input-dependent branches, all input-dependent array indices, and other instructions with input-dependent timings.” The GitHub page lists coding rules for implementations of cryptographic operations, and more generally for operations involving secret or sensitive values.

The Montgomery ladder is an ${\displaystyle x}$-coordinate only algorithm for elliptic curve point multiplication and is based on the double and add rules over a specific set of curves known as Montgomery curve. The algorithm has a conditional branching such that the condition depends on a secret bit. So a straightforward implementation of the ladder won't be constant time and has the potential to leak the secret bit. This problem has been addressed in literature and several constant time implementations are known. The constant time Montgomery ladder algorithm is as given below which uses two functions CSwap and Ladder-Step. In the return value of the algorithm Z₂^p-2 is the value of Z₂⁻¹ computed using the Fermat's little theorem.

<b id="mwAXE">algorithm</b> Montgomery-Ladder(x<sub id="mwAXI">P</sub>, n) <b id="mwAXM">is</b> <b id="mwAXQ">input</b>: An <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt94" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"l"}}' id="mwAXU"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle l}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>l</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle l}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/829091f745070b9eb97a80244129025440a1cfac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}"/></span>-bit scalar <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt95" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"n"}}' id="mwAXY"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"/></span> and the <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt96" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"x"}}' id="mwAXc"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"/></span>-coordinate <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt97" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"x_P"}}' id="mwAXg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle x_{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b3afc04bf6ffcfa116dc353b44824a2004614aef" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.796ex; height:2.009ex;" alt="{\displaystyle x_{P}}"/></span> of a point <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt98" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"P"}}' id="mwAXk"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"/></span>. <b id="mwAXo">output</b>: <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt99" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"x"}}' id="mwAXs"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"/></span>-coordinate of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt100" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"nP"}}' id="mwAXw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle nP}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle nP}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a9a4ea84878846281ad19ebadcf5c5778249873d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.14ex; height:2.176ex;" alt="{\displaystyle nP}"/></span>, the <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt101" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"n"}}' id="mwAX0"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"/></span>-times scalar multiple of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt102" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"P"}}' id="mwAX4"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"/></span>. X<sub id="mwAX8">1</sub> ← x<sub id="mwAYA">P</sub>; X<sub id="mwAYE">2</sub> ← 1; Z<sub id="mwAYI">2</sub> ← 0; X<sub id="mwAYM">3</sub> ← x<sub id="mwAYQ">P</sub>; Z<sub id="mwAYU">3</sub> ← 1 prevbit ← 0 <b id="mwAYY">for</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt103" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"i"}}' id="mwAYc"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"/></span> from <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt104" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"l-1"}}' id="mwAYg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle l-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>l</mi> <mo>−<!-- − --></mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle l-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e0d448948a353d0b2469b88ca918f34e32c8752" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.696ex; height:2.343ex;" alt="{\displaystyle l-1}"/></span> downto 0 <b id="mwAYk">do</b> bit ← bit-value at index <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt105" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"i"}}' id="mwAYo"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}"/></span> of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt106" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"n"}}' id="mwAYs"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"/></span> b ← bit <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt107" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\oplus"}}' id="mwAYw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \oplus }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⊕<!-- ⊕ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8b16e2bdaefee9eed86d866e6eba3ac47c710f60" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }"/></span> prevbit prevbit ← bit (<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt108" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAY0"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAY4">2</sub>,Z<sub id="mwAY8">2</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt109" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAZA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt110" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAZE"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAZI">3</sub>,Z<sub id="mwAZM">3</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt111" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAZQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>) ← CSwap(<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt112" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAZU"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAZY">2</sub>,Z<sub id="mwAZc">2</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt113" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAZg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt114" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAZk"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAZo">3</sub>,Z<sub id="mwAZs">3</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt115" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAZw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,b) (<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt116" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAZ0"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAZ4">2</sub>,Z<sub id="mwAZ8">2</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt117" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAaA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt118" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAaE"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAaI">3</sub>,Z<sub id="mwAaM">3</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt119" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAaQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>) ← Ladder-Step(<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt120" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAaU"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAaY">2</sub>,Z<sub id="mwAac">2</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt121" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAag"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt122" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAak"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAao">3</sub>,Z<sub id="mwAas">3</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt123" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAaw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,X<sub id="mwAa0">1</sub>)<br id="mwAa4"/> <b id="mwAa8">return</b> X<sub id="mwAbA">2</sub>Z<sub id="mwAbE">2</sub><sup id="mwAbI">p-2</sup>

The Ladder-Step function (given below) used within the ladder is the core of the algorithm and is a combined form of the differential add and doubling operations. The field constant a₂₄ is defined as a₂₄ = ${\displaystyle (A+2)/4}$, where ${\displaystyle A}$ is a parameter of the underlying Montgomery curve.

<b id="mwAbo">Function</b> Ladder-Step(<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt126" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAbs"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAbw">2</sub>,Z<sub id="mwAb0">2</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt127" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAb4"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt128" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAb8"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAcA">3</sub>,Z<sub id="mwAcE">3</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt129" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAcI"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,X<sub id="mwAcM">1</sub>)<br id="mwAcQ"/> T<sub id="mwAcU">1</sub> ← X<sub id="mwAcY">2</sub> + Z<sub id="mwAcc">2</sub> T<sub id="mwAcg">2</sub> ← X<sub id="mwAck">2</sub> - Z<sub id="mwAco">2</sub> T<sub id="mwAcs">3</sub> ← X<sub id="mwAcw">3</sub> + Z<sub id="mwAc0">3</sub> T<sub id="mwAc4">4</sub> ← X<sub id="mwAc8">3</sub> - Z<sub id="mwAdA">3</sub> T<sub id="mwAdE">5</sub> ← T<sub id="mwAdI">1</sub><sup id="mwAdM">2</sup> T<sub id="mwAdQ">6</sub> ← T<sub id="mwAdU">2</sub><sup id="mwAdY">2</sup> T<sub id="mwAdc">2</sub> ← T<sub id="mwAdg">2</sub> · T<sub id="mwAdk">3</sub> T<sub id="mwAdo">1</sub> ← T<sub id="mwAds">1</sub> · T<sub id="mwAdw">4</sub> T<sub id="mwAd0">1</sub> ← T<sub id="mwAd4">1</sub> + T<sub id="mwAd8">2</sub> T<sub id="mwAeA">2</sub> ← T<sub id="mwAeE">1</sub> - T<sub id="mwAeI">2</sub> X<sub id="mwAeM">3</sub> ← T<sub id="mwAeQ">1</sub><sup id="mwAeU">2</sup> T<sub id="mwAeY">2</sub> ← T<sub id="mwAec">2</sub><sup id="mwAeg">2</sup> Z<sub id="mwAek">3</sub> ← T<sub id="mwAeo">2</sub> · X<sub id="mwAes">1</sub> X<sub id="mwAew">2</sub> ← T<sub id="mwAe0">5</sub> · T<sub id="mwAe4">6</sub> T<sub id="mwAe8">5</sub> ← T<sub id="mwAfA">5</sub> - T<sub id="mwAfE">6</sub> T<sub id="mwAfI">1</sub> ← a<sub id="mwAfM">24</sub> · T<sub id="mwAfQ">5</sub> T<sub id="mwAfU">6</sub> ← T<sub id="mwAfY">6</sub> + T<sub id="mwAfc">1</sub> Z<sub id="mwAfg">2</sub> ← T<sub id="mwAfk">5</sub> · T<sub id="mwAfo">6</sub><br id="mwAfs"/> <b id="mwAfw">return</b> (<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt130" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAf0"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAf4">2</sub>,Z<sub id="mwAf8">2</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt131" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAgA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>,<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt132" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\langle"}}' id="mwAgE"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \langle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/465059661f2295b855415c61124fb1a960e9e888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \langle }"/></span>X<sub id="mwAgI">3</sub>,Z<sub id="mwAgM">3</sub><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt133" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\rangle"}}' id="mwAgQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/39c8d726068b5e1a371e72e13feafb8c8cd4b0d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.905ex; height:2.843ex;" alt="{\displaystyle \rangle }"/></span>)

The CSwap function manages the conditional branching and helps the ladder to run following the requirements of a constant time implementation. The function swaps the pair of field elements ${\displaystyle ⟨}$X₂,Z₂${\displaystyle ⟩}$ and ${\displaystyle ⟨}$X₃,Z₃${\displaystyle ⟩}$ only if ${\displaystyle b}$ = 1 and this is done without leaking any information about the secret bit. Various methods of implementing CSwap have been proposed in literature. A lesser costly option to manage the constant time requirement of the Montgomery ladder is conditional select which is formalised through a function CSelect. This function has been used in various optimisations and has been formally discussed in

Since the inception of the standard Montgomery curve Curve25519 at 128-bit security level, there has been various software implementations to compute the ECDH on various architectures and to achieve best possible performance cryptographic developers have resorted to write the implementations using assembly language of the underlying architecture. The work provided a couple of 64-bit assembly implementations targeting the AMD64 architecture. The implementations were developed using a tool known as qhasm which can generate high-speed assembly language cryptographic programs. The function CSwap was used in the implementations of these ladders. After that there has been several attempts to optimise the ladder implementation through hand-written assembly programs out of which the notion of CSelect was first used in and then in. Apart from using sequential instructions, vector instructions have also been used to optimise the ladder computation through various works. Along with AMD64, attempts have also been made to achieve efficient implementations on other architectures like ARM. The works and provides efficient implementations targeting the ARM architecture. The libraries lib25519 and are two state-of-art libraries containing efficient implementations of the Montgomery ladder for Curve25519. Nevertheless, the libraries have implementations of other cryptographic primitives as well.

Apart from Curve25519, there have been several attempts to compute the ladder over other curves at various security levels. Efficient implementations of the ladder over the standard curve Curve448 at 224-bit security level have also been studied in literature. A curve named Curve41417 providing security just over 200 bits was proposed in which a variant of Karatsuba strategy was used to implement the field multiplication needed for the related ECC software. In pursuit of searching Montgomery curves that are competitive to Curve25519 and Curve448 research has been done and couple of curves were proposed along with efficient sequential and vectorised implementations of the corresponding ladders. At 256-bit security level efficient implementations of the ladder have also been addressed through three different Montgomery curves.