0
$\begingroup$

In an attempt to understand the mathematical operations related to encryption with elliptic curves, in particular finite field arithmetic (Modular reduction) I found in the Montgomery reduction that Montgomery form is an alternative finite field representation. what is this suppose to mean ? what it does differ from the usual finite field representation ?

$\endgroup$
2

1 Answer 1

1
$\begingroup$

Montgomery arithmetic is a technique for modular computation modulo some integer $m$. It centers on Montgomery reduction, an alternative to reduction modulo $m$ by Euclidean division.

Montgomery reduction uses an alternate representation of the ring of integers modulo $m$. That is, the representation of a ring element $A$ as digits is not the same as in the Positional Number System, where $A$ is represented by digits $a_j$ in some base $\beta$, with $0\le a_j<\beta$ and $A=\sum a_j\,\beta^j$ (and perhaps $A<m$, making the tuple unique). In Montgomery representation with $m<\beta^\ell$ and $\gcd(m,\beta)=1$, a ring element $A$ is represented by a tuple of $\ell$ digits $a_j$, with $0\le a_j<\beta$ and $\beta^\ell\,A\;\equiv\;\sum a_j\,\beta^j\pmod m$ (and perhaps $\sum a_j\,\beta^j<m$, making the tuple unique).

Montgomery reduction avoids the issue that in long division in PSN, the step of estimating the next digit in the quotient is difficult and occasionally off-by-one, thus requiring a correction before (or at) the processing of the next quotient digit. In the bulk of Montgomery reduction this is replaced by a simple operation with no exceptional case. That simplicity makes it easier to interleave modular multiplication and reduction, which in turn reduces memory accesses.


Montgomery reduction has little relation with Montgomery elliptic curves. The closest is that for Montgomery elliptic curves on a finite field of large characteristic (that is field $\mathbb F_{p^k}$ with large $p$), arithmetic modulo $p$ can use Montgomery reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.