Definition of $x^u bmod k$

What is the exact definition of $x^ubmod k$?

In RSA and most cryptographic contexts, $x^ubmod k$ is written with:

• $k$ in the set $Bbb N^*$ of strictly positive integers. $k$ is the modulus (plural moduli)
• $u$ in the set $Bbb Z$ of signed integers. $u$ is the exponent.
• $x$ in the set $Bbb Z$ of signed integers, or in the set $Bbb Z_k$ of integers modulo $k$. The later is a special case of the former, since we'll assimilate $Bbb Z_k$ to the non-negative integers less than $k$.

$x^ubmod k$ can be spoken « $x$ raised to the power $u$ [small pause] modulo $k$ », and becomes « $x$ to the $u$ mod $k$ », or « $x$ to $u$ » under time constraints.

For the full definition, skip to $eqref{fgr4}$. For a gentle introduction, we'll first study the

definition with exponent $u>0$

When $u>0$, the notation $x^ubmod k$ just stands for $left(x^uright)bmod k$, where $x^u=z$ and $zbmod k=y$ have their usual definition:

• $x^u$ is $underbrace{xcdot xcdots xcdot x}_{utext{ term(s)}},$ where $cdot$ is integer multiplication. More formally $$x^u,underset{text{def}}=begin{cases} x&text{if},u=1\ xcdotleft(x^{left(u-1right)}right)&text{if},u>1 end{cases}tag1label{fgr1}$$ Note: the parentheses would usually be omitted¹.
• $zbmod k$ is defined to be $y$ such that $0le y<k$ and $z-y$ is a multiple of $k$. Equivalently:
  • $zbmod k$ is obtained from $z$ by subtracting or adding $k$ as many times as necessary for the result to be in range $[0,k)$. More formally: $$zbmod k,underset{text{def}}=begin{cases} z&text{if},0le z<k\ left(z-kright)bmod k&text{if},zge k\ left(z+kright)bmod k&text{if},z<0 end{cases}tag2label{fgr2}$$
  • If $zge 0$, then $zbmod k$ is the remainder in the Euclidean division of $z$ by $k$;
    otherwise, $zbmod k$ is $k-1-left(left(-z-1right)bmod kright)$.
    More formally, noting $ell$ for the quotient (with $ell=leftlfloor z/krightrfloor$ per the mathematical definition of that): $$zbmod k,underset{text{def}}=yinBbb Z_k,text{ such that },existsellinBbb Z,text{ such that },y=z-ellcdot ktag3label{fgr3}$$

Example: We compute $3^5bmod35$ directly from this definition. That's $x^ubmod k$ with $x=3$, $u=5$, $k=35$. We compute $x^u=3^5=3cdot3cdot3cdot3cdot3=243$. We perform the Euclidean division of $z=243$ by $k=35$, yielding quotient $ell=6$ and remainder $y=243-6cdot35=33$. Thus $3^5bmod35=33$.

In Python, the above is obtained as (3**5)%35 or pow(3,5)%35 or pow(3,5,35). The three forms internally use exponentiation by squaring, but only the later uses modular reduction of intermediary results. Using both techniques is essential for even mildly efficient modular exponentiation in RSA, e.g. encryption per $C=M^ebmod N$ with common parameters like 2048-bit $N$ and $e=65537$.
Starting with Python 3.8, pow also handles all the following.

---

Extensions to any integer exponent $u$

The full² definition of $x^ubmod k$ in cryptography is: $$begin{array}{l} x^ubmod kunderset{text{def}}=\\ begin{cases} yinBbb Z_k,;existsellinBbb Z,;y=x^u-ellcdot k&text{if }u>0\ yinBbb Z_k,;existsellinBbb Z,;ycdot x^{-u}+ellcdot k=1&text{if }u<0,;k>1text{ and }gcd(x,k)=1\ text{undefined}&text{if }u<0,;k>1text{ and }gcd(x,k)ne1\ 1&text{if }u=0,;k>1\ 0&text{if }k=1\ end{cases}end{array}tag4label{fgr4}$$ In this, $Bbb Z_k$ stands for the non-negative integers less than $k$, or equivalently the integers modulo $k$. “$text{such that}$” is replaced by “$,;$” which is common practice (suppressing it is also accepted).

This definition extends $eqref{fgr3}$ to the multiplicative group of integers modulo $k$, that is the subset $Bbb Z_k^*$ of $Bbb Z_k$ that forms a group under multiplication modulo $k$. For negative $u$, the notation $x^{-u}bmod k$ is now defined as the multiplicative inverse of $x^u$ in $Bbb Z_k^*$.

