In the RSA algorithm in the previous chapter, we see that the decomposition of large prime factors constitutes the basis of RSA cryptosystem security. Theoretically, this security should not be questioned, because there is only the definition of prime in mathematics, and there is no general method to detect prime. The main purpose of this chapter is to introduce some basic prime test methods, including Fermat test, Euler test, Monte Carlo method, continued fraction method, etc., understanding the content of this chapter requires some special number theory knowledge.
5.1 Fermat Test
According to Fermat’s congruence theorem (commonly known as Fermat’s small theorem, which is a special case of Euler congruence theorem), if n is a prime number, the following congruence formula holds for all integers b, \((b,n)=1\),The above formula is an important characteristic of prime numbers. Although n satisfying the above formula is not necessarily prime, it can be used as an important basis for detecting prime numbers, because we can conclude that n not satisfying the above formula is definitely not a prime number. Using Formula (5.1) as the standard to detect prime numbers is called Fermat test.
$$\begin{aligned} b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n). \end{aligned}$$
(5.1)
Advertisement
Definition 5.1
An odd number n, assuming that n is a compound number (not a prime number) and there is a positive integer b, \((b,n)=1\), satisfyingthe compound number n is called a Fermat pseudo prime under base b.
$$\begin{aligned} b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n), \end{aligned}$$
The basic properties of pseudo prime numbers are discussed. Our working platform is a finite Abel group \(\mathbb {Z}_{n}^{*}\), define aswhere \(\bar{a}\) is a congruence class of \({{\,\mathrm{mod}\,}}n\) represented by a. The multiplication of two congruence classes is defined as \(\bar{a}\cdot \bar{b}=\bar{ab}\); obviously, \(\mathbb {Z}_{n}^{*}\) forms an Abel group of order \(\varphi (n)\) under multiplication, in a finite group G, the order of a group element \(g \in G\) is defined as\(o(g)=1\) if and only if g is the unit element of group G. By the definition of o(g), obviously,The following two lemmas are the basic conclusions about the order of group element g.
$$\begin{aligned} \mathbb {Z}_{n}^{*}=\{\bar{a}|1\le a \le n,(a,n)=1\}, ~n>1, \end{aligned}$$
(5.2)
$$\begin{aligned} o(g)=\min \{m:g^{m}=1,1\le m \le |G|\}. \end{aligned}$$
$$\begin{aligned} g^{t}=1 \Leftrightarrow o(g)|t. \end{aligned}$$
(5.3)
Lemma 5.1
G is a finite group, \(g \in G\), \(k \in \mathbb {Z}\) is an integer, thenwhere the denominator is the greatest common divisor of k and o(g).
$$\begin{aligned} o(g^{k})=\frac{o(g)}{(k,o(g))}, \end{aligned}$$
(5.4)
Proof
Let \(o(g)=m\), \(o(g^{k})=t\), obviously, \((g^{k})^{m}=1\), in particular,On the other hand, by \(g^{kt}=1\), there is m|kt, thusSo we have \(t=\frac{m}{(k,m)}\), the Lemma holds.
$$\begin{aligned} g^{\frac{k\cdot m}{(k,m)}}=1, \Longrightarrow t \left| \frac{m}{(k,m)} \right. . \end{aligned}$$
$$\begin{aligned} \frac{m}{(k,m)}\left| \frac{k}{(k,m)}t, \Longrightarrow \frac{m}{(k,m)}\right| t. \end{aligned}$$
Advertisement
Lemma 5.2
Suppose G is a finite Abel group, \(a, b \in G\), \((o(a), o(b))=1\), then
$$\begin{aligned} o(ab)=o(a)o(b). \end{aligned}$$
Proof
Let \(o(a)=m_{1}\), \(o(b)=m_{2}\), then \((m_{1},m_{2})=1\). Let \(o(ab)=t\), by \((ab)^{m_{1}m_{2}}=a^{m_{1}m_{2}}b^{m_{1}m_{2}}=1\), there is \(t|m_{1}m_{2}\), on the other hand, \((ab)^{t}=1\), then \((ab)^{tm_{1}}=1\), thus \(b^{tm_{1}}=1\), \(m_{2}|m_{1}t\), \(m_{2}|t\). By the same reason, there is \( m_{1}|t\), thus \(m_{1}m_{2}|t\), \(t=m_{1}m_{2}\). The Lemma holds.
Back to the finite group \(\mathbb {Z}_{n}^{*}\), any integer \(a \in \mathbb {Z}\), \((a,n)=1\), then \(\bar{a} \in \mathbb {Z}_{n}^{*}\), we denote \(o(\bar{a})\) with o(a), a is called the order \({{\,\mathrm{mod}\,}}n\), obviously, \(o(a)=o(b)\), if \(a\equiv b({{\,\mathrm{mod}\,}}n)\). A basic problem in number theory is the existence of primitive roots of \({{\,\mathrm{mod}\,}}n\). equivalently, is \(\mathbb {Z}_{n}^{*}\) a cyclic group? If there is a positive integer a, \((a,n)=1\), \(o(\bar{a})=|\mathbb {Z}_{n}^{*}| =\varphi (n)\), then \(\mathbb {Z}_{n}^{*}\) is a cyclic group of order \(\varphi (n)\), so that the primitive root of \({{\,\mathrm{mod}\,}}n\) exists and a is the primitive root of \({{\,\mathrm{mod}\,}}n\).
Lemma 5.3
(Existence of primitive root) If and only if \(n=2\), 4, \(p^{\alpha }(\alpha \ge 1)\) and \(a=2p^{\alpha }(\alpha \ge 1)\) four cases, the primitive root of \({{\,\mathrm{mod}\,}}n\) exists, where \(p>2\) is an odd prime.
Proof
If \(n=2\), 4, then the lemma holds. If \(n=p\), then \(\mathbb {Z}_{n}=\mathbb {F}_{p}\), \(\mathbb {Z}_{n}^{*}=\mathbb {F}_{p}^{*}\), by Lemma 4.7 of Chap. 4, it can be seen that \(\mathbb {F}_{p}^{*}\) is a cyclic group of order \((p-1)\), so \({{\,\mathrm{mod}\,}}p\) has primitive roots. Now, we need to prove for all positive integer \(\alpha \), the primitive root of \({{\,\mathrm{mod}\,}}p^{\alpha }\) also exists. Therefore, let a be a primitive root of \({{\,\mathrm{mod}\,}}p\), that is, the order of a \({{\,\mathrm{mod}\,}}p\) is \(p-1\). If the order of \(a {{\,\mathrm{mod}\,}}p^{\alpha }\) is denoted by o(a), thenso there is \(p-1|o(a)\). And the number of elements of \(\mathbb {Z}^{*}_{p^{\alpha }}\) is \(\varphi (p^{\alpha })=p^{\alpha -1}(p-1)\), obviously, \(o(a)|p^{\alpha -1}(p-1)\), thus, \(o(a)=p^{i}(p-1)\), \(0\le i\le \alpha -1\).
$$\begin{aligned} a^{o(a)}\equiv 1({{\,\mathrm{mod}\,}}p^{\alpha }), \Longrightarrow a^{o(a)}\equiv 1({{\,\mathrm{mod}\,}}p), \end{aligned}$$
We might as well let \(o(a)=p-1\), if \(o(a)=p^{i}(p-1)\),\(1\le i\), then replace a with \(a^{p^{i}}\). By Lemma 5.1,Therefore, without losing generality, let \(o(a)=p-1\), then by Sylow theorem, when \(\alpha >1\), \(p^{\alpha -a}|\varphi (p^{\alpha })\), there is an integer b, \((b,n)=1\), b is \(o(n)=p^{\alpha -1}\) in the order of \({{\,\mathrm{mod}\,}}p^{\alpha }\), because of \((o(a),o(b))=1\), then by Lemma 5.2, there isSo the primitive root of \({{\,\mathrm{mod}\,}}p^{\alpha }\) exists.
$$\begin{aligned} o(a^{p^{i}})=\frac{p^{i}(p-1)}{(p^{i},p^{i}(p-1))}. \end{aligned}$$
$$\begin{aligned} o(ab)=o(a)o(b)=p^{\alpha -1}(p-1)=\varphi (p^{\alpha }), \end{aligned}$$
When \(n=2p^{\alpha }\), \(p>2\) is odd prime, then \(\varphi (n)=\varphi (p^{\alpha })\). Thus, the primitive root a of \({{\,\mathrm{mod}\,}}p^{\alpha }\) is also an primitive root of \({{\,\mathrm{mod}\,}}2p^{\alpha }\). The Lemma holds.
Lemma 5.4
Let n be an odd compound number, then
(i)
\(b\ge 1\) is a positive integer, \((b,n)=1\), n is Fermat pseudo prime under base b if and only if \(o(b)|n-1.\)
(ii)
n is Fermat pseudo prime under bases \(b_{1}\) and \(b_{2}\), then it is Fermat pseudo prime under bases \(b_{1}b_{2}\) and \(b_{1}b_{2}^{-1}\), where \(b_{2}^{-1}\) is the multiplicative inverse of \(b_{2} {{\,\mathrm{mod}\,}}n \).
Proof
(i) and (ii) are trivial. (i) can be obtained by (5.3). And \(b_{1}\), \(b_{2}\in \mathbb {Z}_{n}^{*}\),So there is (ii). To prove (iii). Let n not be Fermat pseudo prime to base b, if n is Fermat pseudo prime to base a, then n is not Fermat pseudo prime to base ab. By (ii), therefore, if there is a base to make n a Fermat pseudo prime number, there must be a base to make n not a Fermat pseudo prime number, so more than half of the base b must make n not a Fermat pseudo prime number. The Lemma holds.
$$\begin{aligned} {\left\{ \begin{aligned}&b_{1}^{n-1}\equiv 1 ({{\,\mathrm{mod}\,}}n), b_{2}^{n-1} \equiv 1({{\,\mathrm{mod}\,}}n). \Longrightarrow (b_{1}b_{2})^{n-1} \equiv 1({{\,\mathrm{mod}\,}}n).\\&b^{n-1}\equiv 1 ({{\,\mathrm{mod}\,}}n), \Longrightarrow (b^{-1})^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n). \end{aligned} \right. } \end{aligned}$$
By Lemma 5.3, if there is a base b so that n is not Fermat pseudo prime, detect a, \(1\le a\le n\), \((a,n)=1\) in sequence, whether \(a^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n)\); that is, there is more than \(50 \% \) chance that find the exact b such that \(b^{n-1}\not \equiv 1 ({{\,\mathrm{mod}\,}}n)\), this proves that n is not a prime number. Is it possible that all a, \(1\le a\le n\), \((a,n)=1\), n is Fermat pseudo prime to base a The answer is yes, such a number n is called Carmichael number.
Definition 5.2
A Carmichael number n is an odd compound number, and for \(\forall ~ b \in \mathbb {Z}^{*}_{n}\), there is
$$\begin{aligned} b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n). \end{aligned}$$
For Carmichael number, we have the following engraving.
Theorem 5.1
Let n be a compound number, then
(i)
If there is an integer \(a>1\), \(a^{2}|n\), then n is not a Carmichael number.
(ii)
Assuming that n is a square free number, then n is a Carmichael number \(\Leftrightarrow \) for all prime p, p|n, there is \(p-1|n-1\).
(iii)
A Carmichael number is the product of at least three different prime numbers.
Proof
Let’s prove (i) first. Let \(p^{2}|n\), p be a prime number, by Lemma 5.3, \({{\,\mathrm{mod}\,}}p^{2}\) has primitive roots. Let g be an original root of \({{\,\mathrm{mod}\,}}p^{2}\), that is \(o(g)=p(p-1)\), letAccording to the Chinese remainder theorem, there is a positive integer b such thatThen b is an primitive root of \({{\,\mathrm{mod}\,}}p^{2}\), and \((b,n)=1\). We assert that n to base b is not a Fermat pseudo prime. If n to base b is a Fermat pseudo prime, thenThat is \(p(p-1)|n-1\), but p|n is contradict with \(p|n-1\). So \(b^{n-1}\not \equiv 1({{\,\mathrm{mod}\,}}n)\), n is not Carmichael number, (i) holds.
$$\begin{aligned} n'=\prod _{p'|n,p'\ne p }{p'}, ~p'~\text {is a prime number}. \end{aligned}$$
$$\begin{aligned} {\left\{ \begin{aligned}&b\equiv g({{\,\mathrm{mod}\,}}p^{2}),\\&b\equiv 1({{\,\mathrm{mod}\,}}n'). \end{aligned} \right. } \end{aligned}$$
$$\begin{aligned} b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n), \Longrightarrow b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}p^{2}), \Longrightarrow o(b)|n-1. \end{aligned}$$
Now to prove (ii). If \(\forall ~ p, p|n\), there is \(p-1|n-1\), then \( \forall ~ b \in \mathbb {Z}_{n}^{*}\),Because n is a square free number, soTherefore, n is the Carmichael number. Conversely, if there is a prime number p, p|n, but \(p-1\not \mid n-1\), Let g be a primitive root of \({{\,\mathrm{mod}\,}}p\), which is given by the Chinese remainder theorem,Then \((b,n)=1\), andBy \(p-1\not \mid n-1\), then \(g^{n-1}\not \equiv 1({{\,\mathrm{mod}\,}}p)\), so there is \(b^{n-1}\not \equiv 1({{\,\mathrm{mod}\,}}n)\), this contradicts with the assumption that n is the Carmichael number. So (ii) holds.
$$\begin{aligned} b^{n-1}=(b^{\frac{n-1}{p-1}})^{p-1}\equiv 1({{\,\mathrm{mod}\,}}p), \forall ~ p|n. \end{aligned}$$
$$\begin{aligned} b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n),\ \forall ~ b\in \mathbb {Z}_{n}^{*} . \end{aligned}$$
$$\begin{aligned} {\left\{ \begin{aligned}&b\equiv g({{\,\mathrm{mod}\,}}p),\\&b\equiv 1 \left( {{\,\mathrm{mod}\,}}\frac{n}{p}\right) . \end{aligned} \right. } \end{aligned}$$
$$\begin{aligned} b^{p-1}\equiv g^{p-1}\equiv 1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
To prove (iii), we just need to exclude that n is the product of two prime numbers. By (ii), let \(n=pq\), \(p<q\), if n is a Carmichael number, then \(q-1\mid n-1\), but \(n-1=p(q-1+1)-1=p(q-1)+p-1\), thenthis contradicts with \(n-1 \equiv 0({{\,\mathrm{mod}\,}}q-1)\), so \(n=pq\) must not be a Carmichael number, the Theorem holds.
$$\begin{aligned} n-1\equiv p-1({{\,\mathrm{mod}\,}}q-1), \end{aligned}$$
Below we give some examples of Carmichael numbers, from property (ii) in Theorem 5.1, we can easily verify whether a square free number is Carmichael number.
Example 5.1
The following positive integers n are Carmichael numbers,
$$\begin{aligned}&n=1105=5\cdot 13\cdot 7, n=1729=1\cdot 13\cdot 19, n=2465=5\cdot 17\cdot 29,\\&n=2821=7\cdot 13\cdot 31,n=6601=7\cdot 23\cdot 41. \end{aligned}$$
Example 5.2
The positive integer \(561=3\cdot 11\cdot 17\) is the smallest Carmichael number.
Proof
Defined by, the Carmichael number is odd and compound, so the minimum Carmichael number isLet \(p=5, p=7\), the congruence equationhas no prime solution q, when \(p=11\), the above formula has a minimum solution \(q=17\), so \(n=3\cdot 11\cdot 17\) is the smallest Carmichael number.
$$\begin{aligned} n=3\cdot p\cdot q, \text {where}~ p-1|n-1,q-1|n-1,p<q ~\text {is a prime}. \end{aligned}$$
$$\begin{aligned} 3\cdot p\cdot q \equiv 1({{\,\mathrm{mod}\,}}q-1), q>p \end{aligned}$$
Example 5.3
For given prime number \(r\ge 3\), then the congruence equationshas only finite different prime solutions p, q. Let’s leave this conclusion for reflection.
$$\begin{aligned} {\left\{ \begin{aligned}&rpq \equiv 1({{\,\mathrm{mod}\,}}p-1)\\&rpq \equiv 1({{\,\mathrm{mod}\,}}q-1) \end{aligned} \right. } \end{aligned}$$
5.2 Euler Test
Let \(p>2\) be an odd prime, Euler test uses the Euler criterion in the quadratic residue of \({{\,\mathrm{mod}\,}}p\) to detect whether a positive integer n is prime. Like Fermat’s test, it is obvious that the n that passes the test cannot be determined as prime, but the n that fails the test is certainly not prime. We know that when the positive integers a and n are given \((n>1)\), the solution of the quadratic congruence equation \(x^{2}\equiv a({{\,\mathrm{mod}\,}}n)\) is a famous “NP complete” problem. We can’t find a general solution in an effective time. However, in the special case where \(n=p>2\) is an odd prime number, we have rich theoretical knowledge to discuss the quadratic residue of \({{\,\mathrm{mod}\,}}p\), these knowledge include the famous Gauss quadratic reciprocal law and Euler criterion, which constitute the core knowledge system of elementary number theory. First, we introduce Legendre sign and let \(p>2\) be a given odd prime number.
\(\mathbb {Z}_{p}^{*}\) is a \((p-1)\)-order cyclic group, \(a\in \mathbb {Z}_{p}^{*} ~(\text {i.e.,}~(a,p)=1)\), we define the Legendre symbolic function asIf \((a,p)>1\), that is \(p\mid a\), we let \((\frac{a}{p})=0\), for \(\forall ~ a\in \mathbb {Z}\), Legendre symbolic function \((\frac{a}{p})\) is all defined, and it is a completely integral function of \(\mathbb {Z}\rightarrow \{1,-1,0\}\).andIf \((\frac{a}{p})=1\), then \(x^{2}\equiv a({{\,\mathrm{mod}\,}}p)\) is solvable, a is called a quadratic residue of \({{\,\mathrm{mod}\,}}p\), if \((\frac{a}{p})=-1\), then \(x^{2}\equiv a({{\,\mathrm{mod}\,}}p)\) is unsolvable, a is called a quadratic nonresidue of \({{\,\mathrm{mod}\,}}p\).
$$\begin{aligned} \left( \frac{a}{p}\right) =\left\{ \begin{aligned}&1, \ \ \ \ \ \text {when}~x^{2}\equiv a({{\,\mathrm{mod}\,}}p)~\text { is solvable}\\&-1,\text {when}~x^{2}\equiv a({{\,\mathrm{mod}\,}}p)~\text {is unsolvable}\\ \end{aligned} \right. \end{aligned}$$
$$\begin{aligned} \left( \frac{ab}{p}\right) =\left( \frac{a}{p}\right) \left( \frac{b}{p}\right) ,\forall ~ a,b \in \mathbb {Z}\end{aligned}$$
$$\begin{aligned} \left( \frac{a}{p}\right) =\left( \frac{b}{p}\right) , ~\text {if}~ a\equiv b\left( {{\,\mathrm{mod}\,}}p\right) . \end{aligned}$$
Lemma 5.5
\(a \in \mathbb {Z},p\not \mid a\), then the necessary and sufficient condition for a to be the quadratic residue of \({{\,\mathrm{mod}\,}}p\) is
$$\begin{aligned} a^{\frac{p-1}{2}}\equiv 1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
Proof
\(\mathbb {Z}_{p}^{*}\) is a \(p-1\)-order cyclic group, let g be a primitive root of \({{\,\mathrm{mod}\,}}p\), that is \(\bar{g}\) is the generator of \(\mathbb {Z}_{p}^{*}\), that is \(\forall a\in \mathbb {Z},(a,p)=1\), we haveObviously, a is the quadratic residue of \({{\,\mathrm{mod}\,}}p\) \(\Leftrightarrow t\) is even. Therefore, if t is even, thenConversely, if \(a^{\frac{p-1}{2}}\equiv 1({{\,\mathrm{mod}\,}}p)\), then \(o(a)\mid \frac{p-1}{2}\), and by Lemma 5.1, can calculateSothat is t is even, thus, a is a quadratic residue of \({{\,\mathrm{mod}\,}}p\), the Lemma holds.
$$\begin{aligned} a\equiv g^{t} ({{\,\mathrm{mod}\,}}p), ~\text {where}~1\le t \le p-1. \end{aligned}$$
$$\begin{aligned} a^{\frac{p-1}{2}}\equiv g^{\frac{t(p-1)}{2}}\equiv (g^{\frac{t}{2}})^{p-1}\equiv 1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
$$\begin{aligned} o(a)=o(g^{t})=\frac{p-1}{(t,p-1)}. \end{aligned}$$
$$\begin{aligned} o(a) \mid \frac{p-1}{2} \Leftrightarrow 2 |(t, p-1)\Leftrightarrow 2 |t, \end{aligned}$$
Lemma 5.6
(Euler criterion). For \(\forall ~ a \in \mathbb {Z}\), we have
$$\begin{aligned} a^{\frac{p-1}{2}}\equiv \left( \frac{a}{p}\right) ({{\,\mathrm{mod}\,}}p). \end{aligned}$$
(5.5)
Proof
If \((a,p)>1\), that is p|a, the above formula holds. Might as well let \(p\not \mid a\). By Fermat congruence theorem \(a^{p-1}\equiv 1({{\,\mathrm{mod}\,}}p)\), there isThusIf \(a^{\frac{p-1}{2}}\equiv 1({{\,\mathrm{mod}\,}}p)\), by Lemma 5.5, then \((\frac{a}{p})=1\). If \(a^{\frac{p-1}{2}}\equiv -1({{\,\mathrm{mod}\,}}p)\), then \((\frac{a}{p})=-1\). So (5.5) holds.
$$\begin{aligned} (a^{ \frac{p-1}{2}}+1)(a^{ \frac{p-1}{2}}-1)\equiv 0({{\,\mathrm{mod}\,}}p). \end{aligned}$$
$$\begin{aligned} a^{\frac{p-1}{2}}\equiv \pm 1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
Definition 5.3
Suppose n is an odd compound number, if there is an integer \(b, (b, n)=1\), it satisfiesCall n an Euler pseudo prime under base b. Where \((\frac{b}{n})\) is Jacobi symbol, define as
$$\begin{aligned} b^{\frac{n-1}{2}}\equiv \left( \frac{b}{n}\right) ({{\,\mathrm{mod}\,}}n), \end{aligned}$$
(5.6)
$$\begin{aligned} \left( \frac{b}{n}\right) =\left( \frac{b}{p_{1}}\right) ^{\alpha _{1}}\left( \frac{b}{p_{2}}\right) ^{\alpha _{2}}\cdots \left( \frac{b}{p_{s}}\right) ^{\alpha _{s}}, ~\text {if}~n=p_{1}^{\alpha _{1}}\cdots p_{s}^{\alpha _{s}}. \end{aligned}$$
(5.7)
From the definition, we obviously have a corollary: if n is Euler pseudo prime under basis b, then n is Fermat pseudo prime under basis b. This conclusion can be proved by squaring both sides of Eq. (5.6) at the same time.
The following example shows that the inverse of inference is not tenable; that is, if n is Fermat pseudo prime under basis b, but not Euler pseudo prime.
Example 5.4
\(n=91\) is Fermat pseudo prime under basis \(b=3\), but not Euler pseudo prime. In fact, it’s easy to calculate \(3^{6}\equiv 1({{\,\mathrm{mod}\,}}91)\), thus \(3^{90}\equiv 1({{\,\mathrm{mod}\,}}91)\). From \(3^{6}\equiv 1({{\,\mathrm{mod}\,}}91)\), we haveSo 91 to base 3 is not an Euler pseudo prime.
$$\begin{aligned} 3^{42}\equiv 1({{\,\mathrm{mod}\,}}91), \Longrightarrow 3^{45}\equiv 9({{\,\mathrm{mod}\,}}91). \end{aligned}$$
Example 5.5
\(n=91\) to base \(b=10\) is an Euler pseudo prime. Becausecalculate Legendre symbolsso \(n=91\) to base \(b=10\) is an Euler pseudo prime.
$$\begin{aligned} 10^{45}\equiv 10^{3} \equiv -1({{\,\mathrm{mod}\,}}91), \end{aligned}$$
$$\begin{aligned} \left( \frac{10}{91}\right) =\left( \frac{2}{91}\right) \cdot \left( \frac{5}{91}\right) =-1, \end{aligned}$$
From the Euler criterion of Lemma 5.6, we can easily calculate the Legendre symbols of \(-1\) and 2.
Lemma 5.7
Let \(p>2\) be an odd prime, then we have
$$\begin{aligned} \left( \frac{-1}{p}\right) =(-1)^\frac{p-1}{2}, ~\left( \frac{2}{p}\right) =(-1)^{\frac{1}{8}(p^{2}-1)}. \end{aligned}$$
(5.8)
Proof
By Lemma 5.6,Since both sides of the congruence are \(\pm 1\), \(p>2\), there is \((\frac{-1}{p})=(-1)^{\frac{p-1}{2}}\). To calculate the Legendre sign for 2, we notice thatwhere \(r = \frac{p-1}{2}\), if \( \frac{p-1}{2}\) is a even; \(r=p- \frac{p-1}{2}\), if \(\frac{p-1}{2}\) is an odd. There isthat isby Lemma 5.6,there isLemma 5.7 holds.
$$\begin{aligned} (-1)^{\frac{p-1}{2}}\equiv \left( \frac{-1}{p}\right) ({{\,\mathrm{mod}\,}}p), \end{aligned}$$
$$\begin{aligned} \left\{ \begin{aligned}&p-1\equiv (-1)^{1}({{\,\mathrm{mod}\,}}p)\\&2\equiv 2\cdot (-1)^{2}({{\,\mathrm{mod}\,}}p)\\&p-3\equiv 3\cdot (-1)^{3}({{\,\mathrm{mod}\,}}p)\\&\vdots \\&r\equiv \frac{p-1}{2}\cdot (-1)^{\frac{p-1}{2}}({{\,\mathrm{mod}\,}}p), \end{aligned} \right. \end{aligned}$$
$$\begin{aligned} 2\cdot 4\cdot 6\cdots (p-1)\equiv \left( \frac{p-1}{2}\right) !(-1)^{\frac{1}{8}(p^{2}-1)}({{\,\mathrm{mod}\,}}p), \end{aligned}$$
$$\begin{aligned} 2^{\frac{p-1}{2}}\equiv (-1)^{\frac{1}{8}(p^{2}-1)}({{\,\mathrm{mod}\,}}p), \end{aligned}$$
$$\begin{aligned} \left( \frac{2}{p}\right) \equiv (-1)^{\frac{1}{8}(p^{2}-1)}({{\,\mathrm{mod}\,}}p), \end{aligned}$$
$$\begin{aligned} \left( \frac{2}{p}\right) =(-1)^{\frac{1}{8}(p^{2}-1)}, \end{aligned}$$
Let \((\frac{a}{n})\) be a Jacobi symbol, defined by Eq. (5.6), then Lemma 5.7 can be extended to Jacobi symbol.
Lemma 5.8
Let n be an odd, then we have
$$\begin{aligned} \left( \frac{-1}{n}\right) =(-1)^{\frac{n-1}{2}}, ~\left( \frac{2}{n}\right) =(-1)^{\frac{1}{8}(n^{2}-1)}. \end{aligned}$$
(5.9)
Proof
The square of any odd number is congruent 1 under \({{\,\mathrm{mod}\,}}8\), that is \(a^{2}\equiv 1({{\,\mathrm{mod}\,}}8)\). Write \(n=a^{2}\cdot p_{1}p_{2}\cdots p_{t}\), where \(p_{i}\) are different prime numbers, thenSimilarly, for \(\forall ~ n \in \mathbb {Z}\), by (5.7),thusThe same can be proved \(\left( \frac{2}{n}\right) \), the Lemma holds.
$$\begin{aligned} n\equiv p_{1}p_{2}\cdots p_{t}({{\,\mathrm{mod}\,}}8). \end{aligned}$$
$$\begin{aligned} \left( \frac{b}{n}\right) =\left( \frac{b}{p_{1}}\right) \left( \frac{b}{p_{2}}\right) \cdots \left( \frac{b}{p_{t}}\right) , \end{aligned}$$
(5.10)
$$\begin{aligned} \left( \frac{-1}{n}\right) =\left( \frac{-1}{p_{1}}\right) \left( \frac{-1}{p_{2}}\right) \cdots \left( \frac{-1}{p_{t}}\right) =(-1)^{\frac{p_{1}-1}{2}+\frac{p_{2}-1}{2}+\cdots +\frac{p_{t}-1}{2}}=(-1)^{\frac{n-1}{2}}. \end{aligned}$$
(5.11)
Corollary 5.1
For all odd numbers n, they are Euler pseudo prime under the base \(\pm 1\).
Proof
It is trivial that n to 1 is an Euler pseudo prime number, and n to \(-1\) is an Euler pseudo prime number, which is directly derived from Lemma 5.8.
Lemma 5.9
(Gauss. ) Let p and q be two different odd primes, then
$$\begin{aligned} \left( \frac{q}{p}\right) \left( \frac{p}{q}\right) =(-1)^{\frac{1}{4}(p-1)(q-1)}. \end{aligned}$$
Proof
According to incomplete statistics, there are currently more than 270 methods to prove Gauss quadratic reciprocal law. In order to save space, we leave the proof to the readers, hoping that everyone can find their favorite proof method.
Next, we discuss the computational complexity of Fermat test and Euler test.
Lemma 5.10
Let n be an odd, \(1\le b <n\), \((b,n)=1\), then
$$\begin{aligned} \left\{ \begin{aligned}&\mathrm{Time}(n ~\mathrm{to} ~ \mathrm{base}~b\mathrm{'s} ~\mathrm{Fermat} ~\mathrm{test}) =O(\log ^{3}n),\\&\mathrm{Time}(n ~\mathrm{to} ~\mathrm{base}~b\mathrm{'s} ~\mathrm{Euler} ~ \mathrm{test}) =O(\log ^{4}n). \end{aligned} \right. \end{aligned}$$
Proof
By (5.1), the Fermat test of n to base b is actually an operation of \(b^{n-1}\) to \({{\,\mathrm{mod}\,}}n\), by the Lemma 1.5 of Chap. 1, bit operations of \(b^{n-1} {{\,\mathrm{mod}\,}}n\),Euler test of n to base b, by (5.6), the number of bit operations on the left is \(O(\log ^{3}n)\). Find Jacobi symbol \((\frac{b}{n})\), from Eq. (5.7) and quadratic reciprocal law, the calculation can be transformed into the calculation of Legendre symbol. Each reciprocal law is actually a division, so we only consider the calculation of Legendre symbols. By Euler criterion,The number of prime factors of each n has an estimated \(O(\log \log n)\), soWe have completed the calculation of Lemma 5.10.
$$\begin{aligned} \mathrm{Time}(b^{n-1} {{\,\mathrm{mod}\,}}n)=O(\log {n}\log ^{2} n)= O(\log ^{3}n). \end{aligned}$$
$$\begin{aligned} \mathrm{Time}\left( \text {calculate}~\left( \frac{b}{p}\right) \right) =\mathrm{Time}\left( b^{\frac{p-1}{2}} {{\,\mathrm{mod}\,}}p\right) = O(\log ^{3}n). \end{aligned}$$
$$\begin{aligned} \mathrm{Time}\left( \text {calculate Jacobi symbol}~\left( \frac{b}{n}\right) \right) =O(\log \log n \cdot \log ^{3}n)= O(\log ^{4}n). \end{aligned}$$
Solovay and Strassen proposed a probabilistic method to detect prime numbers by Euler test in 1977. When \(n>1\) is an odd number, k numbers are randomly selected, \(b_{1},b_{2},\ldots ,b_{k}\), where \(1<b_{i}<n\), \((b_{i},n)=1\). Use Eq. (5.6) to calculate both sides of each b in turn, and the required bit operation is \(O(\log ^{4}n)\), if both sides of Eq. (5.6) are not equal, then n is not a prime number and the test is terminated. If k b pass the Euler test of Eq. (5.6), then n is the probability \(<\frac{1}{2^{k}}\) of compound number, that isThe above formula is directly derived from Lemma 5.3. Let’s introduce a better Miller–Rabin method than Solovay–Strassen method in a sense.
$$\begin{aligned} P\{n ~\text {is not prime}\}\le 2^{-k}. \end{aligned}$$
Definition 5.4
Let n be an odd compound number, write \(n-1=2^{t}\cdot m\), where \(t\ge 1\), m is an odd. Let \(b \in \mathbb {Z}^{*}_{n}\), if n and b satisfy one of the following conditions,Then n is called a strong pseudo prime under base b.
$$\begin{aligned} b^{m}\equiv 1({{\,\mathrm{mod}\,}}n), \text {or exists one}~r, 0\le r<t, \text {such that}~ b^{2^{r}m}\equiv -1({{\,\mathrm{mod}\,}}n). \end{aligned}$$
(5.12)
Lemma 5.11
Suppose \(n\equiv 3({{\,\mathrm{mod}\,}}4)\), then n is a strong Pseudoprime under base b if and only if n is an Euler Pseudoprime under base b.
Proof
Because \(n\equiv 3({{\,\mathrm{mod}\,}}4)\), then \(n-1=2m\), that is \(t=1\), \(m=\frac{1}{2}(n-1)\). By Definition 5.4, n is a strong pseudo prime under base b if and only ifTherefore, if n is an Euler pseudo prime number under base b, the above formula holds, so it is also a strong pseudo prime number for base b. Conversely, if the above formula holds, because of \(n\equiv 3({{\,\mathrm{mod}\,}}4)\), then \(\frac{1}{2}(n-1)\) is an odd number, so \((\frac{-1}{n})=-1\), andTherefore, n to base b is Euler pseudo prime. The Lemma holds.
$$\begin{aligned} b^{m}=b^{\frac{n-1}{2}}\equiv \pm 1({{\,\mathrm{mod}\,}}n). \end{aligned}$$
$$\begin{aligned} \left( \frac{b}{n}\right) =\left( \frac{b}{n}\right) ^{\frac{n-1}{2}}\equiv \left( \frac{b^{\frac{n-1}{2}}}{n}\right) \equiv b^{\frac{n-1}{2}}({{\,\mathrm{mod}\,}}n). \end{aligned}$$
Below we give the main results of this section.
Theorem 5.2
Let n be an odd number, \(b \in \mathbb {Z}^{*}_{n}\), then
(i)
If n to base b is a strong pseudo prime, then n to base b is an Euler pseudo prime.
(ii)
Base b, which makes n a strong pseudo prime number, accounts for \(25\%\) of \(1\le b<n\), \((b,n)=1\) at most.
Before proving Theorem 5.2, let’s introduce Miller–Rabin’s test method, in order to test whether a large odd number n is a prime number, we write \(n-1=2^{t}\cdot m\), m is an odd number, \(t\ge 1\), select one b at random, \(1\le b<n\), \((b,n)=1\). We first calculate \(b^{m}{{\,\mathrm{mod}\,}}n\), if we get the result is \(\pm 1\), then n passes the strong pseudo prime test (5.12). If \(b^{m}{{\,\mathrm{mod}\,}}n\ne \pm 1\), then we square \(b^{m}{{\,\mathrm{mod}\,}}n\) and find the minimum nonnegative residue of the squared number under \({{\,\mathrm{mod}\,}}n\) to see if we get the result of \(- 1\) and perform r times. If we can’t get \(- 1\), then n to base b fails to test Formula (5.12). Therefore, it is asserted that n to base b is not a strong pseudo prime number. If \(- 1\) is obtained by r squared, then n passes the test under base b.
In Miller–Rabin’s test, if n to base b fails to pass the test Formula (5.12), then n must not be a prime number, if n to randomly selected k \(b=\{b_{1},b_{2},\ldots , b_{k}\}\) pass the test, by property (ii) of 5.2, each \(b_{i}\) accounts for no more than 25Compared with the Solovay–Strassen method using Euler test, the Miller–Rabin method using strong pseudo prime test is more powerful.
$$\begin{aligned} P\{n ~\text {not prime}\}\le \frac{1}{4^{k}}. \end{aligned}$$
(5.13)
To prove 5.2, we first prove the following two lemmas.
Lemma 5.12
Let \(G=\langle g \rangle \) be a finite group of order m, that is \(o(g)=m\), then equation \(x^{k}=1\) has exactly d solutions in G, \(d=(k,m)\).
Proof
\(x \in G\), write \(x=g^{t}\), then \(x^{k}=g^{kt}=1\Leftrightarrow m|kt\), that is \(\frac{m}{d}|\frac{k}{d}\cdot t\), thus \(\frac{m}{d}|t\), let \(t=\frac{m}{d}\cdot s\), then when \(s=1,2,\ldots ,d\), \(x=g^{t}\) has exactly d solutions. The Lemma holds.
Lemma 5.13
Let p be an odd prime number, \(p-1=2^{t}m'\), \(t\ge 1\), \(m'\) is prime, thenThe number of solutions N in \(\mathbb {Z}^{*}_{p}\) satisfies
$$\begin{aligned} x^{2^{r}m}\equiv -1({{\,\mathrm{mod}\,}}p), m~\mathrm{is} \;\mathrm{odd} \end{aligned}$$
(5.14)
$$\begin{aligned} N={\left\{ \begin{aligned}&0,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathrm{if}~r\ge t;\\&2^{r}(m,m'),\ \ \mathrm{if}~r<t. \end{aligned} \right. } \end{aligned}$$
Proof
Let g be a generator of \(\mathbb {Z}^{*}_{p}\), write \(x=g^{j}\), \(1\le j\le p-1\), because \(o(g)=p-1\), soThusNamely,Because \(p-1=2^{t}m'\), the above formula is equivalent toIf \(r>t-1\), then the congruence has no solution to j, because m and \(m'\) are odd numbers, so when \(r\ge t\), (5.14) is unsolvable. If \(r<t\), let \(d=(m,m')\), thenthen Eq. (5.15) has exactly d solutions for j. Each j corresponds to one \(x=g^{j}\), then the number of solutions of Eq. (5.14) to x is \(N=2^{r}d\), the Lemma holds.
$$\begin{aligned} g^{\frac{p-1}{2}} \equiv -1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
$$\begin{aligned} x^{2^{r}m}\equiv -1({{\,\mathrm{mod}\,}}p)\Leftrightarrow 2^{r}mj \equiv \frac{p-1}{2} ({{\,\mathrm{mod}\,}}p-1). \end{aligned}$$
$$\begin{aligned} 2^{r}mj \equiv 0 ({{\,\mathrm{mod}\,}}p-1). \end{aligned}$$
$$\begin{aligned} 2^{r}mj \equiv 2^{t-1}m' ({{\,\mathrm{mod}\,}}2^{t}m'). \end{aligned}$$
(5.15)
$$\begin{aligned} (2^{r}m, 2^{t}m')= 2^{r}d, \end{aligned}$$
With the above preparation, we now give the proof of Theorem 5.2.
Proof
(The proof of Theorem 5.2). Let’s first prove that (i), that is, n and b satisfy Eq. (5.12), we want to prove that formula (5.6) is satisfied; that is, if n to base b is a strong pseudo prime number, then n to base b is an Euler pseudo prime number, write \(n-1=2^{t}m\), m is prime, we prove the property (i) of Theorem 5.2 in three cases.
(1)
\(b^{m}\equiv 1({{\,\mathrm{mod}\,}}n)\). In this case, it is obvious that \(b^{\frac{n-1}{2}}\equiv 1({{\,\mathrm{mod}\,}}n)\). Let’s prove \((\frac{b}{n})=1\), in fact, There is That is n to base b is an Euler pseudo prime number.
$$\begin{aligned} 1=\left( \frac{1}{p}\right) =\left( \frac{b^{m}}{p}\right) =\left( \frac{b}{p}\right) ^{m}=1. \end{aligned}$$
$$\begin{aligned} b^{\frac{n-1}{2}}\equiv \left( \frac{b}{n}\right) \equiv 1({{\,\mathrm{mod}\,}}n). \end{aligned}$$
(2)
\(b^{\frac{n-1}{2}}\equiv -1({{\,\mathrm{mod}\,}}n)\). In this case, we have to prove \((\frac{b}{n})=-1\), let p|n be any prime factor of n, write \(p-1=2^{t_{1}}m_{1}\), where \(t_{1}\ge 1\), \(m_{1}\) is an odd number. Let’s calculate the Legendre symbol \((\frac{b}{p})\), in fact, \(t_{1}\ge t\), and Because by p|n, we have If \(t_{1}< t\), from the above formula, there is This contradicts Fermat’s congruence theorem, so we always have \(t_{1}\ge t\). If \(t_{1}= t\), by (5.17), then Because if the above formula is 1, both sides will be m power at the same time, which will contradict Formula (5.17). If \(t_{1}> t\), put both sides of Eq. (5.17) to the power of \(2^{t_{1}- t}\) at the same time, then \((\frac{b}{p})=1\), so we have (5.16).
$$\begin{aligned} \left( \frac{b}{p}\right) ={\left\{ \begin{aligned}&-1,\ \ \text {if}~t_{1}= t;\\&1,\ \ \ \ \ \ \ \text {if}~t_{1}> t. \end{aligned} \right. } \end{aligned}$$
(5.16)
$$\begin{aligned} b^{\frac{n-1}{2}}=b^{2^{t-1}m}\equiv -1({{\,\mathrm{mod}\,}}n),\Longrightarrow b^{2^{t-1}mm_{1}}\equiv -1({{\,\mathrm{mod}\,}}n), \end{aligned}$$
$$\begin{aligned} b^{2^{t-1}mm_{1}}\equiv -1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
(5.17)
$$\begin{aligned} b^{2^{t_{1}}m_{1}}\equiv -1({{\,\mathrm{mod}\,}}p), \Longrightarrow b^{p-1}\equiv -1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
$$\begin{aligned} \left( \frac{b}{p}\right) \equiv b^{\frac{p-1}{2}}=b^{2^{t-1}m}\equiv -1({{\,\mathrm{mod}\,}}p). \end{aligned}$$
We now complete the proof of case (2) under the conclusion of Eq. (5.16), write \(n=\prod _{p|n}{p}\), p does not require different, define the positive integer k as By (5.16), then Let’s prove that k is an odd number, because \(t_{1}\ge t\), \(p-1=2^{t_{1}}m_{1}\), \(n-1=2^{t}m\), under \({{\,\mathrm{mod}\,}}2^{t+1}\), we have Because \(n=1+2^{t}({{\,\mathrm{mod}\,}}2^{t+1})\), so So k must be odd, by (5.18), then \((\frac{b}{n})=-1\). Case (2) is proved.
$$\begin{aligned} k=\# \{p\mid p|n,p-1=2^{t_{1}}m_{1},m_{1} ~\text {is odd}, t_{1}=t\}. \end{aligned}$$
$$\begin{aligned} \left( \frac{b}{n}\right) = \prod {\left( \frac{b}{p}\right) }=(-1)^{k}. \end{aligned}$$
(5.18)
$$\begin{aligned} p \equiv {\left\{ \begin{aligned}&1({{\,\mathrm{mod}\,}}2^{t+1}),\ \ \ \ \ \ \ \ \ \ \text {if}~t_{1}>t;\\&1+2^{t}({{\,\mathrm{mod}\,}}2^{t+1}),\ \ \text {if}~t_{1}=t. \end{aligned} \right. } \end{aligned}$$
$$\begin{aligned} n\equiv 1+2^{t} \equiv 1+k\cdot 2^{t}({{\,\mathrm{mod}\,}}2^{t+1}), \end{aligned}$$
(3)
\(b^{2^{r-1}\cdot m}\equiv -1({{\,\mathrm{mod}\,}}n)\), where \(1\le r\le t\), \(n-1=2^{t}\cdot m\).
In this case, we replace r of Eq. (5.12) with \(r-1\). Because \(r-1\le t-1\), so \(b^{\frac{n-1}{2}}\equiv 1({{\,\mathrm{mod}\,}}n)\). To prove property (i) of Theorem 5.2, we have to prove \((\frac{b}{n})=1\), as in case (2), we let p|n, write \(p-1=2^{t_{1}}\cdot m_{1}\), \(m_{1}\) is odd, then we have \(t_{1}\ge r\), and The proof of Formula (5.19) is the same as that of case (2), write \(n=\prod p\), p is not required to be a different prime, define positive integer \(k_{1}\): as in case (2), we have \((\frac{b}{n})=(-1)^{k_{1}}\), similarly, under \({{\,\mathrm{mod}\,}}2^{r+1}\), it can be proved that \(k_{1}\) must be even. Thus \((\frac{b}{n})=1\), we have completed all the proofs of property (i) in Theorem 5.2. Next, we prove property (ii) in Theorem 5.2. It is also discussed in three cases.
$$\begin{aligned} \left( \frac{b}{p}\right) ={\left\{ \begin{aligned}&-1,\ \ \text {if}~t_{1}= r;\\&1,\ \ \ \ \ \ \ \text {if}~t_{1}> r. \end{aligned} \right. } \end{aligned}$$
(5.19)
$$\begin{aligned} k_{1}=\#\{p\mid p|n, p-1=2^{t_{1}}m_{1},m_{1}~\text {is odd}, t_{1}=r\}. \end{aligned}$$
(1)
n can be divided by a square number; that is, there is a prime number p, \(p^{\alpha }||n\), \(\alpha \ge 2\).
In this case, we prove that there are at least \(\frac{1}{4}(n-1)\) b, \(b \in \mathbb {Z}^{*}_{n}\), n to base b is not Fermat prime number, let alone a strong pseudo prime. First, suppose \(b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}n)\), then there is a prime p, \(p^{2}|n\), thus \(b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}p^{2})\). Because \(\mathbb {Z}^{*}_{p^{2}}\) is a \(p(p-1)\)-order cyclic group (see Theorem 5.3), let g be a generator of \(\mathbb {Z}^{*}_{p^{2}}\), then By Lemma 5.12, the number of b satisfying \(b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}p^{2})\) is d, Because p|n, so \(p\not \mid n-1\), and \(p\not \mid d\); therefore, the maximum possibility of d is \(p-1\); therefore, the proportion of b in \(b^{n-1}\equiv 1({{\,\mathrm{mod}\,}}p^{2})\) in \(1 \le b <n\) shall not exceed Therefore, there is at most b in the proportion of \(\frac{1}{4}\), so that n to base b is Fermat prime, in case (1), we prove the property (ii) of Theorem 5.2.
$$\begin{aligned} \mathbb {Z}^{*}_{p^{2}}=\{g, g^{2},\ldots , g^{p(p-1)}\}. \end{aligned}$$
$$\begin{aligned} d=(n-1,p(p-1))=(n-1,p-1). \end{aligned}$$
$$\begin{aligned} \frac{p-1}{p^{2}-1}=\frac{1}{p+1}\le \frac{1}{4}. \end{aligned}$$
(2)
\(n=pq\) are two different prime numbers.
In this case, let \(p-1=2^{t_{1}}m_{1}\), \(q-1=2^{t_{2}}m_{2}\), \(m_{1}\), \(m_{2}\) to be odd. Without losing generality, you can let \(t_{1}\le t_{2}\). Let \(b \in \mathbb {Z}^{*}_{n}\), in order for n to base b to be a strong pseudo prime number, it is necessary to satisfy or By Lemma 5.12, the number of b satisfied (5.20) is \(\le (m,m_{1})(m,m_{2})\le m_{1}m_{2}\). By Lemma 5.13, for each r, \(0\le r<\min (t_{1},t_{2})=t_{1}\), the number of b satisfying \(b^{2^{r}m}\equiv -1({{\,\mathrm{mod}\,}}n)\) is \(2^{r}(m,m_{1})\cdot 2^{r}(m,m_{2})<4^{r}m_{1}m_{2}\). Because \(n=pq\), then \(\varphi (n)=(p-1)(q-1), \Longrightarrow n-1>\varphi (n)=2^{t_{1}+t_{2}}\), therefore, the proportion of b of the strong pseudo prime of n to base b does not exceed in \(1\le b<n, (b,n)=1\).
$$\begin{aligned} b^{m}\equiv 1({{\,\mathrm{mod}\,}}p), ~b^{m}\equiv 1({{\,\mathrm{mod}\,}}q) \end{aligned}$$
(5.20)
$$\begin{aligned} b^{2^{r}m}\equiv -1({{\,\mathrm{mod}\,}}p), ~b^{2^{r}m}\equiv -1({{\,\mathrm{mod}\,}}q), 0\le r<t. \end{aligned}$$
(5.21)
$$\begin{aligned} \frac{m_{1}m_{2}+m_{1}m_{2}+4m_{1}m_{2}+\cdots +4^{t_{1}-1}m_{1}m_{2}}{2^{t_{1} +t_{2}}m_{1}m_{2}}=2^{-t_{1}-t_{2}}\left( 1+\frac{4^{t_{1}}-1}{4-1}\right) \end{aligned}$$
(5.22)
If \(t_{1}<t_{2}\), then the above formula shall not exceed If \(t_{1}=t_{2}\), then \(m_{1}\ne m_{2}\), so \((m,m_{1})\le m_{1}\) and \((m,m_{2})\le m_{2}\), one must be strictly less than. The reason is that if they are equal, then \(m_{1}|m\), \(m_{2}|m\), \(n-1=2^{t}m, \Longrightarrow n-1=2^{t}m=pq-1\equiv q-1({{\,\mathrm{mod}\,}}m_{1})\), thus \(m_{1}|n-1, \Longrightarrow m_{1}|q-1=2^{t_{2}}m_{2}, \Longrightarrow m_{1}|m_{2}\), this is a contradiction. So \((m,m_{1})\le m_{1}\) and \((m,m_{2})\le m_{2}\) must have a strict less than 0. We have If \(m_{1}m_{2}\) is substituted for \(\frac{1}{3} m_{1}m_{2}\) in Eq. (5.22), the proportion of n to b whose base b is a strong pseudo prime number does not exceed We complete the proof of property (ii) of Theorem 5.2 in case (2).
$$\begin{aligned} 2^{-2t_{1}-1}\left( \frac{2}{3}+\frac{4^{t_{1}}}{3}\right) \le 2^{-3}\cdot \frac{2}{3}+\frac{1}{6}=\frac{1}{4}. \end{aligned}$$
$$\begin{aligned} (m,m_{1})\cdot (m,m_{2})\le \frac{1}{3} m_{1}m_{2}. \end{aligned}$$
$$\begin{aligned} \frac{1}{3}2^{-2t_{1}}\left( \frac{2}{3}+\frac{4^{t_{1}}}{3}\right) \le \frac{1}{18}+\frac{1}{9}=\frac{1}{6}<\frac{1}{4}. \end{aligned}$$
(3)
Finally, suppose \(n=p_{1}p_{2}\cdots p_{k}, k\ge 3\) is the product of different prime factors.
In this case, write \(p_{i}-1=2^{t_{i}}m_{i}\), \(m_{i}\) as an odd number. As in case (2), without losing generality, it can make \(t_{1}\le t_{j}(1\le j\le k)\). Similarly to the proof of formula (5.22), the proportion of b satisfying that n is a strong pseudo prime number for base b does not exceed because \(k\ge 3\), in this way, we have completed all the proofs of Theorem 5.2.
$$\begin{aligned} \begin{aligned} 2^{-t_{1}-t_{2}-\cdots -t_{k}}\left( 1+\frac{2^{k+1}-1}{2^{k}-1}\right)&\le 2^{-kt_{1}}\left( \frac{2^{k}-2}{2^{k}-1}+\frac{2^{kt_{1}}}{2^{k}-1}\right) \\&=2^{-kt_{1}}\cdot \frac{2^{k}-2}{2^{k}-1}+\frac{1}{2^{k}-1}\\&\le 2^{-k}\frac{2^{k}-2}{2^{k}-1}+\frac{1}{2^{k}-1}\\&=2^{1-k}\\&\le \frac{1}{4}, \end{aligned} \end{aligned}$$
Euler test and strong pseudo prime test require some complex quadratic residual techniques. We summarize the main conclusions of this section as follows:
(A)
n to base b is a strong pseudo prime number \(\Rightarrow \) n to base b is an Euler pseudo prime number \(\Rightarrow \) n to base b is a Fermat pseudo prime number; therefore, the strong pseudo prime test is the best way to detect prime numbers.
(B)
Although no test can successfully detect a prime number at present, the probability detection method of strong pseudo prime number test, that is, Miller–Rabin method, can obtain that the success probability (see (5.13)) of detecting whether any odd number n is a prime number can be infinitely close to 1. That is Moreover, the computational complexity of the detection algorithm is polynomial.
$$\begin{aligned} P\{\text {detect whether odd }n~\text { is prime}\}>1-\varepsilon , \forall ~ \varepsilon >0~\text {given}. \end{aligned}$$
5.3 Monte Carlo Method
Using all the prime number test methods introduced in the previous two sections, for a huge odd number n, even if we already know that n is not a prime number, we cannot successfully decompose n, because the prime number test does not provide prime factor decomposition information, A more direct method—like the sieve method—verifies whether the prime factor of n is for prime numbers not greater than \(\sqrt{n}\), because a compound number n must have a prime factor p, \(p\le \sqrt{n}\). Selected \(p\le \sqrt{n}\), the bit operation required to divide n by p is \(O(\log n)\), there are \(O(\frac{\sqrt{n}}{\log n})\) prime numbers \(p\le \sqrt{n}\) in total, therefore, the bit operation required for such a verification is \(O(\sqrt{n})\). A more effective method was proposed by J. M. Pollard in 1975. We call it Monte Carlo method, or “rho” method.
First, find a convenient mapping f of \(\mathbb {Z}_{n} {\mathop {\longrightarrow }\limits ^{f}} \mathbb {Z}_{n}\); for example, f(x) is an integer coefficient polynomial, such as \(f(x)=x^{2}+1\); secondly, a prime number \(x_{0}\) is randomly generated, let \(x_{1}=f(x_{0})\), \(x_{2}=f(x_{1})\), \(\ldots \), \(x_{j+1}=f(x_{j})(j=0, 1, 2, \cdots )\). In these \(x_{j}\), we want to find two integers \(x_{j}\) and \(x_{k}\), which are different elements in \(\mathbb {Z}_{n}\), but there are some factors d of n, d|n, and \(x_{j}\) and \(x_{k}\) are the same elements in \(\mathbb {Z}_{d}\), that is to sayOnce \(x_{j}\) and \(x_{k}\) are found, the algorithm is said to be completed.
$$\begin{aligned} x_{j}\not \equiv x_{k}({{\,\mathrm{mod}\,}}n), (x_{j}-x_{k},n)>1. \end{aligned}$$
(5.23)
Theorem 5.3
Let S be a set of r elements, let \(f:S\rightarrow S\) is a mapping, \(x_{0} \in S\), define \(x_{j+1}=f(x_{j})(j=0, 1, 2, \ldots )\). Suppose \(\lambda \) is a positive real number, let \(l=1+[\sqrt{2\lambda r}]\), then the condition \(x_{0}, x_{1}, \ldots , x_{l}\) is the ratio \(\le e^{-\lambda }\) of the mapping f of elements in different s to the initial value \(x_{0}\), \((f,x_{0})\), f in all mappings S and all \( x_{0} \in S\).
Proof
The total number of mappings f from \(f:S\rightarrow S\) is \(r^{r}\), because each \(x \in S\), we can arrange r images for it, that is, f(x) has r choices. The initial value \(x_{0}\) has r choices, so the total number of \((f, x_{0})\) is \(r^{r+1}\). The question is which of these \((f,x_{0})\) choices can satisfy the condition that \(x_{0}, x_{1}, \ldots , x_{l}\) is a different element in S. we want to prove that the proportion of \((f, x_{0})\) satisfying the condition in \(r^{r+1}\) \((f, x_{0})\) is not greater than \(\le \mathrm{e}^{-\lambda }\).
When \(x_{0} \in S\) given, there are r \(x_{0}\) choices, then \(x_{1}=f(x_{0})\) has only \(r-1\) choices and \(x_{2}=f(x_{1})\) has only \(r-2\) choices, this goes on until \(x_{l}=f(x_{l-1})\), there are only \(r-l\) options. The remaining \(x \in S\) and f can be selected arbitrarily; that is, there are \(r^{r-l}\) choices. Therefore, when \(x_{0}\) is given, there are N f to make \((f,x_{0})\) meet the required conditions, whereDivide N by \(r^{r+1}\), and the proportion of \((f,x_{0})\) satisfying the condition isWe notice that the real number \(x \in (0,1)\), then \(\log (1-x)<-x\). Take the logarithm to the right of the above formula, thenBecause of \(l=1+[\sqrt{2\lambda r}]>\sqrt{2\lambda r}\), from the above formula,By (5.24), we haveWe complete the proof of Theorem 5.3.
$$\begin{aligned} N=r^{r-l}\prod ^{l}_{j=0}(r-j). \end{aligned}$$
$$\begin{aligned} \frac{N}{r^{r+1}}=r^{-l}\prod ^{l}_{j=1}(r-j)=\prod ^{l}_{j=1}\left( 1-\frac{j}{r}\right) , \end{aligned}$$
(5.24)
$$\begin{aligned} \sum ^{l}_{j=1}\log \left( 1-\frac{j}{r} \right)<-\sum ^{l}_{j=1}\frac{j}{r}=\frac{-l(l+1)}{2r}<-\frac{l^{2}}{2r}. \end{aligned}$$
$$\begin{aligned} \sum ^{l}_{j=1}\log \left( 1-\frac{j}{r}\right) <-\lambda . \end{aligned}$$
$$\begin{aligned} \frac{N}{r^{r+1}}\le \mathrm{e}^{-\lambda }. \end{aligned}$$
Monte Carlo method uses a polynomial \(f(x) \in \mathbb {Z}[x]\), so that n is a positive integer, and the congruence equation of \({{\,\mathrm{mod}\,}}n\) is invariant to polynomial f(x), that is\(x_{0} \in \mathbb {Z}_{n}\) given, \(x_{j+1}=f(x_{j})(j=0,1,\ldots )\), if you find an \(x_{k_{0}} \in \mathbb {Z}_{n}\) that satisfies \(x_{k_{0}}\equiv x_{j_{0}}({{\,\mathrm{mod}\,}}r)\), where r|n, \(r>1\), \(k_{0}>j_{0}\). By (5.25),Thus for any \(k>j\), if \(k-j=k_{0}-j_{0}\), there is \(x_{k}\equiv x_{j}({{\,\mathrm{mod}\,}}r)\), this proves that a polynomial mapping \(\mathbb {Z}_{n} {\mathop {\longrightarrow }\limits ^{f}} \mathbb {Z}_{n}\) produces \(k_{0}\) different residue classes under \({{\,\mathrm{mod}\,}}r (r|n)\),Therefore, there is the following Lemma 5.14.
$$\begin{aligned} a\equiv b({{\,\mathrm{mod}\,}}n), \Longrightarrow f(a)\equiv f(b)({{\,\mathrm{mod}\,}}n). \end{aligned}$$
(5.25)
$$\begin{aligned} f(x_{k_{0}})\equiv f(x_{j_{0}})({{\,\mathrm{mod}\,}}r), \Longrightarrow x_{k_{0}+1}\equiv x_{j_{0}+1}({{\,\mathrm{mod}\,}}r). \end{aligned}$$
$$\begin{aligned} \{x_{0}, x_{1}, \ldots , x_{k_{0}-1}\}. \end{aligned}$$
Lemma 5.14
\(f(x) \in \mathbb {Z}[x]\) is a polynomial, \(n>1\) is an positive integer, let \(x_{0} \in \mathbb {Z}_{n}\), \(x_{j}=f(x_{j-1})(j=1,2,\ldots )\), if k is the first subscript, there is a j, \(0\le j<k\), such thatThen \(\{x_{0},x_{1},\ldots ,x_{k-1}\}\) is k different residual classes under \({{\,\mathrm{mod}\,}}r\), so it is also k different residual classes under \({{\,\mathrm{mod}\,}}n\). Moreover, Monte Carlo calculation defined by f can only produce k different residual classes.
$$\begin{aligned} (x_{k}-x_{j},n)=r>1. \end{aligned}$$
We call the polynomial f and the initial value \(x_{0}\) described in Lemma 5.14 an average mapping. When the first subscript k is very large, the amount of calculation is very large. Here we give an improved Monte Carlo algorithm.
\(f(x) \in \mathbb {Z}[x]\) given, Monte Carlo algorithm needs to continuously calculate \(x_{k}(k=1,2,\ldots )\). Let \(2^{h}\le k <2^{k+1}(h\ge 0)\), \(j=2^{h}-1\); that is, k is an \((h+1)\)-bit number, j is the maximum h-bit number, compare \(x_{k}\) with \(x_{j}\) and calculate \((x_{k}-x_{j},n)\), if \((x_{k}-x_{j},n)>1\), then the calculation is terminated, otherwise consider \(k+1\). The improved Monte Carlo algorithm only needs to calculate \((x_{k}-x_{j},n)\) once for each k, \(j=2^{h}-1\). There is no need to verify every j, \(0\le j<k\), when k is very large, it reduces a lot of computation, but there is a disadvantage. It may miss the smallest subscript k satisfying the condition, but the error is controllable. In fact, we have the following error estimation.
Lemma 5.15
\(f(x) \in \mathbb {Z}[x]\), \(n\ge 1\) given, \(x_{0} \in \mathbb {Z}_{n}\), \(x_{j}=f(x_{j-1})(j=1,2,\ldots )\), let \(k_{0}\) be the smallest subscript and satisfy \((x_{k_{0}}-x_{j_{0}},n)>1\), where \(0\le j_{0}<k_{0}\), assuming that k is the smallest positive integer satisfying \((x_{k}-x_{j},n)>1\) in the improved Monte Carlo algorithm, we have \(k\le 4k_{0}\).
Proof
Suppose \(k_{0}\) has \((h+1)\) bits. Let \(j=2^{h+1}-1\), \(k=j+(k_{0}-j_{0})\). By Lemma 5.14, thenObviously, j is the maximum number of \((h+1)\) bits and k is the number of \((h+2)\) bits, so k is the required subscript calculated by the improved Monte Carlo algorithm. Obviously,Lemma 5.15 holds.
$$\begin{aligned} (x_{k_{0}}-x_{j_{0}},n)>1, \Longrightarrow (x_{k}-x_{j},n)>1. \end{aligned}$$
$$\begin{aligned} k=j+(k_{0}-j_{0})\le 2^{h+1}-1+2^{h+1}<4\cdot 2^{h}\le 4k_{0}. \end{aligned}$$
Example 5.6
Let \(n=91\), \(f(x)=x^{2}+1\), \(x_{0}=1\). By Monte Carlo algorithm, then \(x_{1}=2\), \(x_{2}=5\), \(x_{3}=26\) and \(x_{4}=40 \; (\mathrm{because}26^{2}+1\equiv 40({{\,\mathrm{mod}\,}}91))\). By the improved Monte Carlo algorithm, only \((x_{4}-x_{3},91)\) needs to be detected to obtain
$$\begin{aligned} (x_{4}-x_{3},91)=(14,91)=7. \end{aligned}$$
Lemma 5.16
Let n be an odd number and a compound number, and r be a factor of n, r|n, \(1<r<\sqrt{n}\). Let \(f(x) \in \mathbb {Z}[x]\), \(x_{0} \in \mathbb {Z}_{n}\) given, then the computational complexity of finding r by Monte Carlo algorithm \((f,x_{0})\) isFurther, there is a normal number C, so that for any positive real number \(\lambda \), the success probability of Monte Carlo algorithm \((f,x_{0})\) to find a nontrivial factor r of n is greater than \(1-\mathrm{e}^{-\lambda }\), that isThe number of bit calculation operations required by the algorithm that depends on parameter \(\lambda \) (to ensure the success rate of the algorithm) is \(O(\sqrt{\lambda }\root 4 \of {n}\log ^{3}n)\).
$$\begin{aligned} \mathrm{Time}((f,x_{0}))=O(\sqrt{n}\log ^{3}n)~ \mathrm{bits}. \end{aligned}$$
(5.26)
$$\begin{aligned} P\{(f,x_{0})\mathrm{find} \; \mathrm{out}~r|n, r>1\}\ge 1-\mathrm{e}^{-\lambda }. \end{aligned}$$
(5.27)
Proof
From the discussion of computational complexity in Chap. 1, finding the maximum common divisor of two integers and the addition, subtraction, multiplication and division in \({{\,\mathrm{mod}\,}}n\) are polynomial. Let \(C_{1}\) satisfies\(C_{2}\) satisfiesIf \(k_{0}\) is \((f,x_{0})\), the first subscript in the calculation satisfies \((x_{k_{0}}-x_{j_{0}},n)>1\), by the improved Monte Carlo algorithm, we have \((x_{k}-x_{j},n)>1\), where \(j=2^{h}-1\), \(2^{h}\le k< 2^{h+1}\). By Lemma 5.15, \(k\le 4k\). ThusLet \((x_{k_{0}}-x_{j_{0}},n)=r>1\), \(r<\sqrt{n}\), by Lemma 5.14, \(k_{0}\le r\), soEquation (5.26) proved. In the sense of probability, that is, on the premise of allowing certain errors, Eq. (5.26) can be further improved.
$$\begin{aligned} \mathrm{Time}((y-z,n))\le C_{1}\log ^{3}n,\text {where}~ y,z\le n. \end{aligned}$$
$$\begin{aligned} \mathrm{Time}(f(x){{\,\mathrm{mod}\,}}n)\le C_{2}\log ^{3}n,x \in \mathbb {Z}_{n}. \end{aligned}$$
$$\begin{aligned} \mathrm{Time}(\text {found by }(f,x_{0})~k)\le 4k_{0}(C_{1}\log ^{3}n+ C_{2}\log ^{3}n). \end{aligned}$$
(5.28)
$$\begin{aligned} \mathrm{Time}(\text {find}~r,r|n,r<\sqrt{n})\le 4\sqrt{n}(C_{1}\log ^{3}n, C_{2}\log ^{3}n). \end{aligned}$$
Let \(\lambda >0\) be any given real number, by Lemma 5.3, ratio of \(k_{0} \ge 1+\sqrt{2\lambda r}\) \(<\mathrm{e}^{-\lambda }\), in other words, the probability of successfully finding r, r|n, \(r\le \sqrt{n}\) isIn order to ensure the success rate, then \(k_{0}\le 1+\sqrt{2\lambda r}\). By (5.28), the number of bit operations required shall not be greater thanWe have completed the proof of Lemma.
$$\begin{aligned} P\{\text {find out}~r,r|n, r<\sqrt{n} \}\ge 1-\mathrm{e}^{-\lambda }. \end{aligned}$$
$$\begin{aligned} 4(1+\sqrt{2\lambda r})(C_{1}\log ^{3}n+ C_{2}\log ^{3}n)=O(\sqrt{\lambda }\root 4 \of {n}\log ^{3}n). \end{aligned}$$
Remark 5.1
A basic assumption of Monte Carlo method is that the integer coefficient polynomial f can be used as an average mapping (see Lemma 5.14); this has not yet been proved.
5.4 Fermat Decomposition and Factor Basis Method
Lemma 5.17
Suppose n is an odd number, there is a 1-1 correspondence between factorization \(n=a\cdot b(a\ge b>0)\) of n and expression \(n=t^{2}-s^{2}\) (t and s are nonnegative integers) of n. The corresponding \(\sigma :(a,b)\rightarrow (t,s)\) can be written as \(\sigma ((a,b))=(t,s)\), whereInverse mapping is
$$\begin{aligned} \sigma ((a,b))=\left( \frac{a+b}{2},\frac{a-b}{2}\right) . \end{aligned}$$
$$\begin{aligned} \sigma ^{-1}((t,s))=(t+s,t-s). \end{aligned}$$
Proof
If \(n=ab\), because both a and b are odd, then \(n=(\frac{a+b}{2})^{2}-(\frac{a-b}{2})^{2}\), so defineConversely, if \(n=t^{2}-s^{2}\), then \(n=(t+s)(t-s)\). So define \(\sigma ^{-1}((t,s))=(t+s,t-s)\), we prove \(\sigma ^{-1}\sigma =1\), \(\sigma \sigma ^{-1}=1.\) By the definition,So \(\sigma \) is a 1-1 correspondence between the two decomposition \(n=ab=t^{2}-s^{2}\), the Lemma holds.
$$\begin{aligned} \sigma ((a,b))=\left( \frac{a+b}{2},\frac{a-b}{2}\right) . \end{aligned}$$
$$\begin{aligned} {\left\{ \begin{aligned}&\sigma ^{-1}\sigma ((a,b))=\sigma ^{-1}\left( \frac{a+b}{2},\frac{a-b}{2}\right) =(a,b),\\&\sigma (\sigma ^{-1}((t,s)))=\sigma (t+s,t-s)=(t,s). \end{aligned} \right. } \end{aligned}$$
The above simple lemma provides us with a method of factor decomposition, called Fermat factor decomposition: if \(n=ab\), a is very close to b, then \(n=(\frac{a+b}{2})^{2}+(\frac{a-b}{2})^{2}=t^{2}-s^{2}\), where s is very small and t is only a little larger than \(\sqrt{n}\). Therefore, starting from \(t=[\sqrt{n}]+1\), we successively detect whether \(t^{2}-n\) is a complete square number. If not, we change it to \(t=[\sqrt{n}]+2\) for detection. In this way, until \(t^{2}-n=s^{2}\), we get \(n=(t+s)(t-s)\) through Fermat factorization. This method is effective when \(n=ab\), a and b are very close.
Fermat factor decomposition can be further expanded into a factor-based method to become a more effective factor decomposition method. Its basic idea is: in Fermat factorization, \(t^{2}-n^{2}\) is required to be a complete square, which is difficult to appear in practice, but \(t^{2}\equiv s^{2}({{\,\mathrm{mod}\,}}n)\), \(t\not \equiv \pm s({{\,\mathrm{mod}\,}}n)\) is easy to appear. Calculate the maximum common divisor \((t+s,n)\) and \((t-s,n)\), then we have factorization
$$\begin{aligned} n=(t+s,n)(t-s,n). \end{aligned}$$
Definition 5.5
Let B be h different primes \((\text {maybe}~ p_{1}=-1\)), B is called a factor base. An integer b is called a B-number, if the minimum nonnegative residue of \(b^{2}\) under \({{\,\mathrm{mod}\,}}n\) can be expressed as the product of prime numbers in B, where n is the given positive integer.
Example 5.7
Let \(n=4633\), \(B=\{-1,2,3\}\), then 67, 68, 69 are all B-number, because \(67^{2}\equiv -144({{\,\mathrm{mod}\,}}4633)\), \(68^{2}\equiv -9({{\,\mathrm{mod}\,}}4633)\), \(69^{2}\equiv 128({{\,\mathrm{mod}\,}}4633)\).
If b is a B-number, \(b^{2} {{\,\mathrm{mod}\,}}n\) represents the minimum nonnegative residue of \(b^{2}\) under \({{\,\mathrm{mod}\,}}n\), by the definition,Let \(e=\{e_{1},e_{2},\ldots ,e_{h}\} \in \mathbb {F}_{2}^{h}\) be an h-dimensional binary vector, definee is called the binary vector corresponding to b if \(\{b_{i}\}=A\) is a set of B-numbers. The binary vector corresponding to each \(b_{i}\) is denoted as \(e_{i}=\{e_{i_{1}},e_{i_{2}}, \ldots , e_{i_{h}}\} \), denote \(b_{i}^{2} {{\,\mathrm{mod}\,}}n\) with \(a_{i}\). We haveSuppose \(\sum _{i \in A}e_{i}=(0,0, \ldots , 0)\) is the zero vector in \(\mathbb {F}^{h}_{2}\), thenThat is, \(\prod a_{i}\) is a square number. Let \(r_{j}=\frac{1}{2}\sum _{i \in A}\alpha _{ij}\), thenOn the other hand, \(b_{i} {{\,\mathrm{mod}\,}}n\) represents the minimum nonnegative residue of \(b_{i}\) under \({{\,\mathrm{mod}\,}}n\), letwhere \(\delta _{i}=b_{i}{{\,\mathrm{mod}\,}}n\), that is \(0\le \delta _{i}<n\), and \(b_{i}\equiv \delta _{i}({{\,\mathrm{mod}\,}}n)\), thusBecause of \(a_{i}=b_{i}^{2} {{\,\mathrm{mod}\,}}n \), that is \(0\le a_{i}<n\), and \(b_{i}^{2}\equiv a_{i}({{\,\mathrm{mod}\,}}n)\). There isTwo different integers b and c defined by Eqs. (5.29) and (5.30) satisfy \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n)\), We write the above analysis as the following lemma.
$$\begin{aligned} b^{2} {{\,\mathrm{mod}\,}}n= \prod ^{h}_{i=1}p_{i}^{\alpha _{i}}, \alpha _{i}\ge 0. \end{aligned}$$
$$\begin{aligned} e_{j}= {\left\{ \begin{aligned}&0,\ \ \text {if}~\alpha ^{j}~ \text {is even};\\&1,\ \ \text {if}~\alpha ^{j} ~\text {is odd}. \end{aligned} \right. } \ \ 1\le j\le h. \end{aligned}$$
$$\begin{aligned} \prod _{i \in A}a_{i}=\prod ^{h}_{j=1}p_{j}^{\sum _{i \in A}\alpha _{ij}}, ~\text {where}~ a_{i}=\prod ^{h}_{j=1}p_{j}^{\alpha _{ij}}, \end{aligned}$$
$$\begin{aligned} \sum _{i \in A}\alpha _{ij}\equiv 0({{\,\mathrm{mod}\,}}2), \forall ~1\le j\le h. \end{aligned}$$
$$\begin{aligned} \prod _{i \in A}a_{i}=\left( \prod ^{h}_{j=1}p_{j}^{r_{j}}\right) ^{2}, \text {define}~c=\prod ^{h}_{j=1}p_{j}^{r_{j}}, \end{aligned}$$
(5.29)
$$\begin{aligned} b=\prod _{i \in A}(b_{i}{{\,\mathrm{mod}\,}}n)=\prod _{i \in A}\delta _{i}, \end{aligned}$$
(5.30)
$$\begin{aligned} \prod _{i \in A}b_{i}\equiv b({{\,\mathrm{mod}\,}}n). \end{aligned}$$
$$\begin{aligned} \prod _{i \in A}b_{i}^{2}=b^{2}\equiv \prod _{i \in A}a_{i}=c^{2}({{\,\mathrm{mod}\,}}n). \end{aligned}$$
Lemma 5.18
Let \(A=\{b_{1},b_{2},\ldots , b_{i},\ldots \}\) be a finite set of some B-numbers, let \(e_{i}=(e_{i_{1}}, e_{i_{2}},\ldots , e_{i_{h}}) \in \mathbb {F}^{h}_{2}\) be the binary vector corresponding to \(b_{i}\), \(a_{i}=b_{i}^{2}{{\,\mathrm{mod}\,}}n\), \(\delta _{i}=b_{i}{{\,\mathrm{mod}\,}}n\). If \(\sum _{i \in A}e_{i}=0\) is the zero vector in \( \mathbb {F}^{h}_{2}\), then \(\prod _{i \in A}a_{i}\) is a square number. WritewhereFurther let \(b=\delta _{1}\delta _{2}\cdots \), we have \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n)\).
$$\begin{aligned} a_{i}= \prod ^{h}_{j=1}p_{j}^{\alpha _{ij}}, ~ \prod _{i \in A} a_{i}=\prod ^{h}_{j=1}p_{j}^{\sum _{i \in A}\alpha _{ij}}=c^{2}. \end{aligned}$$
$$\begin{aligned} c=\prod ^{h}_{j=1}p_{j}^{\frac{1}{2}\sum _{i \in A}\alpha _{ij}}, \end{aligned}$$
From the above lemma, if \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n)\), \(b\not \equiv \pm c({{\,\mathrm{mod}\,}}n)\). Then we will find a nontrivial factor \(d=(b+c,n)\) of n. Now the question is, if \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n)\), how likely is \(b\not \equiv \pm c({{\,\mathrm{mod}\,}}n)\)? Might as well make \((b,n)=(c,n)=1\), otherwise both sides are divided by \((b,n)^{2}\): by \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n), \Longrightarrow (bc^{-1})^{2}\equiv 1({{\,\mathrm{mod}\,}}n)\). The problem is transformed into how many solutions x are in \(x^{2}\equiv 1({{\,\mathrm{mod}\,}}n)\), \(1\le x<n\).
Lemma 5.19
Let n be an odd number, then the number of solutions of \(x^{2}\equiv 1({{\,\mathrm{mod}\,}}n)\) is \(2^{r}\), where r is the number of different prime factors of n.
Proof
If \(r=1\), then \(n=p^{\alpha }(\alpha \ge 1)\), p is an odd prime, now \(x^{2}\equiv 1({{\,\mathrm{mod}\,}}p^{\alpha })\) has two solutions \(x=\pm 1\), because let g be the original root of \({{\,\mathrm{mod}\,}}p^{\alpha }\), then \(x=g^{t}(1\le t\le p^{\alpha -1}(p-1))\), \(x^{2}=1\Leftrightarrow p^{\alpha -1}(p-1)|2t\). So there are only two solutions \(t=\frac{1}{2}p^{\alpha -1}(p-1)\) and \(t=p^{\alpha -1}(p-1)\). So \(x\equiv \pm 1({{\,\mathrm{mod}\,}}p^{\alpha })\). If \(n=p_{1}^{\alpha _{1}}\cdots p_{r}^{\alpha _{r}}\), then the number of solutions of \(x^{2}\equiv 1({{\,\mathrm{mod}\,}}n)\) deduced from the Chinese remainder theorem is \(2^{r}\). The Lemma holds!
Lemma 5.20
n is an odd number and is the product of the power of more than two different primes, \(B=\{p_{1},p_{2},\ldots ,p_{h}\}\) is a factor base. Randomly select two B-numbers b and c, then \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n), \Longrightarrow b\equiv \pm c({{\,\mathrm{mod}\,}}n)\)’s rate is \(\le \frac{1}{2}\).
Proof
\(x^{2}\equiv 1({{\,\mathrm{mod}\,}}n)\) has \(2^{r}\) different solutions \(({{\,\mathrm{mod}\,}}n)\), \(r\ge 2\). The two solutions corresponding to \(x\equiv \pm 1({{\,\mathrm{mod}\,}}n)\) correspond to \(b\equiv \pm c({{\,\mathrm{mod}\,}}n)\). ThusLemma 5.20 holds.
$$\begin{aligned} b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n), \Longrightarrow b\equiv \pm c({{\,\mathrm{mod}\,}}n) \text {'s rate}~\le \frac{2}{2^{r}}\le \frac{1}{2}, \end{aligned}$$
According to Lemma 5.20, b and c are selected by using factor basis, if \(b\equiv \pm c({{\,\mathrm{mod}\,}}n)\), then select failure, and the probability of failure is \(\le \frac{1}{2}\). If the selection fails, select another \(b_{1}\) and \(c_{1}\), in this way, we randomly select k b and c equally almost independently, and the probability of success of \(b\not \equiv \pm c({{\,\mathrm{mod}\,}}n)\) isIn other words, the probability of finding a nontrivial factor \(d=(b+c,n)\) of n by using the factor base can be infinitely close to 1. Below, we systematically summarize the factor base decomposition method as follows:
$$\begin{aligned} P\{b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n),b\not \equiv \pm c({{\,\mathrm{mod}\,}}n)\}\ge 1-\frac{1}{2^{k}}. \end{aligned}$$
(5.31)
Factor-based method
Let n be a large odd number and y be an appropriately selected integer (e.g., \(y\le n^{\frac{1}{10}}\)), let the factor base beSelect a certain number of B-number at random, \(A_{1}=\{b_{1},b_{2},\ldots ,b_{N}\}\), usually \(N\le \pi (y)+2\) will meet the needs. Each \(b_{i}\) is expressed as the product of prime numbers in B. Calculate the corresponding binary vector \(e_{i}\), select a subset \(A\subset A_{1}\) in \(A_{1}\), such that \(\sum _{i \in A}e_{i}=0\), \(b_{i}\) corresponding to binary vector \(e_{i}\), denote as \(A=\{b_{1},b_{2},\ldots ,b_{i},\ldots \}\). LetandWe have \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n)\), if \(b\equiv \pm c({{\,\mathrm{mod}\,}}n)\), then reselect the subset A, Until finally \(b \not \equiv \pm c({{\,\mathrm{mod}\,}}n)\), in this way, we find a nontrivial factor d|n of n, \(d=(b+c,n)\). Therefore, there is factorization \(n=d\cdot \frac{n}{d}\).
$$\begin{aligned} B=\{-1,p\mid p~\text {is prime}, ~p\le y\}. \end{aligned}$$
$$\begin{aligned} b=\prod _{i \in A}(b_{i}{{\,\mathrm{mod}\,}}n)= \prod _{i \in A}\delta _{i}, ~\text {where}~\delta _{i}=b_{i} {{\,\mathrm{mod}\,}}n \end{aligned}$$
$$\begin{aligned} c= \prod _{j \in B}p_{j}^{r_{j}} {{\,\mathrm{mod}\,}}n , ~r_{j}=\frac{1}{2}\sum _{i \in A}\alpha _{ij}. \end{aligned}$$
Factor decomposition using factor-based method cannot guarantee the success rate of \(100\%\) because \(b \not \equiv \pm c({{\,\mathrm{mod}\,}}n)\) cannot be deduced from \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}n)\), however, the success probability of factorization for large odd n can be infinitely close to 1. Under the condition of success probability \(\ge 1-\frac{1}{2^{k}}\) (k is a given normal number), the computational complexity of factorization n of by factor-based method can be estimated asThe proof of Formula (5.32) is relatively complex. No detailed proof is given here. Interested readers can refer to pages 136–141 of Pomerance (1982a) in reference 5. The exact value of C in (5.32) is unknown. It is generally guessed that \(C=1+\varepsilon \), where \(\varepsilon >0\) is any small positive real number.
$$\begin{aligned} \mathrm{Time}(\text {factor-based method to}~ n ~\text {factorization})=O(\mathrm{e}^{c\sqrt{\log n \log \log n}}). \end{aligned}$$
(5.32)
Let k be the number of bits of n, and the estimate on the right of (5.32) can be written as \(O(\mathrm{e}^{c\sqrt{k\log k}})\). Therefore, the computational complexity of the factor-based method is sub-exponential. Compared with the Monte Carlo method introduced in the previous section (see (5.31)), its computational complexity is exponential, becauseAs we all know, the security of RSA public key cryptography is based on the prime factorization \(n=pq\) of n. Although there is no general method to factorize any large odd n, although Monte Carlo method and factor-based method are probability calculation methods, the probability of successful factorization is very large, The disadvantage is that their computational complexity is exponential and sub exponential, which is the reason for choosing huge prime numbers p and q in RSA.
$$\begin{aligned} O(\sqrt{n})=O(\mathrm{e}^{c_{1}k}), ~\text {where}~c_{1}=\frac{1}{2}\log 2. \end{aligned}$$
5.5 Continued Fraction Method
In the factor-based method introduced in the previous section, \(b^{2}{{\,\mathrm{mod}\,}}n\) can be the residual of the minimum absolute value of \(b^{2}\) under \({{\,\mathrm{mod}\,}}n\), that isIn this way, \(b^{2}{{\,\mathrm{mod}\,}}n\) can be decomposed into the product of some smaller prime numbers. The continued fraction method is the best method at present. How to find the integer b, so that \(|b^{2}{{\,\mathrm{mod}\,}}n|<2\sqrt{n}\), \(b^{2}{{\,\mathrm{mod}\,}}n\) is more likely to be decomposed into the product of some small prime numbers. First, we introduce what is continued fraction and some basic properties.
$$b^{2}\equiv b^{2}{{\,\mathrm{mod}\,}}n({{\,\mathrm{mod}\,}}n),~|b^{2}{{\,\mathrm{mod}\,}}n|\le \frac{n}{2}.$$
Suppose \(x\in \mathbb {R}\) is a real number, [x] is the integer part of x, and \(\{x\}\) is the decimal part of x. Let \(a_{0}=[x]\), if \(\{x\}\ne 0\), and let \(a_{1}=[\frac{1}{\{x\}}]\), because of \(x=[x]+\{x\}\), there isIf \(\{\{x\}^{-1}\}\ne 0\), writeconsiderSo we gotThe above formula is called the continued fraction expansion of real number x. To save space, write \(x=[a_{0},a_{1},\ldots ,a_{n},\ldots ]\), if and only if x is a rational number, the continued fraction of x is expanded to be finite, denote asIt is called the standard expansion of rational number x.
$$x=a_{0}+\frac{1}{\{x\}}=a_{0}+\frac{1}{a_{1}+\{\{x\}^{-1}\}}.$$
$$a_{2}=[\{\{x\}^{-1}\}^{-1}],$$
$$\{\{\{x\}^{-1}\}^{-1}\}^{-1},$$
$$x=a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\cdots }}}.$$
$$x=[a_{0},a_{1},\ldots ,a_{n}],~\text {where}~a_{n}>1.$$
Definition 5.6
\(x=[a_{0},a_{1},\ldots ,a_{n},\ldots ]\) is the continued fraction expansion of x, for \(i\ge 0\), call \(\frac{b_{i}}{c_{i}}=[a_{0},a_{1},\ldots ,a_{i}]\) the ith asymptotic fraction of x, specially,
$$\frac{b_{0}}{c_{0}}=\frac{a_{0}}{1}, ~\frac{b_{1}}{c_{1}}=\frac{a_{1}a_{0}+1}{a_{1}}.$$
The progressive fraction \(\frac{b_{i}}{c_{i}}\) of the real number x is a reduced fraction, that is \((b_{i},c_{i})=1\), and has the following properties.
Lemma 5.21
\(x=[a_{0},a_{1},\ldots ,a_{n},\cdots ]\) is the continued fraction expansion of x, \(\frac{b_{i}}{c_{i}}\) is the asymptotic fraction, then
(i)
when \(i\ge 2\),
$$\begin{aligned} \frac{b_{i}}{c_{i}}=\frac{a_{i}b_{i-1}+b_{i-2}}{a_{i}c_{i-1}+c_{i-2}}. \end{aligned}$$
(5.33)
(ii)
If \(i\ge 1\), then
$$\begin{aligned} b_{i}c_{i-1}-b_{i-1}c_{i}=(-1)^{i-1}. \end{aligned}$$
(5.34)
Proof
We prove that (i) by induction. Obviously, the proposition of \(i=2\) holds, that isIf the proposition holds for i, that isThen write \([a_{0},a_{1},\ldots ,a_{i},a_{i+1}]=[a_{0},a_{1},\ldots ,a_{i}+\frac{1}{a_{i+1}}]\),So (i) holds.
$$\frac{b_{2}}{c_{2}}=\frac{a_{2}b_{1}+b_{0}}{a_{2}c_{1}+c_{0}}=\frac{a_{2}(a_{1}a_{0}+1)+a_{0}}{a_{2}a_{1}+1}.$$
$$\frac{b_{i}}{c_{i}}=\frac{a_{i}b_{i-1}+b_{i-2}}{a_{i}c_{i-1}+c_{i-2}}.$$
$$\frac{b_{i+1}}{c_{i+1}}=\frac{\left( a_{i}+\frac{1}{a_{i+1}}\right) b_{i-1} +b_{i-2}}{\left( a_{i}+\frac{1}{a_{i+1}}\right) c_{i-1}+c_{i-2}}=\frac{a_{i+1}b_{i}+b_{i-1}}{a_{i+1}c_{i}+c_{i-1}}.$$
We prove Formula (5.34) by induction, when \(i=1\),So when \(i=1\), the proposition holds, and when i, the proposition holds, that isThenLemma 5.21 holds.
$$b_{1}c_{0}-b_{0}c_{1}=a_{1}a_{0}+1-a_{1}a_{0}=1=(-1)^{0}.$$
$$b_{i}c_{i-1}-b_{i-1}c_{i}=(-1)^{i-1}.$$
$$\begin{aligned} \begin{aligned} b_{i+1}c_{i}-b_{i}c_{i+1}&=(a_{i+1}b_{i}+b_{i-1})c_{i}-b_{i}(a_{i+1}c_{i}+c_{i-1})\\&=b_{i-1}c_{i}-b_{i}c_{i-1}\\&=(-1)^{i}. \end{aligned} \end{aligned}$$
Continued fractions have many important applications in numbers, such as rational approximation of real numbers and rational approximation of algebraic numbers. Periodic continued fractions are an important special case in rational approximation of algebraic numbers. \(x=[a_{0},a_{1},\ldots ,a_{n},\ldots ]\). If these \(a_{i}\) occur in cycles of a certain length, they are called periodic continued fractions. The famous Lagrange theorem shows that the necessary and sufficient condition for the expansion of the continued fraction of x into a periodic continued fraction is that x is a quadratic real algebraic number. Here we do not discuss some profound properties of continued fractions, but only prove some properties we need.
Lemma 5.22
Let \(x>1\) be a real number, \(\frac{b_{i}}{c_{i}}(i\ge 0)\) is the asymptotic fraction of x, then
$$|{b_{i}}^{2}-x^{2}c_{i}^{2}|<2x, \forall ~ i\ge 0.$$
Proof
Because x is between progressive scores \(\frac{b_{i}}{c_{i}}\) and \(\frac{b_{i+1}}{c_{i+1}}\), by property (ii) of Lemma 5.21, there isThusSoThe Lemma holds.
$$\left| \frac{b_{i+1}}{c_{i+1}}-\frac{b_{i}}{c_{i}}\right| =\frac{1}{c_{i}c_{i+1}},i\ge 0.$$
$$\begin{aligned} \begin{aligned} |{b_{i}}^{2}-x^{2}c_{i}^{2}|&=c_{i}^{2}\left| x-\frac{b_{i}}{c_{i}}\right| \left| x+\frac{b_{i}}{c_{i}}\right| \\&<c_{i}^{2}\cdot \frac{1}{c_{i}c_{i+1}}\left( x+\left( x+\frac{1}{c_{i}c_{i+1}}\right) \right) . \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} |{b_{i}}^{2}-x^{2}c_{i}^{2}|-2x&<2x \left( -1+\frac{c_{i}}{c_{i+1}}+\frac{1}{2xc_{i+1}^{2}}\right) \\&<2x \left( -1+\frac{c_{i}}{c_{i+1}}+\frac{1}{c_{i+1}}\right) \\&<2x \left( -1+\frac{c_{i+1}}{c_{i+1}}\right) =0. \end{aligned} \end{aligned}$$
Lemma 5.23
Let n be a positive integer and n not a complete square. Let \(\{\frac{b_{i}}{c_{i}}\}_{i\ge 0}\) be the asymptotic fraction of the continued fraction expansion of \(\sqrt{n}\), and \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\) be the residue of the minimum absolute value of \(b_{i}^{2}\) under \({{\,\mathrm{mod}\,}}n\), then we have
$$b_{i}^{2}{{\,\mathrm{mod}\,}}n <2\sqrt{n},~ \forall ~ i\ge 0.$$
Proof
By Lemma 5.22, let \(x=\sqrt{n}\), thenBecauseThe Lemma holds.
$$b_{i}^{2}\equiv b_{i}^{2}-nc_{i}^{2}({{\,\mathrm{mod}\,}}n).$$
$$|b_{i}^{2}-nc_{i}^{2}|<2\sqrt{n}, \Longrightarrow b_{i}^{2} {{\,\mathrm{mod}\,}}n<2\sqrt{n}, ~\forall ~ i\ge 0.$$
Combining the above Lemma 5.23 with the factorization method, we obtain the continued fraction decomposition method.
Continued fraction decomposition method:
The operations of \({{\,\mathrm{mod}\,}}n\) involved in this algorithm, except that it is specially pointed out, are the minimum nonnegative residue of \({{\,\mathrm{mod}\,}}n\). If n is a large odd number, it is also a compound number, first let \(b_{-1}=b\), \(b_{0}=a_{0}=[\sqrt{n}]\), and \(x_{0}=\sqrt{n}-a_{0}=\{\sqrt{n}\}\), calculate \(b_{0}^{2}{{\,\mathrm{mod}\,}}n\), in fact, \(b_{0}^{2}{{\,\mathrm{mod}\,}}n=b_{0}^{2}-n\). Second, consider \(i=1,2,\ldots \). To determine \(b_{i}\), we proceed in several steps:
1.
Let \(a_{i}=[\frac{1}{x_{i-1}}]\), and \(x_{i}=\frac{1}{x_{i-1}}-a_{i}(i\ge 1).\)
2.
Let \(b_{i}=a_{i}b_{i-1}+b_{i-2}\), the minimum nonnegative residual \(b_{i}{{\,\mathrm{mod}\,}}n\) of \(b_{i}\) under \({{\,\mathrm{mod}\,}}n\) is still recorded as \(b_{i}\).
3.
calculate \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\).
By Lemma 5.23, \(b_{i}^{2}{{\,\mathrm{mod}\,}}n <2\sqrt{n}\), it can be decomposed into the product of some small prime numbers. If a prime number p appears in the decomposition of two or more \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\), or in the decomposition of an \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\), p appears to an even power, p is called a standard prime number, in other words, a standard prime p isOrWe choose factor base B asIn this way, all \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\) are B-numbers, and the corresponding binary vector is \(e_{i}\). Select a subset \(A=\{b_{i}\}, \Longrightarrow \sum _{i\in A}e_{i}=0\). Letand \(c=\prod _{j\in B}p_{j}^{r_{j}}\), whereIf \(b\not \equiv \pm c({{\,\mathrm{mod}\,}}n)\), then \((b+c,n)\) is a nontrivial factor of n, and we obtain the factorization of n. If \(b \equiv \pm c({{\,\mathrm{mod}\,}}n)\), then another subset A is selected and repeated to complete the continued fraction factorization method.
$$p|b_{i}^{2}{{\,\mathrm{mod}\,}}n, ~p|b_{j}^{2}{{\,\mathrm{mod}\,}}n,i\ne j.$$
$$p^{\alpha }\Vert b_{i}^{2}{{\,\mathrm{mod}\,}}n, ~\alpha ~\text {is even}.$$
$$B=\{-1,~\text {standard prime}\}.$$
$$b=\prod _{i\in A}(b_{i}{{\,\mathrm{mod}\,}}n)=\prod _{i\in A}\delta _{i}$$
$$r_{j}=\frac{1}{2}\sum _{i\in A}\alpha _{ij}, \forall j\in B.$$
Example 5.8
The continued fraction method is used to factorize \(n=9073\).
Solution: We calculate \(a_{i}\), \(b_{i}\) and \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\) in turn, where \(b_{i}=(a_{i}b_{i-1}+b_{i-2}){{\,\mathrm{mod}\,}}n\), the table is as follows:
i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
\(a_{i}\) | 95 | 3 | 1 | 26 | 2 |
\(b_{i}\) | 95 | 286 | 381 | 1119 | 2619 |
\(b_{i}^{2}{{\,\mathrm{mod}\,}}n\) | \(-48\) | 139 | \(-7\) | 87 | \(-27\) |
From the value of \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\), we can choose the factor base B as \(B=\{-1,2,3,7\}\). Then \(b_{i}^{2}{{\,\mathrm{mod}\,}}n\) is the number of B-number, when \(i=0,2,4,\ldots \). The corresponding binary vector isEasy to calculate \(e_{0}+e_{4}=(0,0,0,0)\). Therefore, we chooseBecause \(b^{2}\equiv c^{2}({{\,\mathrm{mod}\,}}9073)\), that is \(3834^{2}=36^{2}({{\,\mathrm{mod}\,}}9073)\), but \(3834\not \equiv \pm 36({{\,\mathrm{mod}\,}}9073)\), so we get a nontrivial factor of \(n=9073\), \(d=(3834+36,9073)=43\). Thus \(9073=43\cdot 211\), the factorization of 9073 is obtained.
$$e_{0}=(1,4,1,0), e_{2}=(1,0,0,1), \text {and}~e_{4}=(1,0,3,0).$$
$$ {\left\{ \begin{array}{ll} \ b=95\cdot 2619\equiv 3834{{\,\mathrm{mod}\,}}9073 ;\\ \ c=2^{2}\cdot 3^{2}=36. \end{array}\right. } $$
Exercise 5
1.
p is a prime, if and only if \(b^{p-1}\equiv 1({{\,\mathrm{mod}\,}}p^{2})\), \(p^{2}\) to base b is a Fermat pseudo prime.
2.
What is the minimum pseudo prime number with Fermat pseudo prime for base 5? What is the minimum Fermat pseudo prime number for base 2?
3.
\(n=pq\), \(p\ne q\) are two primes, let \(d=(p-1,q-1)\), it is proved that n to base b is Fermat pseudo prime number, if and only if \(b^{d}\equiv 1({{\,\mathrm{mod}\,}}n)\), and calculate the number of bases b.
4.
If \(b\in \mathbb {Z}_{n}^{*}\), n to base b is Fermat pseudo prime, then n to base \(-b\) and b are Fermat pseudo prime numbers.
5.
If n to base 2 is Fermat pseudo prime, then \(N=2^{n}-1\) is also Fermat pseudo prime.
6.
If n to base b is Fermat pseudo prime, and \((b-1,n)=1\), then \(N=\frac{b^{n}-1}{b-1}\) to base b is also Fermat pseudo prime.
7.
Prove that the following integers are Carmichael numbers:
$$1105=5\cdot 13\cdot 17, 1729=7\cdot 13\cdot 19, 2465=5\cdot 17\cdot 29, 2821=7\cdot 13\cdot 31, $$
$$ 6601=7\cdot 23\cdot 41, 29{,}341=13\cdot 37\cdot 61, 172{,}081=7 \cdot 13 \cdot 31 \cdot 61, 278{,}545=5\cdot 17\cdot 29\cdot 113.$$
8.
Find all Carmichael numbers of form 3pq and all Carmichael numbers of form 5pq.
9.
Prove that 561 is the minimum Carmichael number.
10.
If n to base 2 is a Fermat pseudo prime, prove \(N=2^{n}-1\) is a strong pseudo prime.
11.
There are infinite Euler pseudo primes and strong pseudo primes for base 2.
12.
If n to base b is a strong pseudo prime, then n to base \(b^{k}\) is also a strong pseudo prime for any integer k.
13.
The Fermat factorization method is used to decompose the positive integer as follows:
$$n=8633, n=809{,}009, n=92{,}296{,}873, n=88{,}169{,}891.$$
14.
The Fermat factorization method is used to decompose the positive integer as follows:
$$n=68{,}987, n=29{,}895{,}581, n=19{,}578{,}079, n=17{,}018{,}759.$$
15.
Expand the rational number \(x=\frac{45}{89}, x=\frac{55}{89}, x=1.13\) into continued fractions.
16.
Let a be a positive integer, \(x=[a,a,a,\cdots ]\), calculate \(x=?\)
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.