Tag Info

3

The usual motivation for using Montgomery multiplication is that it significantly reduces the cost of modular reduction by changing the representation of elements. In the Montgomery ring the polynomial $A(x)$ is instead represented by $a(x)=A(x)r(x)\pmod{n(x)}$ where $r(x)$ is a fixed element of the same degree as $n(x)$, but for which division is very ...

2

Where to apply Montgomery Multiplication in $GF(2^n)$? This answer really depends on how you constructed the binary extension field $GF(2^n)$. If the irreducible polynomial is trinomial or pentanomial then the reduction is already efficient! Modular Multiplication with trinomials Let $GF(2^n)$ is constructed with the trinomial $P(x)=x^m+x^n+1$ where $\alpha$...

1

Elliptic curves can be represented in different form. The most basic equation, in which every elliptic curve can be represented is the Weierstraß equation: $$y^2 = x^3 + ax + b$$ For a Montgomery curve it must be able to be represented in the following form: $$(b)y^2 = x^3 + ax^2 + x$$ For every Montgomery curve it is possible to transform its equation to ...

1

The key to Montgomery Multiplication is the prescaling of one or two of the inputs by $r^k$ as stated in this answer by kelalaka to How Does Montgomery Reduction Work. In the case of polynomial evaluation of $$p = a_0 + a_1b^1 + a_2b^2 + ... + a_mb^m \mod n$$ by Horner's scheme: $$p = (((a_m * B) + a_{m-1}) * B + ...) * B + a_0$$  = (((a_m b ) + a_{m-1}) b ...

Only top voted, non community-wiki answers of a minimum length are eligible