Number Theory

Number Theory and its Application to Cryptography, Combinatorics, Relations

For a comprehensive subject on number theory the reader is referred to the book [Hardy and Wright(1975)].

Elementary number theory

Prime factorisation

${\textstyle \mathrm {\ \ \ \ } }$ Fundamental theorem of arithmetic

Fundamental theorem of arithmetic - in number theory
Every integer ${\textstyle a>1}$ is either prime itself or the product of prime numbers, where this product is unique, up to the order of the factors. In other words

$$a=\prod _{i=1}^{n}p_{i}^{e_{i}}$$

where ${\textstyle p_{i}}$ is the ${\textstyle i}$-th prime number arising in the product generating ${\textstyle a}$ and ${\textstyle e_{i}}$ is its multiplicity.

${\textstyle \mathrm {\ \ \ \ } }$ Prime factorisation algorithm
The prime factorisation is an iterative algorithm to determine the prime factors of a given number. The algorithm is based on the Fundamental theorem of arithmetic. The prime factors are determined by performing iterative division by prime numbers in increasing order.
Example Prime factorisation of ${\textstyle 2520}$

$${\begin{aligned}2520|2&\\1260|2&\\630|2&\\315|3&\\105|3&\\35|5&\\7|7&\\1|\mathrm {\ } &\\\end{aligned}}$$

Prime factorisation is believed to be difficult to perform practically for large number since its time complexity is NP, i.e. superpolynomial (= not bounded above by any polynomial).

Congruence

${\textstyle \mathrm {\ \ \ \ } }$ Modulo operator

Definition - modulo operator
The ${\textstyle a\mod m=}$ the remainder after dividing ${\textstyle a}$ by ${\textstyle m}$.
It follows

$$a\mod m=r\equiv a=k*m+r,\mathrm {~where~} 0<=r<m.$$

Operator identities of modulo operator are given as

1. Distributivity - addition
   $$(a+b)\mod n=[(a\mod n)+(b\mod n)]\mod n$$
2. Distributivity - multiplication
   $$ab\mod n=[(a\mod n)*(b\mod n)]\mod n$$
3. Distributivity - power
   $$a^{c}\mod m=(a\mod m)^{c}\mod m$$

These identities can be proved directly from the definition of the modulo operator. Due to these three identities one can think in modular arithmetic including only addition, multiplication and power, like in regular integer arithmetic without modulo.

${\textstyle \mathrm {\ \ \ \ } }$ Greatest common divisor

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Divisability

Definition - divisability
${\textstyle n}$ is dividable by a if and only if there exists an integer ${\textstyle k}$ for which ${\textstyle n=a*k}$. This is denoted by ${\textstyle a|n}$. The number ${\textstyle a}$ is called the divisor of ${\textstyle n}$.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Greatest common divisor operator

Definition - greatest common divisor, gcd() operator The greatest common division of the integers ${\textstyle a}$ and ${\textstyle b}$, ${\textstyle gcd(a,b)}$ is defined by

$$gcd(a,b)=\max _{i}\{d_{i}\mathrm {~such~that~} d_{i}|a\mathrm {~and~} d_{i}|b\}.$$

An alternative notation of ${\textstyle gcd(a,b)}$ is ${\textstyle (a,b)}$.

The operator characteristics of the ${\textstyle gcd()}$ operator are given by

1. Reflexivity:
   $$(a,b)=(b,a).$$
2. ${\textstyle 0}$ is neutral element with respect to the operator ${\textstyle gcd()}$. In other words
   $$(a,0)=a.$$
3. The following relation holds
   $$(a,b)=(b,a\mod b).$$
   Proof.
   