Definition $eqref{fgr4}$ maximizes the domain where it holds the property: $$begin{array}{l} text{if },x^ubmod k,text{ and },x^vbmod k,text{ are both defined, then}\ quadbigl(left(x^ubmod kright)cdotleft(x^vbmod kright)bigr)bmod k;=;x^{u+v}bmod k end{array}tag5label{fgr5}$$

When $u<0$ and $k>1$, the equation $ycdot x^{-u}+ellcdot k=1$ follows from extending definition $eqref{fgr3}$ with $y=x^ubmod k$ constrained to be an integer, while insuring property $eqref{fgr5}$. With $x^{-u}$ replaced by $z$, that becomes a Bézout identity $ycdot z+ellcdot k=1$. The requirement $gcd(x,k)=1$ pops up, as well that $y$ and $ell$ can³ be computed per the extended Euclidean algorithm (that can yield $y<0$; we need to bring it back to positive by reducing it modulo $k$, or equivalently adding $k$).

Example: We compute $3^{-5}bmod35$ directly from this definition. That's $x^ubmod k$ with $x=3$, $u=-5$, $k=35$. We compute $x^{-u}=3^5=3cdot3cdot3cdot3cdot3=243$. We perform the extended Euclidean algorithm to solve for $y$ (and $ell$ that we don't need) the Bézout identity $ycdot 243+ellcdot 35=1$. Using the pseudocode of this Try It Online!, the steps are $$begin{array}{rrrrrrr|rrr} r&r'&s&s'&t&t'&q&zcdot s+kcdot t&=&r\ hline 243&35&1&0&0&1&6&243cdot1+35cdot0&=&243\ 35&33&0&1&1&-6&1&243cdot0+35cdot1&=&35\ 33&2&1&-1&-6&7&16&243cdot1+35cdot(-6)&=&33\ 2&1&-1&17&7&-118&2&243cdot(-1)+35cdot7&=&2\ 1&0&17&-35&-118&243&&243cdot17+35cdot(-118)&=&1 end{array}$$ and that yields $y=17$, $ell=-118$. Thus $3^{-5}bmod35=17$.

The definition $eqref{fgr4}$ is such that $$begin{array}{l} text{if any two among the three $;x^ubmod k$, $;;x^vbmod k$, $;;x^{ucdot v}bmod k$}\ text{are defined, then all three quantities are defined, and}\ quadleft(x^ubmod kright)^vbmod k;=;x^{ucdot v}bmod k;=;left(x^vbmod kright)^ubmod k end{array}tag6label{fgr6}$$ Applied for a negative $w$ with positive $u=-w$ and $v=-1$, $eqref{fgr6}$ allows computing $x^wbmod k$ using modular exponentiation with a positive exponent, and (after or before that) a modular inversion, thus avoiding monstrously large input to the extended Euclidean algorithm, and using alternative algorithms.

---

The meaning of $bmod$ ^{_{[reference to Monty-Python intentional]}}

In some contexts including the definition of RSA, we need to distinguish two kinds of $bmod$

1. An operator, yielding e.g. the remainder of Euclidean division when applied to two strictly positive integers. It is to be typeset using bmod k in $LaTeX$ / MathJax (see this, or this for more). In this case, that operator's result, when and if defined, is always a non-negative integer less than the modulus. And, depending on context, that operator has
   • two arguments like in $7bmod5$, or in $7bmod5,=,2$, or in $2,=,7bmod5$. The first is the integer $2$, the later two are two true statements.
   • three arguments like in $3^{-1}bmod5$, or in $3^{-1}bmod5,=,2$, or in $2,=,3^{-1}bmod5$. The first is the integer $2$, the later two are two true statements.
2. The indication of modular equivalence (class) in what stands on its left. That is best typeset:
   • As pmod k in $LaTeX$ / MathJax, which shows as “$pmod k$” with an opening parenthesis “$($” immediately before $bmod$ and a closing parenthesis “$)$” after the modulus.
   • And⁴ with the sign $equiv$ rather than $=$ anywhere on its left.
   • And with only the closing parenthesis on the right of the modulus.

Example of typographically and mathematically correct usages of modular equivalence:

• Definition: $requiv sbmod m;underset{text{def}}iff;existsellinBbb Z,,r=s+ellcdot m$
• In any valid RSA public/private key, $ecdot dequiv1pmod{lambda(N)}$
• It holds $7equiv2 pmod 5$ thus $2equiv7 pmod 5$
• It holds $3^5equiv243equiv33 pmod{35}$ thus $33equiv3^5 pmod{35}$
• $lambda(35)=12$ and $-5=7 pmod{12}$, thus $3^{-5}equiv3^7equiv2187equiv17 pmod{35}$.
• $7pmod 5$ can be seen as the infinite set ${ldots,-8,-3,2,7,12,ldots}$.

