pub struct Num(/* private fields */);Expand description
Number used for modular arithmetic. Internally stored in little-endian (least-significant byte first) format.
Implementations§
Source§impl Num
impl Num
pub const ZERO: Num
pub const ONE: Num
pub const TWO: Num
pub const THREE: Num
pub const SEVEN: Num
pub const fn from_le_words(n: [u64; 4]) -> Self
pub fn from_le_bytes(b: [u8; 32]) -> Self
pub fn to_le_bytes(&self) -> [u8; 32]
Sourcepub fn inv(&self, p: Self) -> Option<Self>
pub fn inv(&self, p: Self) -> Option<Self>
Get the modular multiplicative inverse of the number by using the
extended Euclidean algorithm. Returns None for Num::ZERO,
since 0 has no inverse.
The non-extended Euclidean algorithm computes the greatest common divisor $gcd(a, b)$ given $a, b, a \leq b$. It relies on the following fact: $gcd(a, b) = gcd(b - \lfloor \frac{b}{a} \rfloor a, a)$. This fact allows the algorithm to successively reduce the values of $a$ and $b$ until one is eventually equal to zero, and the other is equal to the greatest common divisor. The algorithm operates as follows:
- Set $u = a, v = b$. The algorithm maintains the invariant that $u \leq v$.
- Iteratively update $u$ and $v$. First, get the quotient $q = \lfloor \frac{v}{u} \rfloor$, then set the new values $v' = u, u' = v - qu$. Note that $v - qu$ is the remainder from dividing $v$ by $u$. Call this remainder $r$, so that $u = r$.
- Terminate when $u = 0$. $v$ is the greatest common divisor.
To extend the algorithm above, apply Bezout’s identity. This identity states that, given two integers $a$ and $b$ with greatest common divisor $d$, there exist integers $x$ and $y$ such that $ax + by = d$.
The extended algorithm will represent $u$ and $v$ as
$$ u = x_1a + y_1b \\ v = x_2a + y_2b $$
Since $u$ should be initialized to $a$, and $v$ should be initialized to $b$, the initial values for $x_{1, 2}$ and $y_{1, 2}$ are $x_1 = 1, y_1 = 0, x_2 = 0, y_2 = 1$.
The rest of the algorithm is exactly the same, except that apart from updating $u$ and $v$ like the regular Euclidean algorithm, the extended Euclidean algorithm also updates $x_{1, 2}$ and $y_{1, 2}$. This is done as follows:
$$ x_2' = x_1 \\ x_1' = x_2 - qx_1 \\ y_2' = y_1 \\ y_1' = y_2 - qy_1 $$
Where $q = \lfloor \frac{v}{u} \rfloor$ is the quotient and $r = v - qu$ is the remainder, same as in the non-extended Euclidean algorithm. It is not difficult to verify that the values for $x_{1, 2}'$ and $y_{1, 2}'$ are correct. Namely, it must be true that $v' = u$ and $u' = r$ as in the non-extended Euclidean algorithm. This can be shown with a few substitutions:
$$ v' = x_2'a + y_2'b \\ v' = x_1a + y_1 b \\ v' = u $$
And
$$ u' = x_1'a + y_1'b \\ u' = (x_2 - qx_1)a + (y_2 - qy_1)b \\ u' = ax_2 + by_2 - (ax_1 + by_1)q \\ u' = v - qu $$
So $v' = u, u' = v - qu$ as expected. The algorithm terminates when $u = 0$, at which point $x_2$, $y_2$, and $v$ are the result of the algorithm.
Finally, the above can be used to get a multiplicative inverse. If $b$ (or $a$) is prime, the result of the algorithm will be $v = 1$ because the greatest common divisor between a prime number and any other number is 1.
$$ v = 1 = x_2a + y_2b $$
If the operations are done in a prime field with order $b$, then
$$ y_2b \equiv 0 \pmod b \implies v \equiv x_2a \equiv 1 \pmod b $$
This means that $x_2$ is the multiplicative inverse of $a$ in the prime field with order $b$. Finally, since $y_1$ and $y_2$ are not used, they can be omitted from the algorithm as a small optimization.
Trait Implementations§
Source§impl<C: Curve> Mul<Point<C>> for Num
Multiply the point by a scalar.
impl<C: Curve> Mul<Point<C>> for Num
Multiply the point by a scalar.
This uses the square-and-multiply method. For example, to calculate $x^{19}$, start with $y = x$ and multiply $y$ with itself, resulting in $y = y \cdot y = x^2$. Then, multiply $y$ with itself again, resulting in $y = y \cdot y = x^4$. Repeat this until it can no longer be done, at which point $y = x^{16}$ and there have been four multiplications thus far. Finally, multiply $y$ with $x$ three more times to get the desired result.
With this method, $x^{19}$ was calculated in only seven multiplications, compared to the naive algorithm which would execute 19 multiplications.
In the case of elliptic curve points, the “square” is equivalent to doubling, and “multiply” is equivalent to addition.