${\textstyle (a,b)=d\Rightarrow a=de,b=df\mathrm {~and~} (e,f)=1}$.
Let ${\textstyle e=gf+h}$ be, where ${\textstyle h<f}$. It follows that ${\textstyle (f,h)=1}$, since otherwise ${\textstyle f}$ and due to expression of ${\textstyle e}$ also ${\textstyle e}$ were dividable by ${\textstyle (f,h)}$ which would lead to ${\textstyle (e,f)>1}$. Then ${\textstyle a=de=dgf+dh=gb+dh\Rightarrow a\mod b=dh\mod df=dh}$, where the last step comes from ${\textstyle h<f}$. Thus ${\textstyle (b,a\mod b)=(b,dh)=(df,dh)=d}$, due to ${\textstyle (f,h)=1}$.

${\textstyle \mathrm {\ \ \ \ } }$ Congruence

Definition - relatively prime (also called as coprime)
The integers ${\textstyle a}$ and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle b} are relatively prime if and only if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (a,b)=1} .
Definition - congruence
The congruence is a relation and refers to a base number ${\textstyle m}$. The integers Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle b} are in congruence relation if and only if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (a\mod m) = (b\mod m)} . The congruence id denoted by ${\textstyle a\equiv b\mod m}$.

Note that ${\textstyle a\equiv b\mod m}$ implies ${\textstyle m|(b-a)}$. Congruence is an equivalence relation - partitioning the set Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathbb{Z}} to ${\textstyle m}$ disjunct subsets.

Being an equivalence relation, congruence have the following properties: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{aligned} &\mathrm{CP1.~}\mathrm{~ reflexivity~} a \equiv a\mod m\mathrm{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\ &\mathrm{CP2.~}\mathrm{~ symmetry~}a \equiv b \mod~m \Rightarrow b \equiv a\mod m\\ &\mathrm{CP3.~}\mathrm{~ transitivity~} a \equiv b\mod m \mathrm{~ and~} b \equiv c\mod m \Rightarrow a \equiv c\mod m \\ \end{aligned}}

The operator identities of the congruence refer to given ${\textstyle a\equiv b\mod m}$ and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle c \equiv d \mod m} and can be given as
CO1. Adding a constant Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \alpha}

$$a+\alpha \equiv b+\alpha \mod m.$$

CO2. Multiplication by constant ${\textstyle \alpha }$

$${\begin{aligned}&\alpha *a\equiv \alpha *b\mod m.\\&\Rightarrow -a\equiv -b\mod m.\end{aligned}}$$

CO3. Addition of congruences Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a+c \equiv b+d \mod m.} CO4. Multiplication of congruences Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a*c \equiv b*d \mod m.} CO5. Division by constant ${\textstyle \alpha }$ Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha*a \equiv \alpha*b \mod m \Rightarrow a \equiv b \mod m.}

The first three identities can be proved directly from the definitions of the modulo and congruence operators. The last identity follows from the general identity for division by constant:

$$\alpha *a\equiv \alpha *b\mod m\Leftrightarrow a\equiv b\mod (m/d),$$

where ${\textstyle (\alpha ,m)=d}$.
Proof:

$${\begin{aligned}&\alpha *a\equiv \alpha *b\mod m\Leftrightarrow m|[\alpha *(b-a)]\Leftrightarrow \\&[m/d]|[\alpha /d*(b-a)]\Leftrightarrow [m/d]|[(b-a)],\end{aligned}}$$

since Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (m/d,\alpha/d)=1} . Then Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle [m/d]|[(b-a)] \Leftrightarrow a \equiv b \mod (m/d)} .

${\textstyle \mathrm {\ \ \ \ } }$ Congruence class

Definition - Congruence class modulo ${\textstyle m}$ (also called residue class modulo ${\textstyle m}$)
Congruence class modulo ${\textstyle m}$ is any of the disjunct subsets resulted by partitioning the set ${\textstyle \mathbb {Z} }$ by congruence as equivalence relation. In other words congruence class modulo ${\textstyle m}$ is a set Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle {k \in Z \mathrm{~such~that~} k \equiv a \mod m}} for any ${\textstyle a=0,\ldots ,(m-1)}$. For a specific Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} the congruence class modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} is denoted by ${\textstyle a+m\mathbb {Z} }$.

