Properties of modulo operation:
\(\forall a, b \in \mathbb{N}_{0}, m \in \mathbb{N}\):
- \(0 \le { \left( a \mod m \right) } \le m-1 \)
- \({ \left( a \mod m \right) } \mod m = a \mod m \)
- \(\left( a \cdot b \right) \mod m\) \(=\) \(\left( \left( a \mod m \right) \cdot \left( b \mod m \right) \right) \mod m\).
Lemma “About finiteness of modular-power sequence”
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\), \(i = \overline{2, m}\).
Then for the given sequence the condition of repeat is satisfied:
\(\exists i \in {\mathbb{N}_{0}}\), \(j \in \mathbb{N}\), \(0 \le i < j \le m\):
\(a_{i}\) \(=\) \(a_{j}\).
Periodicity of modular exponentiation
Let’s prolong the earlier-observed sequence to the infinite length, and further we will be observing only the gotten sequence \(\{ a_{i} \}_{i=0}^{+\infty}\), defined by the following law:
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\), \(i = \overline{2, +\infty}\), where \(m \in \mathbb{N}\), \(m \ge 2\) – certain module, \(a \in \{ 0, 1, \ldots, m-1 \}\).
Let’s call this sequence a modular-power sequence with module \(m\) and basis number \(a\).
Due to the lemma about of finiteness of modular-power sequence (further – MSP), we have, that for the first \(m\) elements the condition of repeat: \(\exists i \in {\mathbb{N}_{0}}\), \(j \in \mathbb{N}\), \(0 \le i < j \le m\): \(a_{i}\) \(=\) \(a_{j}\).
So, suppose given indexes \(i\) and \(j\), for which ones this condition is satisfied. Due to the definition of the sequence it follows that \(a_{i+1} = \left(a_{i} \cdot a \right) \mod m\), and similarly \(a_{j+1}\) \(=\) \(\left(a_{j} \cdot a \right) \mod m\). However due to \(a_{i}\) \(=\) \(a_{j}\), we have that \(a_{j+1}\) \(=\) \(\left(a_{j} \cdot a \right) \mod m\) \(=\) \(\left(a_{i} \cdot a \right) \mod m\) \(=\) \(a_{i+1}\). So, \(a_{i+1}\) \(=\) \(a_{j+1}\). Similarly can be shown, that \(a_{i+2}\) \(=\) \(a_{j+2}\), \(a_{i+3}\) \(=\) \(a_{j+3}\), and in general \(\forall t \in \mathbb{N}_{0}\) \(a_{i+t}\) \(=\) \(a_{j+t}\).
So, suppose a given MPS \(\{ a_{i} \}_{i=0}^{+\infty}\) with module \(m\) and basis number \(a\).
Theorem “About period of MPS”
Suppose a given MPS \(\{ a_{i} \}_{i=0}^{+\infty}\) with module \(m\) and a basis number \(a\), and also suppose defined \(i\) and \(j\) – the beginning of period and the first point of repeat respectively. Then period \(p\) of given sequence exists, and can be found with formula \(p = j – i\).
Let’s take one of the facts from the meant above reasonings: \(\forall t \in \mathbb{N}_{0}\) \(a_{i+t}\) \(=\) \(a_{j+t}\). Let’s set a number \(p = j-i\) and show, that it is a period of the sequence.
The case \(a_{i+t}\) \(=\) \(a_{i+p+t}\) is obvious, because \(a_{i}\) \(=\) \(a_{j}\). Let’s view the equality \(a_{i+t} = a_{i+p+t}\) when \(t = kp\), \(k = \overline{0, +\infty}\):
\(a_{i} = a_{i+p}\),
\(a_{i+p} = a_{i+2p}\),
\(a_{i+2p} = a_{i+3p}\),
\(a_{i+3p} = a_{i+4p}\),
\(\ldots\),
\(a_{i+ \left( k-1 \right) p} = a_{i+kp}\),
\(\ldots\)
It’s obvious, that \(a_{i}\) \(=\) \(a_{i+p}\) \(=\) \(a_{i+2p}\) \(=\) \(a_{i+3p}\) \(=\) \(\ldots\) \(=\) \(a_{i+kp}\) \(=\) \(\ldots\). Then \(\forall k_{0} \in \mathbb{N}_{0}\): \(a_{i} = a_{i+k_{0}p}\).
Further, due to the definition of sequence we have, that \(a_{i+1} = a_{i+k_{0}p+1}\), \(a_{i+2} = a_{i+k_{0}p+2}\), \(\ldots\) \(a_{i+p-1} = a_{i+k_{0}p+p-1}\), id est: \(\forall t_{0} \in \{ 0, \ldots, p-1 \}\) \(a_{i+t_{0}} = a_{i+k_{0}p+t_{0}}\). Therefore, according to the definition, the number \(p\) is a period of modular-power sequence. Theorem is proven.
Practical application, the main formula of period of MPS
Basing on the mentioned above theory it’s obvious, that modular exponentiation has a periodicity property. So, suppose for a certain MPS \(\{ a_{i} \}_{i=0}^{+\infty}\) with module \(m\) and a basis number \(a\) the beginning of period \(i\) and the first point of repeat \(j\) are found. Then period of a given sequence, as it has been shown in the theorem, will be equal to \(p = j-i\). Let’s find the first \(j\) elements of the sequence:
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{k}\) \(=\) \(\left( a_{k-1} \cdot a \right) \mod m\) \(=\) \(a^{k} \mod m\), \(k = \overline{2, j-1}\), among which ones:
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\).
We know, that with indexes greater or equal \(i\) elements of the sequence will begin to repeat values of the elements, which we have found. Therefore…
The main formula of period
Suppose a given MPS \(\{ a_{i} \}_{i=0}^{+\infty}\) with module \(m\) and a basis number \(a\), the beginning of period \(i\) and period \(p\). Then for any power \(T \in \mathbb{N}_{0}\), \(T \ge i\) the following formula is valid:
\(a^{T} \mod m\) \(=\) \(a^{\left( T-i \right) \mod p + i} \mod m\).
In the case when \(0 \le T < i\) the value \(a^{T}\) can be taken from the MPS: \(a_{T}\) \(=\) \(a^{T}\).
This formula is a consequence of the mentioned theorem. Due to during the exponentiation of number beginning from index of beginning of period \(i\) elements with indexes \(i+t\) and \(i+kp+t\), \(\forall k \in \mathbb{N}_{0}\), \(\forall t \in \{0, \ldots, p-1 \}\) are equal, by subtracting from power \(T \ge i\) the beginning of period \(i\) and by applying modulo \(p\) and adding \(i\), we’re returning the number into the limits of elements \(a_{k}\) \(=\) \(\left( a_{k-1} \cdot a \right) \mod m\) \(=\) \(a^{k} \mod m\), \(k = \overline{i, i+p-1}\).
In this way with finding the index of the beginning of period and the period itself with way of building of the respective elements of MPS for a certain basis number \(a\), we’ll get a possibility to modularly exponentiate this number \(a\) into any non-negative degree immediately. At least, with help of a processing device.
Also there can be made a generalization of modular exponentiation up to any integral number \(A \in \mathbb{Z}\):
\(A \mod m = sign(A) \cdot a\), \(a \ge 0\), тогда \(\forall T \in \mathbb{N}_{0}\) \(A^{T} \mod m = \left( sign(A)^{\left( T \mod 2 \right) } \cdot a^{\left( \left( T-i \right) \mod p + i \right)} \right) \mod m\).
Power congruence equations
The obtained information can be used for solution of the power congruence equations of this kind:
\(a^{x} \equiv b \left( \mod m \right)\), where \(x \in \mathbb{N}_{0}\) – an unknown variable, \(a\), \(b\) \(\in \mathbb{N_{0}}\) – known coefficients, \(m\) – module of equation.
Let’s build an MPS \(\{ a_i \}_{i=0}^{m}\):
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\), \(i = \overline{2, m}\).
This procedure takes \(O \left( m \right)\) of operations. Let’s find the first point of repeat \(i\) and the period \(p\), what also takes \(O \left( m \right)\).
With help of MPS we look over the \(x\) from a set \(\{ 0, 1, \ldots, i+p-1 \}\), and corresponding to them \(a_x = a^x\). Suppose \(i\) – the first point of repeat, \(p\) – the period, and \(x_{0}\) – partial solution of equation from the set \(\{ 0, 1, \ldots, i+p-1 \}\), found with the brute force look over. If \(x_{0} < i\), then we add the value \(x_{0}\) into the set of answers, otherwise if \(x_{0} \ge i\), we add values \(x_{0}+kp\), \(k \in \mathbb{N}_{0}\) into the set of answers.
Double-power exponentiation
Basing on the similar reasonings, this theory can be completed to the case of s-ary double/multiplied power:
Suppose a given the first power/power multiplier \(s \in \mathbb{N}\), a certain module \(m \in \mathbb{N}\), \(m \ge 2\) and a certain number \(a \in \{ 0, 1, \ldots, m-1 \}\). Let’s build a sequence of elements:
\(a_{0}\) \(=\) \({ \left( a^s \right) }^0 \mod m\) \(=\) \(a^{s \cdot 0} \mod m\) \(=\) \(a^{0} \mod m\) \(=\) \(1\),
\(a_{1}\) \(=\) \({ \left( a^{s} \right) }^1 \mod m\)\(=\) \(a^{s \cdot 1} \mod m\) \(=\) \(a^{s} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a^{s} \right) \mod m\) \(=\) \({{\left( a^s \right)}^i} \mod m\) \(=\) \(a^{si} \mod m\), \(i = \overline{2, +\infty}\).
Similarly, for this sequence the existence of two equal elements among the first \(m\) of them is being proven and the concepts of beginning of period \(i\), the first point of repeat \(j\) and period \(p\) are being defined:
\(i\), \(j\) – the least indexes, which satisfy: \(i \in {\mathbb{N}_{0}}\), \(j \in \mathbb{N}\), \(0 \le i < j \le m\), \(a_{i}\) \(=\) \(a_{j}\);
\(p\): \(\forall k \in \mathbb{N}_{0}\), \(\forall t \in \{0, \ldots, p-1 \}\) \(a_{i+t}\) \(=\) \(a_{i+kp+t}\).
The main formula of period will also stay valid, but with changes: \(\forall T \ge i\), \(T \in \mathbb{N}_{0}\),
\({\left( a^s \right) }^{T} \mod m\) \(=\) \(a^{sT} \mod m\) \(=\) \({ \left( a^s \right) }^{\left( T-i \right) \mod p + i} \mod m\) \(=\) \({a^{s \left( {\left( T-i \right) \mod p + i} \right) }} \mod m\).
Repeated-power exponentiation
Let’s take a look at one more kind of modular sequences – sequence with repeated powers.
Suppose a given modulo \(m \in \mathbb{N}\), \(m \ge 2\), basis number of sequence \(a \in \{ 0, \ldots, m-1 \}\), and the amount of repeats of power \(r \in \mathbb{N}\), \(r \ge 2\). Then let’s name modular sequence with module \(m\), basis number \(a\) and repeated power \(r\) the following sequence \(\{ a_{i} \}_{i = 0}^{+\infty}\), defined with the following laws:
\(a_{0}\) \(=\) \(a \mod m\),
\(a_{i}\) \(=\) \(a_{i-1}^{r} \mod m\), \(i = \overline{1, +\infty}\).
All the previous reasonings are also being moved on this kind of sequences. This time let’s show only the last result: if \(p\) is the period of sequence with defined parameters \(m\), \(a\), \(r\) and \(i\) is the beginning of this period, then: \(\forall T \ge i\), \(T \in \mathbb{N}_{0}\):
\(a_{T} = a_{(T-i) mod p+i}\).