Mathematical basis of information security Chapter 4 -- quadratic residual and square root

Definition 4.1 set up m As a positive integer , If the congruence $x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m),(a,m)=1$, Have solution , be a It's called a model m Quadratic residue of , Otherwise it is called a module m Quadratic non residual

Definition 4.2 Legendre symbol ：$(\frac{a}{p})$, When a For the mould p The second remaining time of , The value is 1; Not 2 Time remaining value is -1, if $p|a$ Then the value is 0

Theorem 4.1 p As a prime number , if $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$, be $(\frac{a}{p})=(\frac{b}{p})$
Congruence $x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$ The solution of can be seen as in a finite field ${\mathbb{Z}}_p$ Find the polynomial in $x^2-a$ The root of the .

Theorem 4.2 Euler's criterion ：p Is an odd prime number , For any integer a,$(\frac{a}{p})\equiv a^{\frac{p-1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$
prove ：
set up $g$ yes ${\mathbb{Z}}_p$ The original elements of , be ${\mathbb{Z}}_p^{\ast }=\{g^0,g^1,...,g^{p-2}\}$
For all $0\le i\le \frac{p-1}{2}$,$(g^{2i}{)}^{\frac{p-1}{2}}=(g^{p-1}{)}^i=1,(g^{2i+1}{)}^{\frac{p-1}{2}}=(g^{p-1}{)}^i{g}^{\frac{p-1}{2}},g^{\frac{p-1}{2}}=-1$（ from g We know from the original $g^{\frac{p-1}{2}}\ne 1$, but $(g^{\frac{p-1}{2}}{)}^2=1$, So it can only be -1）, so $(g^{\frac{p-1}{2}}{)}^{2i+1}=-1$
Due to the consideration of module p The quadratic congruence of , therefore a You can view it as ${\mathbb{Z}}_p$ The element equivalent to its congruence in
When $a\equiv g^{2i}(\mathrm{m}\mathrm{o}\mathrm{d}p),0\le i<\frac{p-1}{2}$, polynomial $x^2-a=x^2-g^{2i}$ Rooted ±gⁱ, so $(\frac{a}{p})=1\equiv a^{\frac{p-1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$
When $a\equiv g^{2i+1}(\mathrm{m}\mathrm{o}\mathrm{d}p),0\le i<\frac{p-1}{2}$, polynomial $x^2-a=x^2-g^{2i+1}$ There must be no root . Otherwise, if $x_0^2=g^{2i+1}$, that $1=(x_0^2{)}^{\frac{p-1}{2}}=(g^{2i+1}{)}^{\frac{p-1}{2}}=-1$ contradiction . so $(\frac{a}{p})=-1\equiv a^{\frac{p-1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$

According to the above Theorem , model p The quadratic remainder of is $\frac{p-1}{2}$ individual （ All even powers of primitive ）

inference set up p Is an odd prime number , be
$(\frac{1}{p})=1$
$(\frac{-1}{p})=(-1{)}^{\frac{p-1}{2}}$
$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$
$(\frac{a^n}{p})=(\frac{a}{p}{)}^n,n>0$

Theorem 4.3 set up p Is an odd prime number , be $(\frac{2}{p})=(-1{)}^{\frac{p^2-1}{8}}$
prove ： Proof of construction
$(p-1)!\equiv 1\cdot 3\cdot 5\cdot ...\cdot (p-2)\cdot 2\cdot 4\cdot ...\cdot (p-1)$
about 4k+1 Type p Yes
$\equiv 1\cdot (p-2)\cdot 3\cdot (p-4)\cdot 5\cdot ...\cdot \frac{p-3}{2}\cdot (p-\frac{p-1}{2})\cdot 2^{\frac{p-1}{2}}\cdot (\frac{p-1}{2}!)(\mathrm{m}\mathrm{o}\mathrm{d}p)$（ All the even numbers in the last half are mentioned 2 come out , The first half can be alternately mentioned -1）
$\equiv (-1{)}^{\frac{p-1}{4}}\cdot 2^{\frac{p-1}{2}}\cdot (\frac{p-1}{2}!{)}^2(\mathrm{m}\mathrm{o}\mathrm{d}p)$
about 4k+3 Type p Yes
$\equiv 1\cdot (p-2)\cdot 3\cdot (p-4)\cdot 5\cdot ...\cdot (p-\frac{p-3}{2})\cdot \frac{p-1}{2}\cdot 2^{\frac{p-1}{2}}\cdot (\frac{p-1}{2}!)(\mathrm{m}\mathrm{o}\mathrm{d}p)$
$\equiv (-1{)}^{\frac{p-3}{4}}\cdot 2^{\frac{p-1}{2}}\cdot (\frac{p-1}{2}!{)}^2(\mathrm{m}\mathrm{o}\mathrm{d}p)$
Wilson Theorem know $(p-1)!\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$, And $(\frac{p-1}{2}!{)}^2\equiv (-1{)}^{\frac{p+1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$（ Turn into $(-1{)}^{\frac{p-1}{2}}(p-1)!$） Know when $p\equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}8)$ when ,$2^{\frac{p-1}{2}}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$, When $p\equiv \pm 3(\mathrm{m}\mathrm{o}\mathrm{d}8)$ when ,$2^{\frac{p-1}{2}}\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$, Comprehensive verification shows that $2^{\frac{p-1}{2}}\equiv (-1{)}^{\frac{p^2-1}{8}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$, According to Euler's rule $(\frac{2}{p})=(-1{)}^{\frac{p^2-1}{8}}$

Theorem 4.4 The law of quadratic reciprocity ：p,q Is a mutually prime odd prime number , be $(\frac{q}{p})=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}(\frac{p}{q})$
prove ： It's too complicated , No need to master

Definition 4.3 Jacobi symbols ：$m={\prod }_{i=1}^n{p}_i,p_i$ It's an odd prime , For any integer a Definition a model m The Jacobian symbol of is $(\frac{a}{m})={\prod }_{i=1}^n(\frac{a}{p_i})$,m When it is an odd prime number , Its Jacobian symbol is Legendre symbol .

Theorem 4.5 set up m Positive odd number ,$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)\Rightarrow (\frac{a}{m})=(\frac{b}{m})$

Theorem 4.6 set up m Positive odd number , be
(1) $(\frac{1}{m})=1$
(2) $(\frac{ab}{m})=(\frac{a}{m})(\frac{b}{m})$
(3) $(\frac{a^n}{m})=(\frac{a}{m}{)}^n$
(4) $(\frac{-1}{m})=(-1{)}^{\frac{m-1}{2}}$
(5) $(\frac{2}{m})=(-1{)}^{\frac{m^2-1}{8}}$

Theorem 4.7 set up m,n Positive odd number , be $(\frac{n}{m})=(-1{)}^{\frac{m-1}{2}\frac{n-1}{2}}(\frac{m}{n})$

Definition 4.4 Quadratic residual problem ： Unknown n In the case of the decomposition of , Generally judge an integer a Whether it is a module n The quadratic residue of is a difficult problem , It is called quadratic residual problem .

encryption algorithm 1——Rabin encryption algorithm
Alice Select two 4k+3 Prime of type （ be called Blum prime number ）p,q, Calculation n=pq, take p,q Public as private key n.
encryption ： Plaintext is an integer m, Ciphertext c=m²(mod n)
Decrypt ： Solve the congruence equation c=x²(mod n) You can get 4 A solution , Choose the meaningful solution as the plaintext m.

computing method ——a=x²(mod p),p=4k+3 Solution method
If the above formula has a solution , It's in [0,p-1] There must be a solution , Therefore, when the number is not large, it can be used to a Keep adding p Until you find a perfect square （ This method is right p nothing 4k+3 The limitation of , however p It is inconvenient when it is very big ）
from $(\frac{a}{p})=1$ According to Euler's rule $a^{\frac{p-1}{2}}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$, There are $(a^{\frac{p-1}{4}}{)}^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$, Therefore, the solution is $x\equiv \pm a^{\frac{p-1}{4}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$

encryption algorithm 2——Goldwasser-Micali encryption algorithm
Alice Choose two different prime numbers p,q, And integer y Satisfy $(\frac{y}{p})=(\frac{y}{q})=-1$. Calculation n=pq,p and q The seat private key is public n,y
encryption ： Convert binary integers m As clear text , The first i The place is marked as b_i, For everyone , Random selection 0<x_i<n, If the bit is 0 Calculation c_i=x_i²(mod n), Otherwise, calculate c_i=yx_i²(mod n), Ciphertext for all c
Decrypt ： if c_i For the mould n Quadratic residue of , Then judge b_i=0, otherwise b_i=1

Definition 4.5 set up <g> Is an element that consists of g The generated one n Metacyclic group , Then for any a∈<g>, There is 0≤i<n,a=gⁱ, call i For g Bottom a Indicators of , Write it down as ind_ga. The problem of finding indicators , In cryptography, it is usually called discrete logarithm problem .n It is a difficult problem to solve the discrete logarithm problem when the integer is large enough .

Theorem 4.8 set up <g> It's a n Metacyclic group ,a∈<g>, If for a positive integer m Yes ：
(1) a^m=e
(2) For any prime factor p|m,$a^{\frac{m}{p}}\ne e$, be ord(a)=m, And m|n

Definition 4.8 Primordial root ： set up m As a positive integer , Integers a Satisfy (a,m)=1,a model m The order of ord_m(a) Refer to a(mod m) stay ${\mathbb{Z}}_m^{\ast }$ Order in ; If ${\mathbb{Z}}_m^{\ast }$ Is a cyclic group , Integers a It's called a model m The primordial root of means a(mod m) by ${\mathbb{Z}}_m^{\ast }$ The generator of

According to the above definition ,a In the mold m Modulo of all integers in the remaining classes m All orders are ord_m(a)

According to the original root definition ： When m=2,4 when , model m The original roots are 1,3
In a general way , If and only if m=2,4,p^a,2p^a（p Is an odd prime number ,a≥1）, model m It has roots

Theorem 4.9 set up <g> It's a n Metacyclic group ,a,b∈<g>, be ind_gab$\equiv$ind_ga+ind_gb(mod n)
prove ：ind_ga=x,ind_gb=y, be g^x+y=ab=$g^{in{d}_{g}ab}$
namely $g^{x+y-in{d}_{g}ab}=e$, also ord(g)=n, so n|x+y-ind_gab, Therefore, the conclusion is tenable

Definition 4.9 set up m It is greater than 1 The positive integer , If n Second congruence xⁿ=a(mod m), (a,m)=1 Have solution , be a It is called a module m Of n The second surplus , Otherwise, it is a module m Of n Secondary non residual .

Theorem 4.14 （ High order residue ） set up m For more than 1 The positive integer ,g For the mould m One of the original roots ,(a,m)=1,d=(n,$\phi$(m)), that xⁿ=a(mod m) The necessary and sufficient condition for a solution is $a^{\frac{\phi (m)}{d}}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$
prove ：g For the mould m One of the original roots , therefore ${\mathbb{Z}}_m^{\ast }=<g>,x^n\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$ The necessary and sufficient condition for a solution is $in{d}_g{x}^n=in{d}_{g}a\Rightarrow nin{d}_{g}x\equiv in{d}_{g}a(\mathrm{m}\mathrm{o}\mathrm{d}\phi (m))$（ Pay attention to the mold m The cyclic group of is only $\phi (m)$ Elements , Therefore, it is necessary to mold $\phi (m)$！）, Make X=ind_gx, Then there are $nX\equiv in{d}_{g}a(\mathrm{m}\mathrm{o}\mathrm{d}\phi (m))$
The necessary and sufficient condition for the first congruence to have a solution is (n,φ(m))|ind_ga, namely d|ind_ga, Equivalent to ind_ga$\equiv$ 0(mod d)
From theorem 2.4(4) Yes $\frac{\phi (m)}{d}in{d}_{g}a\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}\phi (m))$. Take... On both sides “ Index ” have to $a^{\frac{\phi (m)}{d}}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$, So the original proposition holds .

notes ： The theorem can also help to solve the number of solutions of high-order congruence . For congruence $ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$, The necessary and sufficient condition for its solution is $(a,m)|b$, And the general solution can be written as $x=x_0+\frac{m}{(a,m)}t,t=0,1,...,(a,m)-1$ In the form of , So the number of solutions is $(a,m)$. that $nX\equiv in{d}_{g}a(\mathrm{m}\mathrm{o}\mathrm{d}\phi (m))$ The solution of should have $(n,\phi (m))$ individual