The set of all congruence classes modulo ${\textstyle m}$ is denoted by ${\textstyle \mathbb {Z} /m\mathbb {Z} }$. Thus the number of elements in this set is ${\textstyle m}$, and this set can be given as Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{Z}/m\mathbb{Z} = \{0+m\mathbb{Z}, 1+m\mathbb{Z},..., (m-1)+m\mathbb{Z}\}.}

The set of congruence classes relative prime to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} is denoted by Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (\mathbb{Z}/m\mathbb{Z})^*} . For any ${\textstyle a}$ representing an element of ${\textstyle (\mathbb {Z} /m\mathbb {Z} )^{*}}$ holds ${\textstyle (a,m)=1}$.
Example Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\mathbb{Z}/10\mathbb{Z})^* = \{1+10\mathbb{Z}, 3+10\mathbb{Z}, 7+10\mathbb{Z}, 9+10\mathbb{Z}\}.}

If m is prime then number of elements in ${\textstyle (\mathbb {Z} /m\mathbb {Z} )^{*}}$ = ${\textstyle m}$.

Diophantic equations

Euclidean algorithm

The Euclidean algorithm is the standard way of solving the equation of the form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ax+by=(a,b),} where Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a,b,x,y \in \mathbb{Z}}

${\textstyle \mathrm {\ \ \ \ } }$ Theoretic basics

Bézout’s identity
The greatest common divisor ${\textstyle g}$ of two integers Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} and ${\textstyle b}$ can be represented as a linear sum of the original two numbers ${\textstyle a}$ and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle b} . In other words

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \exists x,y \in \mathbb{Z}, \mathrm{~for~which~} g = (a,b)=ax+by.}

Theorem
The set of all integer linear combinations of the nonzero integer ${\textstyle a}$ and ${\textstyle b}$ equals the set of integer muliples of ${\textstyle (a,b)}$, i.e: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\mathbb{Z}+b\mathbb{Z}=(a,b)\mathbb{Z},}

Proof:

• Step 1: direction Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \Rightarrow} ${\textstyle a\mathbb {Z} +b\mathbb {Z} \in (a,b)\mathbb {Z} }$ - follows from definition of ${\textstyle (a,b)}$
• Step 2: direction Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \Leftarrow} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (a,b)\mathbb{Z} \in a\mathbb{Z}+b\mathbb{Z}} - follows from Bézout’s identity ${\textstyle (a,b)=ax+by,\mathrm {~where~} x,y\in \mathbb {Z} \Rightarrow (a,b)\mathbb {Z} =ax\mathbb {Z} +by\mathbb {Z} }$

Corollary 1
The equation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ax+by = n, \mathrm{~where~} a,b,x,y,n \in \mathbb{Z} \mathrm{~and~} a\neq 0, b\neq 0} has a solution if and only if ${\textstyle (a,b)|n}$.
Proof: It follows directly from the above theorem.
Notes:

• Case 1: If Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (a,b) = 1} then the equation has always a solution.
• Case 2: If ${\textstyle (a,b)=d\neq 1}$ then this case can be fallbacked to Case 1:
  $${\begin{aligned}&a=de,b=df\mathrm {~and~} (e,f)=1~(\mathrm {otherwise~} (a,b)>d)\\&dex+dfy=dg,\mathrm {~then~dividing~by~} d\\&ex+fy=g,\mathrm {~where~} (e,f)=1.\end{aligned}}$$

Corollary 2
The equation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ax+by = (a,b), \mathrm{~where~} a,b,x,y \in \mathbb{Z}\mathrm{~and~}a\neq0, b\neq0} has always a solution.
Proof: It follows directly from Corollary 1.

${\textstyle \mathrm {\ \ \ \ } }$ Solution of equation ${\textstyle ax+by=(a,b)}$

The solution of the equation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ax+by = (a,b)} consists of two steps as

1. determination of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (a,b)} - by means of base variant of Euclidean algorithms and
2. determination of ${\textstyle x}$ and ${\textstyle y}$ - by means of the extended variant of the algorithm.

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Euclidean algorithm - base variant

