1 | initial version |

Since $q$ is a prime here, $\mathbb{Z}/p$ is a field, usually denoted by $F_q$.

All its nonzero elements are invertible, and form a group under multiplication. This group is called the multiplicative group of this field, or its group of units.

This group has order $q-1$ (since it contains all nonzero elements of $F_q$), so every nonzero element $x$ in $\F_q$ satisfies $x^{q-1} = 1$, which can be written as $x^{q-2} \cdot x = 1$, so we get that for any nonzero $x$ in $ F_q$, $x^{q-2}$ is the multiplicative inverse of $x$.

The function `expmod(b, e, m)`

(for "exponentiation modulo")
computes $b^e$ modulo $m$. Here the arguments of this function
are named to reflect their role (basis, exponent, modulus).

Finally, the function `inv`

just computes $x^{q-2}$ modulo $q$.

2 | No.2 Revision |

Since $q$ is a prime here, ~~$\mathbb{Z}/p$ ~~$\mathbb{Z}/q$ is a field,
usually denoted by $F_q$.

All its nonzero elements are invertible, and form a group under multiplication. This group is called the multiplicative group of this field, or its group of units.

This group has order $q-1$ (since it contains all nonzero elements of $F_q$), so every nonzero element $x$ in $\F_q$ satisfies $x^{q-1} = 1$, which can be written as $x^{q-2} \cdot x = 1$, so we get that for any nonzero $x$ in $ F_q$, $x^{q-2}$ is the multiplicative inverse of $x$.

The function `expmod(b, e, m)`

(for "exponentiation modulo")
computes $b^e$ modulo $m$. Here the arguments of this function
are named to reflect their role (basis, exponent, modulus).

Finally, the function `inv`

just computes $x^{q-2}$ modulo $q$.

3 | No.3 Revision |

Since $q$ is a prime here, $\mathbb{Z}/q$ is a field, usually denoted by $F_q$.

All its nonzero elements are invertible, and form a group under multiplication. This group is called the multiplicative group of this field, or its group of units.

This group has order $q-1$ (since it contains all nonzero
elements of $F_q$), so every nonzero element $x$ in ~~$\F_q$
~~$F_q$
satisfies $x^{q-1} = 1$, which can be written as
$x^{q-2} \cdot x = 1$, so we get that for any nonzero $x$
in $ F_q$, $x^{q-2}$ is the multiplicative inverse of $x$.

The function `expmod(b, e, m)`

(for "exponentiation modulo")
computes $b^e$ modulo $m$. Here the arguments of this function
are named to reflect their role (basis, exponent, modulus).

Finally, the function `inv`

just computes $x^{q-2}$ modulo $q$.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.