Sometime a statement is false with the operator from, that would be true as a modular equivalence: $7=7bmod5$ stands for $7,=,(7bmod5)$ thus is false, when $7equiv7 pmod 5$ is true.

The distinction matters in RSA encryption, with ciphertext $C$ specified by $C=M^ebmod N$ where $M$ represents the message. In this, $bmod$ is an operator, thus implies $0le C<N$, which is important. An encryption system only specified to output $C$ such that $Cequiv M^epmod N$ could output $C=M^e$ and be totally insecure, or leak some sensitive information by selectively producing $C=(M^ebmod N)+N$.

---

What is the difference between $x^u=ybmod k$ and $x^uequiv ybmod k$ ?

The cardinal way to read the correct $x^u=ybmod k$ is as $x^u=(ybmod k)$ with $bmod$ an operator. Unambiguously, that implies $x^uequiv ypmod k$, that is $y-x^u$ is a multiple of $k$. Formally, $x^u=(ybmod k)$ also implies $0le x^u<k$. But it is not often that $0le x^u<k$ is meant, thus I try to not use $x^u=ybmod k$, and would use $x^u=(ybmod k)$ only if $0le x^u<k$ was intended.

I'm reading $x^uequiv ybmod k$ (using bmod) as a slight $TeX$po™ of $x^u equiv ymod k$ (using mod, which adds spacing on the left to indicate that it is not an operator) or $x^uequiv ypmod k$ (using pmod, which adds parentheses to more clearly indicate the same thing). Thus here $bmod$ stands for modular equivalence. I avoid mod when pmod rather than bmod is meant, because except in contexts like tex-SE or a JOC paper, 90% of the audience will not interpret the slight extra space correctly.

---

¹ Raising to a power is performed before multiplication (thus before addition), tough after any operation in the exponent. The exponent is on the right, and is typographically distinguishable by being higher and in smaller characters. If that's not feasible, it is often used ** or ^^ (or ^ when confusion with eXlusive-OR operator $oplus$ is impossible), and parentheses.

² Sometime $x^ubmod 1$ and/or $x^0bmod k$ with $gcd(x,k)ne1$ are left undefined or unspecified, for simplicity and because they are seldom practically useful.

³ Since we do not need $ell$, we can simplify the extended Euclidean algorithm by removing the two variables $t$ and $t'$. When performing the algorithm by hand, that has the drawback we can't check intermediary results. But we can still check $ycdot zbmod k=1$ in the end.

⁴ Sometime, this $equiv$ becomes $=$, or the $($ immediately on the left of $bmod$ vanishes [together owith the matching $)$ after the modulus]. But absent at least one of these indications, the meaning changes: we are back to the $bmod$ operator.

It sounds like the questions can be summarized as "when a cryptographer writes $bmod$, what do they mean?

Well, it turns out that $bmod$ has (at least) three subtly different meanings, based on context:

• It can be a function that takes two integers, and evaluates to an integer. In this context, the expression $a bmod b$ is that value that can be expressed as $a + bi$ for some integer $i$ with $0 le a + bi < b$ (assuming $b > 0$); this integer $i$ can be positive, negative or zero. This is the % operation in some computer languages (C, for example), and it is actually somewhat rare in cryptography, in that most uses of $bmod$ can be better understood to be one of other two meanings.

• It can be a notation that two values are taken as "equal" if they differ by a multiple of the modulus; that is, when we write $a = b bmod n$ (or $a equiv b bmod n$, or as I generally prefer, $a = b pmod n$), that is a claim that there is an integer $i$ such that $a - b = icdot n$. This meaning differs from the previous in that it is not an operation on $b$; for example, $103 = 3 bmod {100}$, even though the first meaning would have $3 bmod 100$ would evaluate to 3.

• It can be a note that the operations are to be understood to be taken over the ring $mathbb{Z}_n$, rather than the integers (also known as $mathbb{Z}$). The addition, subtraction and multiplication operations in that ring can be implemented as "perform the operations as if they were over the integers, and then reduce things modulo $n$"; however, division and computing inverses cannot be. For example, when we write $e^{-1} bmod{ phi(n) }$, this is the meaning we are using.

And, to make things even more fun, somethings the $bmod$ notation is implicit. When we write $g^{xy^{-1}}$, the $xy^{-1}$ is computed modulo the group order of $g$ (meaning 3); the reader is assumed to just know that.

With that, here are the answers to your questions:

What is the exact definition of $x^u bmod k$?

Both the first and third meanings work here; you take $u$ copies of $x$, and multiply them together (either in the ring $mathbb{Z}_k$, or after you perform the multiplications, you then apply the modulo operation - both strategies evaluate to the same thing.

Also, what is the difference between $$x^u = y bmod k$$ and $$x^u equiv ybmod k$$

No real difference; both are ways to use meaning two.