The idea of the base variant of Euclidean algorithms is the recursive application of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (a,b) = (b, a \mod b)} until Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (h,0) = h} .
Example - determination of ${\textstyle (a,b)}$:

$${\begin{aligned}&455x+135y=(455,135)\\&\\&455=3*135+50\\&135=2*50+35\\&50=1*35+15\\&35=2*15+5\\&15=3*5+0\\&\\&\Rightarrow (455,135)=5\\\end{aligned}}$$

The Pseudo code of determination gcd(a,b) (as well as storing the coefficients q[i]-s) by means of the base variant of the Euclidean algorithm can be given as

$${\begin{aligned}&h=a;\mathrm {~the~higher~value~} \\&s=b\mathrm {~the~smaller~value~} \\&i=0;\\&while(s>0)\mathrm {~until~} s\mathrm {~reaches~} 0\\&\{\\&\mathrm {\ \ } q[i++]=h\div s;\\&\mathrm {\ \ } t=s;\\&\mathrm {\ \ } s=h\%s;\mathrm {~next~} s\\&\mathrm {\ \ } h=t;\mathrm {~next~} h\\&\}\\&n=i-1;\\&gcd=h;\\\end{aligned}}$$

${\textstyle \mathrm {\ \ \ \ \ \ } }$ Euclidean algorithm - extended variant

The extended Euclidean algorithm is used to determine the unknowns ${\textstyle x}$ and ${\textstyle y}$ after carrying out the base variant of the Euclidean algorithm. This is a necessary previous step, since the extended Euclidean algorithm uses the quotient and remainders computed in the course of executing the steps of the base variant of Euclidean algorithms. The idea of extended Euclidean algorithm is a recursive application of backward substitution based on the steps of the base variant of Euclidean algorithms. This is shown in the next example.
Example - determination of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle x} and ${\textstyle y}$:

$${\begin{aligned}&455x+135y=5\\&\\&\mathrm {~Starting~with~last~but~one~line~of~the~solution~by~the~base~variant~we~get~} \\5&=35-2*15=\\&=35-2*(50-1*35)=-2*50+3*35=\\&=-2*50+3*(135-2*50)=3*135-8*50=\\&=3*135-8*(455-3*135)=-8*455+27*135&\\&\Rightarrow x=-8,y=27\end{aligned}}$$

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ \ \ }} The time complexity

The time complexity of both the base and extended variant of Euclidean algorithm is Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle O((\log h)^2)} , where Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle h} is the number of digits in the smaller number among ${\textstyle a}$ and ${\textstyle b}$.

Fermat–Euler theorem and little Fermat theorem)

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} Euler’s phi function

Definition - Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \phi(n)}
Euler’s phi function, ${\textstyle \phi (n)}$, also called as Euler’s totient function, is defined as the number of integers ${\textstyle k}$ in the range ${\textstyle 1\leq k\leq n}$, for which ${\textstyle k}$ and ${\textstyle n}$ are relatively primes. In other words

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi(n) = |{1<=k<=n \mathrm{~such~that~} (k,n)=1}|,} where Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle |A|} stands for the cardinality of the set Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle A} . Note that ${\textstyle \phi (n)}$ never includes ${\textstyle n}$, sinceFehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (n,n) = n \neq 1} . Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Rightarrow \phi(n) <= n-1.}

Example - Computation of ${\textstyle \phi (10)}$

$${\begin{aligned}&\{{1<=k<=10\mathrm {~such~that~} (k,10)=1}\}=\{1,3,7,9\}\\&\Rightarrow \phi (10)=|{1,3,7,9}|=4.\end{aligned}}$$

The properties of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \phi(n)} can be given as

1. If p is prime then ${\textstyle \phi (p)=p-1}$.
2. If (m,n)=1 then ${\textstyle \phi (m*n)=\phi (m)*\phi (n)}$.
3. If p and q are prime then Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \phi(p*q) = (p-1)*(q-1)}
   

Proof. This property follows from properties 2. and 1.

1. In general ${\textstyle \phi (n)}$ can be expressed by the prime factorisation of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle n} as ${\textstyle \phi (n)=n*\prod _{i=1}^{k}(1-1/p_{i})}$, where ${\textstyle n=\prod _{i=1}^{k}p_{i}^{e_{i}}}$.

The order of congruence classes relative prime to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} , ${\textstyle (\mathbb {Z} /m\mathbb {Z} )^{*}}$ is exactly ${\textstyle \phi (m)}$. If m prime then this order is Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m-1} .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} Fermat–Euler theorem

Fermat–Euler theorem - also called as Euler’s theorem.
If Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} and ${\textstyle n}$ are relatively prime then

$$a^{\phi (n)}\equiv 1\mod n.$$

${\textstyle \mathrm {\ \ \ \ } }$ Fermat’s little theorem

Fermat’s little theorem - If ${\textstyle n}$ is prime and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle n} are relatively prime then

$$a^{p-1}\equiv 1\mod n.$$

Fermat’s little theorem is a special case Fermat–Euler theorem for the case where Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle n} is prime.

Modular multiplicative inverse and its computation

${\textstyle \mathrm {\ \ \ \ } }$ Residue systems modulo ${\textstyle m}$
Definition - Complete system of residues modulo m
The complete system of residues modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} is any set of ${\textstyle m}$ integers so that each element comes from a different congruence class modulo ${\textstyle m}$.
Definition - Least residue system modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m}
Least residue system modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} is the set 0,1,..., m-1.
Definition - Reduced residue system modulo ${\textstyle m}$
Reduced residue system modulo ${\textstyle m}$ is a set obtained from complete system of residues modulo ${\textstyle m}$ by deleting all elements being not coprime with ${\textstyle m}$.

${\textstyle \mathrm {\ \ \ \ } }$ Modular multiplicative inverse of an integer

Definition - Modular multiplicative inverse of an integer ${\textstyle a}$
The modular multiplicative inverse of an integer ${\textstyle a}$, is the integer x that is given by Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ax \equiv 1 \mod m.}

Observe, that not every elements of a complete system of residues modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} has modular multiplicative inverse !
Theorem
An integer ${\textstyle a}$ element of complete system of residues modulo ${\textstyle m}$ has modular multiplicative inverse if and only if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} and ${\textstyle m}$ are relatively prime, in other words if ${\textstyle (a,m)=1}$.
Proof: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{aligned} &ax \equiv 1 \mod m \Leftrightarrow ax + bm = 1\\ &\mathrm{~The~equation~} ax + my = 1 \mathrm{~has~solution~if~and~only~if~} (a,m) = 1. \end{aligned}}

The modular multiplicative inverse of integer ${\textstyle a}$ is denoted by ${\textstyle a^{-1}}$. This can be explained by dividing the relation the relation ${\textstyle ax\equiv 1\mod m}$ formally by Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} . With this notation holds the relation

$$a^{-1}\equiv x\mod m\Leftrightarrow ax\equiv 1\mod m.$$

If exists, the modular multiplicative inverse of an integer ${\textstyle a}$ is determined uniquely
Corollary
If Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} is prime then each of the elements ${\textstyle {1,...,m-1}}$ of the least residue system modulo ${\textstyle m}$ has modular multiplicative inverse.
Proof: Each element of ${\textstyle {1,...,m-1}}$ and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} are relatively primes.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} Computation of the modular multiplicative inverse

The modular multiplicative inverse of an integer ${\textstyle a\mod m,(a,m)=1}$ can be computed on the following ways.

• Computation way 1. - by using the extended Euclidean algorithm

  $$ax\equiv 1\mod m\Leftrightarrow ax+bm=1.$$

  Due to ${\textstyle (a,m)=1}$ the equation ${\textstyle ax+bm=1}$ has solution. ${\textstyle \Rightarrow }$ Solving the equation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle ax + bm = 1} by the extended Euclidean algorithm, ${\textstyle x}$ gives the modular multiplicative inverse of an integer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a \mod m} .

• Computation way 2. - by means of efficient computation of raising an integer to a higher power, using a formula based on Euler’s theorem

  $$a^{\phi (n)-1}*a\equiv 1\mod n\Rightarrow a^{-1}\equiv a^{\phi (n)-1}\mod n$$
  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \Rightarrow} The the modular multiplicative inverse of an integer ${\textstyle a\mod m}$ are given by ${\textstyle a^{\phi (n)-1}\mod n}$, which can be determined by efficient computation of a modular multiplicative inverse - by using exponentiation by squaring.

${\textstyle \mathrm {\ \ \ \ } }$ Modular exponentiation by squaring

Modular exponentiation is raising an integer to a higher power modulo ${\textstyle n}$, in other words computing Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g^e \mod n} . Exponentiation by squaring is an efficient computation of modular exponentiation. The idea of exponentiation by squaring is to compute Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g^e \mod n} by the help of successive squares of ${\textstyle g}$. This can be implemented as follows.

• Rearrange ${\textstyle g^{e}}$ by using the binary representation of ${\textstyle e}$
  $$g^{e}=g^{(\sum _{i=0}^{k}e_{i}*2^{i})}=\prod _{i=0}^{k}g^{e_{i}*2^{i}}.$$
  ${\textstyle \Rightarrow }$ Only those terms of the product must be computed, for which Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle e_i=1} , since for ${\textstyle e_{i}=0}$ the term ${\textstyle g^{e_{i}*2^{i}}}$ becomes ${\textstyle g^{0*2^{i}}=1}$. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \Rightarrow} The terms with Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle e_i=1} becomes powers of ${\textstyle g}$ as ${\textstyle g^{2^{i}}}$.
• Computation of the powers Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g^{2^i}} successively by applying
  $$g^{2^{l+1}}=(g^{2^{l}})^{2}\mathrm {~for~} l>=0$$
• Computate each term with mod ${\textstyle n}$.

Example - Exponentiation by squaring

$${\begin{aligned}&3^{52}\mod 100\\&\\&52=110100=2^{2}+2^{4}+2^{5}\\&3^{(2^{0})}=3\\&3^{(2^{1})}=3^{2}=9\\&3^{(2^{2})}=9^{2}=81\\&3^{(2^{3})}=81^{2}\mod 100=61\\&3^{(2^{4})}=61^{2}\mod 100=21\\&3^{(2^{5})}=21^{2}\mod 100=41\\&\\&3^{52}\mod 100=81*21*41\mod 100=41.\end{aligned}}$$

${\textstyle \Rightarrow }$ Conclude that instead of 52 multiplications only 5 squaring and 3 multiplications were needed.

Discrete logarithm

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \mathrm{\ \ \ \ }} Primitive root modulo m

Definition - primitive root modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m}
The number ${\textstyle g}$ is primitive root modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} if for every integer ${\textstyle a}$ being coprime to ${\textstyle m}$ (i.e. ${\textstyle (a,m)=1}$) there is an integer ${\textstyle k}$ for which ${\textstyle g^{k}\equiv a\mod n}$.
Interpretation
All elements of the set of congruence classes coprime to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle n} , ${\textstyle (\mathbb {Z} /m\mathbb {Z} )^{*}}$ can be generated by power of ${\textstyle g}$ modulo ${\textstyle m}$. Therefore

• ${\textstyle g}$ is also called as generator of the set of congruence classes coprime to ${\textstyle m}$ and
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g} must be coprime to ${\textstyle m}$.

Definition - Multiplicative order of primitive root modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m}
The multiplicative order of primitive root modulo ${\textstyle m}$ is the lowest power of a which is congruent to ${\textstyle 1}$ modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} .
Statement The multiplicative order of primitive root modulo ${\textstyle m}$ is ${\textstyle \phi (m)}$.

This is because

• this power of a is congruent to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle 1} modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle n} , since ${\textstyle a^{\phi (m)}\equiv 1\mod n}$ due to Euler’s theorem and
• this is the lowest power as the other lower powers are needed to generate the other elements of the set ${\textstyle (\mathbb {Z} /m\mathbb {Z} )^{*}}$.

It follows that if ${\textstyle m}$ is prime then the multiplicative order Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \phi(m) = m-1} .

Note that not all elements of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (\mathbb{Z}/m\mathbb{Z})^*} are primitive root modulo m ! However the non-primitive root modulo ${\textstyle m}$ elements are cyclic generator of a subset of ${\textstyle (\mathbb {Z} /m\mathbb {Z} )^{*}}$. The non-primitive root elements of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (\mathbb{Z}/m\mathbb{Z})^*} have also multiplicative order, which is can be however less then ${\textstyle \phi (m)}$.
Example - ${\textstyle m=7}$ prime

$${\begin{aligned}&(\mathbb {Z} /7\mathbb {Z} )^{*}-\mathrm {~least~residue~system~modulo~} 7={0,1,...,6}\mathrm {~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\&\mathrm {~~The~elements~} 3\mathrm {~and~} 4\mathrm {~are~primitive~root~modulo~} m.\\&\mathrm {~~For~example~the~element~} 2\mathrm {~is~not~primitive~root~modulo~} m!\\&\mathrm {~~} \Rightarrow \mathrm {~~Multiplicative~order~of~} 2\mathrm {~is~} 3<\phi (7)=6,\mathrm {~since~} 2^{3}\equiv 1\mod 7.\end{aligned}}$$

${\textstyle \mathrm {\ \ \ \ } }$ Discrete logarithm to the base ${\textstyle g}$ modulo ${\textstyle m}$
Definition - Discrete logarithm (also called index)
Discrete logarithm, also called index When Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a=g^k \equiv a \mod m} then the Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle k} is called as discrete logarithm of the integer ${\textstyle a}$ to the base ${\textstyle g}$ modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} . Here ${\textstyle g}$ is primitive root modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} , and ${\textstyle a}$ is an element of ${\textstyle (\mathbb {Z} /m\mathbb {Z} )^{*}}$, i.e. ${\textstyle a}$ coprime to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m} .

The practical importance of the discrete logarithm lies in its property that computation of discrete logarithm is believed to be difficult to perform, especially for some specific groups.

Application to cryptography

${\textstyle \mathrm {\ \ \ \ } }$ RSA cryptography

RSA is a cryptosystem, called after its developers: Rivest, Shamir and Adleman. The principle of the key generation can be described by means of the following steps.

• Step 1. Select large primes ${\textstyle p}$ and ${\textstyle q}$, e.g. each of them with size ${\textstyle 512}$ bits.
• Step 2. Compute ${\textstyle n=p*q}$
• Step 3. Compute ${\textstyle \phi (n)=(p-1)*(q-1)}$
• Step 4. Select a random integer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle 1 < e < \phi(n)} , such that ${\textstyle e}$ is coprime to ${\textstyle \phi (n)}$
• Step 5. Determine an integer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle 1 < d < \phi(n)} , such that Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle e*d \mod \phi(n) = 1} , i.e. ${\textstyle d}$ is modular multiplicative inverse of ${\textstyle e}$.
  

${\textstyle \Rightarrow }$ The integer ${\textstyle d}$ can be computed

• • either by using the extended Euclidean algorithm
  • or by the help of Euler’s theorem and using exponentiation by squaring.

The keys are called as

• private key = d
• public keys = e, n

Secret parameters of the key generation: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p, q, \phi(n)} .

The usage of RSA for encryption can be explained as

• Notation: ${\textstyle m}$ = message, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle c} = chipertext - both in form natural numbers
• Condition: ${\textstyle m<n}$ - needed for the correct decryption, see below.
• The encryption end decryption processes
  • The encryption
    $$c=m^{e}\mod n,$$
  • The decryption
    $$m'=c^{d}\mod n$$

The correctness of the RSA cryptographic algorithm can be shows by showing Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m'=m}

Proof: Using the way of generation of ${\textstyle d}$ we have

$$e*d\mod \phi (n)=1\Rightarrow e*d=1+k*\phi (n)$$

By using it, the decrypted chipertext ${\textstyle m'}$ can be rearranged as Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{aligned} m' &= c^d\mod n = (m^e)^d\mod n = m^{e*d}\mod n = m^{1 + k*\phi(n)}\mod n =\\ &= [(m^1\mod n) * ((m^{\phi(n)})^k\mod n)]\mod n = \\ & \mathrm{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \uparrow \mathrm{~condition~} m < n \\ &= [m * ((m^{\phi(n)} \mod n)^k) \mod n] \mod n = \\ &\mathrm{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \uparrow \mathrm{~Euler's~theorem~}\\ &= (m * 1) \mod n = m \\ &\mathrm{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \uparrow \mathrm{~condition~} m < n. \end{aligned}}

Note, that proof of correctness is also possible by using Fermat’s little theorem utilizing the fact that ${\textstyle n=p*q}$, i.e. multiplication of two primes.

RSA can be used both for

• encryption and
• authentication,

in both cases including key distribution. Proof of correctness for using RSA for authentication can be shown similar to that one provided for the case of using it for encryption.

The secrecy of RSA is based on the computational difficulty of prime factorization.
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \Rightarrow} If n could be factorized on efficient way then the secrecy of RSA would be broken !!

${\textstyle \mathrm {\ \ \ \ } }$ Diffie–Hellman key exchange

Diffie–Hellman key exchange is a protocol for secure key distribution. The principle of the solution is to generate the common secret key without exchanging the key itself. This is achieved on the way that each party shares only a partial info on the key to be generated.

The Diffie-Hellman key establishment protocol can be described by the following steps.

• Step 1. The parties A and B agree on a prime ${\textstyle p}$ and a natural number Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle 1 < g < p} , which is a primitive root modulo ${\textstyle p}$.
• Step 2. Each party selects a secret number ${\textstyle \alpha <p-1}$ and ${\textstyle \beta <p-1}$, and computes the power ${\textstyle a=g^{\alpha }\mod p}$ and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle b = g^{\beta} \mod p} , respectively.
• Step 3. Each party sends ${\textstyle a}$ and ${\textstyle b}$ to the other party.
• Each party computes the common secret key Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle k} based on the received numbers ${\textstyle a}$ and ${\textstyle b}$ as ${\textstyle k=a^{\beta }\mod p}$ and ${\textstyle k=b^{\alpha }\mod p}$.

Keys arising in the key exchange protocol are classified as

• Public keys: ${\textstyle p,g,a}$ and ${\textstyle b}$
• Private keys: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \alpha} and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \beta}

The operation way of the Diffie-Hellman key exchange protocol is shown in Figure 1.

[[File:./figs/Diffie-Hellman_key_exchange.pdf]]

The equality of the keys generated on the different sides can be shown as follows.

$${\begin{aligned}a^{\beta }\mod p&=(g^{\alpha })^{\beta }\mod p=g^{\alpha *\beta }\mod p=\\&=(g^{\beta })^{\alpha }\mod p=b^{\alpha }\mod p\\\end{aligned}}$$

The secrecy of Diffie-Hellman key exchange protocol is based on the computational difficulty of the discrete logarithms, more precisely on determining ${\textstyle \alpha }$ from Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a = g^{\alpha} \mod p} or ${\textstyle \beta }$ from ${\textstyle b=g^{\beta }\mod p}$ in the knowledge of ${\textstyle g}$ and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a} or Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle b} and ${\textstyle p}$.

Combinatorics

For an introduction to basics of combinatorics see Permutation and Combination.

Relations

For an introduction and overview on mathematical relations see Relation.