Tomcat
Professional
- Messages
- 2,689
- Reaction score
- 963
- Points
- 113
A brief introduction to the mathematical foundations of cryptography will help you understand the features of many well-known cryptographic algorithms. Let's start by defining the most important concepts, and also present the algebra results used in the initial cryptography course.
An integer a divides another integer b, symbolically this is denoted a | B if and only if b = da for some integer d. In this case, a is called a divisor or factor of b.
Let a - an integer greater than 1. Then, as called simple number if its only divisors are 1 and itself as well. Otherwise, a is called a composite number. Any integer n > 1 can be represented uniquely up to the order of factors as a product of primes (the main theorem of arithmetic).
The greatest common divisor of the numbers a and b (denoted by GCD (a, b), or simply (a, b)) is the largest integer dividing a and b at the same time . In other words, (a, b) is the only natural number that divides a and b and itself is divisible by any integer dividing both a and b.
The least common multiple of a and b, LCM (a, b), is the smallest natural number divisible by both a and b.
The greatest common divisor of the numbers a and b (a > b) can be calculated using the Euclidean algorithm. The algorithm is represented by the following chain of equalities:
Ql - C kQ.k + l-
The stopping of the algorithm is guaranteed, since the remainders from division with, form a strictly decreasing sequence of natural numbers.
From the above chain of equations we obtain that c k = (a, b). Indeed, from the last lower equation of the chain it follows that c fc | c fc _p From the penultimate equation, taking into account that | with to _ 1; we obtain that c fc | c fc _ 2 . Climbing upwards, we will successively prove that c fc | c fc _ 3 , ..., c k | with g , with k | B, with k | a. In other words, c k is a common divisora and b.
Now let r divide a and b (r is an arbitrary divisor of a and b). Then from the first equation of the chain we obtain that r | with 15 out of the second - what r | from 2 . Descending to the lower equation, we obtain that r | c k , that is, we will prove that c k = (a, b).
Obviously, from the chain of equations с, = c, +1 q, +1 + с, +2 , taking into account the decreasing sequence с, the inequality с,> 2с, +2 follows . From this we obtain that a > 2 '" / 2 , where m is the number of equations in the chain, and that, therefore, to find (a, b), it is required to perform no more than 21og 2 a divisions with a remainder (log 2 x denotes the logarithm of a positive real number x to the base 2, that everywhere in this register denoted logx).
Since division, like multiplication, of two numbers having a length of I bits in binary representation requires O (Z 2 ) elementary processor operations, finding the greatest common divisor of a and b numbers requires O ((log a) 3 ). An elementary operation is understood to be an "atomic" operation for a computer processor (for example, shifting a data line to the left by one bit, adding a zero bit to the right, adding two bits, etc.).
Here and below, for two functions f (x) and g (x)> 0 defined in the domain D, we use the notation f (x) = O (g (x)) if there exists a constant K > 0 such that | / ( x) | <Kg (x) for all x g?>.
Finally, we will show that indeed O ((logn) 2 ) elementary operations are required to multiply two numbers modulo n . Indeed, multiplication "in a column" of two numbers that have O (logn) signs in the binary representation will reduce first to performing O (logn) left shifts of the row representing the first factor of the product, and then to summing O (log and) resulting shifts lines. Both row shift and their summation require O ((logn) 2 ) elementary operations.
Another important result follows from the chain of equations presented above. From the upper equation of the chain it is easy to express the quantity c } as a linear combination of the quantities a and b and substitute it into the second equation of the chain. Then, from the second equation of the chain, we can express the quantity c 2 as a linear combination of the quantities a and b and substitute it into the third equation of the chain. As a result, going down to the last equation, we get that:
(a, b) = xa + yb, (A1)
for some integers x and y. Obviously, to find such a representation of the greatest common divisor of the numbers a and b , O ((log a) 3 ) operations are required .
Two integers a and b are called coprime if (a, b) = 1. The fact mutually prime numbers and and b has denoted a ± b.
Two integers a and b are called comparable modulo a natural number m if their difference a - b is divisible by m without a remainder. This is expressed by the following notation:
a = b (mod t) (A2)
The number m is called the modulus of comparison. If we fix the comparison module m, then any integer c can be unambiguously represented as:
s = kt + g, (AZ)
where r is the remainder coinciding with one of the m numbers 0, ..., m - 1. The remainder r is also called the residue of the number c modulo m.
The set of all integers c satisfying equation (A3) is called the residue class r modulo m. In other words,
r - {c: c = r (mod m)}.
The set of all residues 0, 1, ..., (m - 1) modulo m is denoted by Z m .
If (a, m) - 1, then (A1) implies the existence of integers x and y such that 1 - xa 4- ym. Hence xa = 1 (mod m). The number x from the last comparison is called the inverse of a modulo m and is denoted by a, n . The complexity of finding the reciprocal is the same as that of Euclid's algorithm - O ((logm) 3 ). It also follows that the comparison az = b (mod m) with (a, m) = 1 can be solved with respect to z in cubic time of the length of the binary representation m . To find zfirst we calculate a ' 1 , and then we multiply it on the right by b. Any z of the form z = a ~ „b + + tm, where t is an arbitrary integer, is a solution of the equation under consideration.
Note that if (a, m) = 1, then u (a,; 1 , m) - 1.
Let pits be relatively prime positive integers. Then the system of equations
x = a (mod u)
x = b (mod m)
has a unique solution x in the residue class Z nm .
The last statement is called the Chinese remainder theorem. Below is a proof of this theorem.
From the first equation of the system follows x - Nn + a. Substituting this expression for x into the second equation, we get:
Nn = (b - a) (mod m).
Since the pits are coprime numbers, there exists n ~ such that the equality nn " 1 = 1 (mod m) holds . Hence, we obtain:
N = (b - a} n m l (mod m)
or for some integer M:
N = (b - a) n “ 1 4- Mt.
Substituting the last equality in the expression for x, we get:
x - (b - a) n ~ } + Mmn + a,
Q.E.D.
A group is a non-empty set G of elements of an arbitrary nature, on which a binary operation is specified, usually called multiplication, for which the following properties are satisfied:
The following theorem holds.
For the subset H to be a subgroup of the group G, it is necessary and sufficient that two conditions be satisfied:
Let us prove the sufficiency. Let Н be a subset of G and conditions (1) and (2) are satisfied. Let us prove that H is a group. Indeed, let us take some element h e H. Then it follows from condition (2) that h ' 1 e H, and hence from condition (1) h / r -1 = e e H.
The associativity condition is easily proved. If h 2 , h 2 , h 3 e H, then from condition (1) it follows (/ r ] / r 2 ) / r 3 e H and g H. Further, since
simultaneously (/ Z] / i 2 ) / i 3 e G and / 1] (/ z 2 / z 3 ) g G, and in the group G the associativity law holds, the equality (/ z x / z 2 ) / z 3 = ^ 1 (^ 2 ^ h) -
Let H - subgroup of G and g e G - arbitrary element of the group G. The set of all possible products gh, where h g H is called the coset (or rather left coset) mod N, and an element g - its representative. The coset with the representative g in the subgroup H is denoted by gH.
For cosets, two things are true:
Let us prove the second statement. Let there exist h 2 , h 2 e H such that gjhi = g 2 h 2 . Then, obviously, for any h ∈ H , g A h = g 2 h 2 h ^ h, that is, gji with g 2 H, and g 2 h = gjijtjh, that is, g 2 H with g x H ...
Thus, from the existence of a common element for two cosets of the same group - g 2 h 2 ), it follows that these cosets coincide (g } H = g 2 H).
In the case when the subgroup H of the group G and G are finite groups of orders m and r, respectively, the representation
c = u "A 1 = 1
and it follows from the statements proved above for cosets that r - m. In other words, the following Lagrange theorem holds: the order of any subgroup of a finite group is a divisor of the order of the group.
Consider the so-called cyclic subgroups that any group possesses. With any element g ∈ G one can associate a cyclic subgroup "generated" by it, which, in essence, is the smallest of the subgroups containing the element g. To define it, we introduce the concept of the degree of an element g. As usual, for any natural k we define g * as k - the multiple product of g and itself. Next, we define g ° = e, g ~ k = (g k ) ~
With such a definition of the degree, the well-known rules of working with degrees apply: for any integers of type, the equalities gT = g m + n > = g mn -
Obviously, if g ∈ G is an element of a finite group, then there exists a natural I such that g 1 = e, a g 'e for i = 1, ..., I - 1. The number I is called the order of an element g in the group G . If for some n we have g "= e, then 1 1 n (if n = kl + t, where I> t > 0, then g c = e, which contradicts the definition of the order of an element).
The degrees g 1 , g 2 , ..., g 1 = е form a cyclic subgroup G g of order I, and the element g is called the generating element of the subgroup. Indeed, the set of degrees g contains the identity ^ = e. For each element g 1 ∈ G ? there is an element g , - 'e G g , which is its inverse. Finally, the associativity law is satisfied for the multiplication operation, and the multiplication operation is closed in G, y for any natural m and n,not exceeding I, the equalities are satisfied g "'g" = g m + n = g * e G g > where 0 <5 < I is the remainder of dividing m 4- n by I.
Since G s is a subgroup of G, by Lagrange's theorem 1 1 n, where n is the order of G.
It may happen that for some element g the cyclic subgroup generated by it coincides with the whole group G. In this case, the group G is called cyclic, and the element g is called a generator element of the group.
It follows from Lagrange's theorem that if the order of the group G is a prime number, then the group is cyclic, and every element of the group, with the exception of the identity element e, is its generating element. Such a group contains only two subgroups: G itself and {e}.
Euler's function <p
of a natural number n is defined as the number of natural numbers a <n, such that (a, u) = 1. If n = p, where p is a prime number, then <p (p) = p - 1. If n = p ' n , where p is a prime number, then φ (p' n ) = p t - p t -
Let us prove the last equality. Obviously, a number a <p m is not coprime with p m if and only if a = cp for some
integer 1 < r <p '" -1 . Then the number of numbers coprime to p' n is equal to p m - 1 - (p m-1 - 1) = p ' n - p m-1 , which was required to prove.
For the Euler function, the following important statement is fulfilled, which makes it possible to calculate the value of the function for any natural n. If (m, u) = 1, then φ (mn) = φ (m) φ.
Indeed, (x, mn) = 1 if and only if simultaneously (x, m) = 1 and (x, u) = 1. Let a and b be the remainders of dividing x by n and m, respectively. Then comparisons are made:
x = a (mod u)
x = b (mod t)
(A4)
Obviously, from (x, n) = 1 and (x, m) = 1 it follows (a, u) - 1 and (b, m) = 1.
Conversely, let (a, u) = 1 and (b, m) = 1 for some pair a <u and b <m. Then, by the Chinese remainder theorem, in the residue class Z nm there is a unique solution x satisfying the system of comparisons (A4 ). In addition, due to (a, n) = 1 and (b, m) = 1, (x, mn) = 1.
Thus, we have proved that for any x < mn such that (x, mn) = 1, there is a unique pair a <n and b <m such that (a, n) - 1 and (b, m) - 1. Moreover, the converse is also true: for any pair a <n and b <m such that (a, n) - 1 and (b, m) = 1, there is a unique non-negative x < mn such that (x, mn) = 1. Hence follows the assertion φ (mn) = φ (m) φ for (m, n) = 1.
For some natural number η, consider the set U of natural numbers a <u, coprime to u. As a binary operation defined on (Di), we consider the usual multiplication mod n. Let us show that U is a group of order φ . Obviously, the unit of the group is the number 1. Further, as shown above, for any a <u coprime to n, there is a number a ' 1 < n such that na' 1 = 1 (mod n) and a - 1 e U . Finally, the associativity of the operation follows from the associativity of the multiplication.
Take an arbitrary number a ∈ U. Let its order be equal to I, i.e. a 1 = 1 (mod n). Since the elements a ' (mod n) for i = 1, ..., I form a subgroup U , it follows from Lagrange's theorem that 1 1 φ . But then for all a ∈ U is true a vW = 1 (mod n).
If we now consider any positive integer c coprime to n, then obviously c = b (mod n) for some integer be E7. Then the equality holds with φ = b φ = 1 (mod u). In other words, we have proved Euler's theorem: if (c, n) = 1, then c vWl = 1 (mod u).
Euler's theorem implies that if n is a prime number not dividing c, then c n-1 = 1 (mod n). This result is called Fermat's little theorem and is widely used in cryptography.
Let us continue our brief excursion into algebra and introduce the concept of a ring. A ring is a non-empty set K, on which two operations are defined, conditionally called addition and multiplication, which have the following properties:
Important examples of rings are the set of integers with addition and multiplication operations, the set of residue classes modulo n.
The definition of a ring does not require multiplication to be commutative. In the case when the multiplication has this additional property, the ring is called commutative.
Multiplication in a ring, like in a group, is an associative operation, but other properties of group multiplication in a ring may not be fulfilled. True, most of the rings important in practice contain a unit element with respect to multiplication. But even such rings contain elements for which there is no converse (irreversible elements). In any ring, the element 0 is irreversible, which is the unit element of the additive group of the ring. Nonzero ring elements can also be irreversible.
A commutative ring with unity in which every nonzero element is invertible is called a field. By virtue of this definition, the set of nonzero elements of the field forms a commutative group with respect to multiplication, which is called the multiplicative group of the field.
It is easy to prove that the residue ring modulo a prime p is a field, which is called the field of residues modulo p.
In algebra, it is proved that in an arbitrary finite field the number of elements q is always a prime power: q = p p . The converse is also true: for any q that is a prime power, there is a field with q elements.
Finite fields are called Galois fields and are denoted by GF (q), where q is the number of field elements. An important property of finite fields used in cryptography and coding theory is that the multiplicative group of the Galois field is a cyclic group of order q - 1. The generating element of the multiplicative group of the Galois field is called the primitive element of the field.
To illustrate what was said above, we prove that the multiplicative group of the residue field modulo a prime p is cyclic. Let us also describe an algorithm for finding all generating elements of this multiplicative group.
We first prove the following lemma.
Lemma 1. If an abelian group G contains two elements of orders r and s, then the group contains an element whose order is equal to the LCM (r, s) (the least common multiple of r and s).
We denote by a and b the elements of the group G of orders r and s, respectively. Let us decompose the orders of r and s into prime factors:
Γ = p e 1 '• - -Pk and s = p { ] • ... -p ?,
where p b , ..., p a - prime numbers appearing in the representation of r and s.
Without loss of generality, the prime factors in the representations r and s are written in such an order that for some 1 < m <k the following inequalities hold:
e 1 - / 1> e 2 - A> •••> e m - fm And e m + l < fn + b •••> e k < fk-
We denote r 0 = p? ? ... • p% and s 0 = p?; • ... •
Obviously, (r 0 , s 0 ) = 1. Further, we denote r = r o r b s = and c = a r 'b c '. Let n be the order of the element c, i.e.
with n = e. (A5)
Obviously, c r, | S ° = e, that is, n | r o s o . Let us raise both sides of equality (A5) to the power r 0 :
c r o n _ QVin ^ s ^ on _ e
Note that the resulting representation is valid only if the multiplication operation in the group commutes.
Since a r ° r ' n = e, we obtain b s ' r ° n = e, and hence 5 0 | r 0 n. Since (r 0 , s 0 ) - 1, it follows that $ 0 1 n.
Similarly, raising both sides of equality (A5) to the power s 0 , one can prove that r 0 | n. Taking into account n | r o s o , we obtain that n = r 0 $ 0 . Thus, the statement of Lemma 1 is proved.
Let us now prove Lemma 2: Let f (x) be a polynomial of degree k with integer coefficients and the leading coefficient (coefficient at x *) equal to 1. If p is a prime number, then f (x) has at most k roots in the ring Z p.
We prove the lemma by induction on the degree of the polynomial m. If m = 1, then f (x) = x + b and the corresponding equation has only one solution -b in Z p , that is, the lemma is true.
Suppose now that any polynomial of degree k - 1 with leading coefficient 1 has at most k - 1 roots in Z p . Let us show that this assumption implies a similar statement for a polynomial of degree k with leading coefficient 1.
Let f (x) be a polynomial of degree k with leading coefficient 1. If f (x) has no roots in Z p , then the assertion is proved. Let f (x) still have a root a e Z p , that is, f (a) = 0 (mod p) (here a is a representative of the residue class a). Then, obviously, the representation f (x) takes place:
/ (x) = (xa) q (x) + / (a),
where the degree of q (x) is k - 1.
The last equality is equivalent to:
/ (x) = (x - a) q (x) (mod p). (A6)
Let p a e the Z p - is another root of / (x) in the 7th district (if there is such a root, the lemma is proved). This means that f (p) = 0 (modp), but p a (mod p).
Substituting in (A6) P instead of x, we get:
О = ЛР) = (Р - a) q (p) (mod р).
Since p is a prime number, it follows from the last equation that q (P) = 0 (mod p). In other words, since P is a root of a polynomial different from a, it follows that p is also a root of the polynomial q (x) in Z p . Hence it follows that in Z p the function f (x) can have only one root more than q (x). And since, by the induction hypothesis, q (x) has at most k - 1 roots in Z p , the polynomial f (x) has at most k roots in Z p , as required.
We now denote by E7 (p) the set of all nonzero residues modulo p. Then the theorem on primitive roots holds: if p is a prime number, then U (p) is a cyclic group.
Take an element a 1 e (p) of order k r . If k r = p - 1, then the assertion of the theorem is proved. If k } <p - 1, then cc e <7 (p) satisfies the equation
x k ' - 1 = O in Z p . Since p is a prime number, it follows from Lemma 2 that the equation x k ' - 1 = 0 has at most roots in Z p . On the other hand, all elements of the set H - {1, of, ..., are different and are the roots of the equation x k ' - 1 = 0 in Z p .
Because, by assumption, to } <p - 1, in group [Ap) contains an element b x e [Ap) such that b & N. Let r - procedure b. Obviously, r does not altogether divide k b since otherwise b is a root x k ' - 1 = 0 in Z p and, therefore, b & H, which contradicts the assumption. But then, in accordance with the result of Lemma 1, using a, e [Dp) and b e [Dp), one can construct an element [Dp) of order k 2 = LCM (k15 d)> k } .
Further, if k 2 = p - 1, the resulting element is a generator of the group u (p). Otherwise, everything is repeated with the constructed element of order k 2 . Obviously, since the sequence k is bounded from above, after a finite number of steps an element of the group of order p - 1 will be found, which is the generating element of the group [Ap).
Let g ∈ [Δp) be a generating element of the group U (p), I be a number coprime to p - 1. Then g l is also a generating element of the group [Δp). Let s be the order of the element g l , that is, g ls = 1. Since р - 1 is the order of the element g, the relation (р - 1) | Is. Since by construction (Cp - 1), /) = 1, it follows from this that (p - 1) | s. On the other hand, equality = 1 holds. Hence it follows that s = р - 1, that is, the order of the element g ' is equal to p - 1, and therefore g 1 is a generating element of the group [7 (p).
It follows from what was proved above that the group [Ap) contains φ (p - 1) different generators.
Consider some prime p> 2. If for a ∈ GF (p) there exists an element xe GF (p) such that a = x ^ (modp), then a is called a quadratic residue modulo p. Otherwise, when the equation a = N (mod p) has no solutions, but is called a quadratic nonresidue mod p.
The above definition of a quadratic residue can also be formulated as follows. If g is a generator element of the multiplicative group of the field GF (p), then a is called a quadratic residue modulo p if a = g * (mod p) for some natural k. If for a ∈ GF (p) for some natural k, a - g 2k + i (mod p), then a is called a quadratic nonresidue mod p.
Indeed, in this case it is impossible to find an x ∈ GF (p) such that a = x 2 (mod p), because if such x existed, then it would immediately follow the equality a = g 2k (mod p) for some k. Thus, there are altogether (p - 1) / 2 quadratic residues and non-residues.
The Legendre symbol in the case of an integer a and a prime p > 2 is determined by the equality:
Oh, if p | a
• 1 if a is a quadratic residue modulo p -1, if a is a quadratic nonresidue mod p.
It is clear that the meaning of the Legendre symbol is the same for two integers comparable to each other modulo p.
Let us prove the following result: if m is a prime number, then for all a the equality holds:
(—1 = a (, n “ 1) / 2 (mod zn). (A7)
m)
If t | a, then equality (A7) is obvious. If a is a quadratic residue modulo m, then the left side of equality (A7) is equal to 1 and, in addition, a can be represented as a - g 2k (mod m) for some natural k. Taking this into account, the right side of equality (A7 ) takes the form g k (m-1) (mod m) and, by Fermat's little theorem, g fc (m-1) = 1 (mod m). Thus, (A7) is proved.
If a is a quadratic nonresidue modulo m, then the left side of (A7) is equal to -1 and, in addition, a can be represented as a = g 2k +} (mod m) for some natural k. Taking this into account, the right side of (A7 ) takes the form g ^^ - D + t " 1 - 1 ^ 2 and in the FORM of Fermat's little theorem g« m - 1 ) + < m - 1 ^ 2 = g (ra - 1) / 2 (mod m).
Fermat's little theorem implies the equality:
^ op-n / r + _ 1} = 0 (mod m y
Since the second factor of the last equality cannot be compared with zero modulo m, since m - 1 is the order of the generating element g, we obtain from this that
g (m ' 1) / 2 = ( mod
Thus, equality (A7) is proved in this case as well.
It follows from the proved statement that
In addition, the following properties of the Legendre symbol can be proved:
{P) [Pj [P)
• for any primes p> 2 and q> 2, the equality - =
/ (PD (qI)
= - • (-1) 4 , which expresses the reciprocity law for square
<1)
technical deductions.
The Jacobi symbol is a generalization of the Legendre symbol for the case of an arbitrary odd number. Consider an integer a and an odd m > 2. Let m = pj 1 • ... • p k k be the factorization of m into prime factors. Then the Jacobi symbol is defined as the product of the corresponding powers of the Legendre symbols:
a
Pi
a
P to
Let us prove the following theorem: if m is an odd composite number, then at most half of the integers a, where (a, m) = 1 and 1 <a <m, satisfy condition (A7), in which the transformation on the left-hand side of the comparison is now understood as Jacobi symbol.
First, we construct a such that (A7) does not hold for a = a. Depending on the representation m = p ['• ...? p k k consider two cases.
Case 1. Suppose that among the numbers q, ..., i k there is a number that is strictly greater than 1. Without loss of generality, we assume q > 2. Then we put a = 1 + m / p { .
„(Os'},„ „
Let us prove that - = 1. Really,
m I
(A8)
Because for everyone; = 1, ..., k , by virtue of the definition of a, the comparison a = 1 (mod p ; ) holds , then it follows from (A7) that each factor in the right
I OS]
part (A8) is equal to 1, whence it follows - = 1.
On the other side,
a (ml) / 2 = (1 + m / pi) (mD / 2 =
(t-1) t (t t ~ 1 Y 2 (t-1) t
= 1 + - + ... + - = 1 + - (mod t).
ennogo element and wrong.
Case 2. The equalities = ... = i k = 1 hold, that is, m = P1 • ... • Pk . Let s be an arbitrary quadratic nonresidue modulo Р1 . Let us construct an element a so that it simultaneously satisfies two comparisons: a = s (mod P1 ) and a = 1 (mod m / P1 ).
Since the moduli of the above congruences are coprime numbers, in accordance with the Chinese remainder theorem, there is a unique element a up to comparison modulo m that simultaneously satisfies these congruences.
From the comparison a = 1 (mod m / P] ) it follows that a = 1 (mod Pj ) for all; - 2, ..., k. It is easy to see that
_ ( aa
f a ^ for all j - 2, ..., k. Further, by virtue of a = 5 (mod P1 ), we have - = -1.
(а 1 v J
So - = -1.
(m)
If equality (A7) was valid, then from the obtained result it would follow that a (m “ 1) / 2 = -1 (mod m), ie there would be an integer C such that a ( '"' 1) / 2 = cC P -1.
j = i
Since a = 1 (mod m / P1 ) holds, the relation a (m-1) / 2 = 1 to
(mod m / P1 ), that is, there exists an A such that a (m-1) / 2 = A] ^ [ Pj + 1. Hence, we obtain k > 2
it is assumed that P [ P / (C P] - A) = 2, which is not true for any integer values> 2
A and C. Consequently, the assumption a ( '"“ 1) / 2 = -1 (mod m) is incorrect.
Thus, for any number of composite T was constructed as such that equation (A7) with a = not performed.
Consider now all integers 1 <ω, < m, (ω ,, m) - 1, 1 < i <t, satisfying (A7). Then, obviously, all numbers of the form
u = ω, a (mod m), 1 < i <t
are different and satisfy the conditions 1 <u, < m, (u if m) = 1.
If some satisfies (A7), then this means that the comparison is performed:
(mod t).
Since ω, satisfy (A7), it follows from this:
(t-1) / 2 =
OS
T
(mod m),
which contradicts the fact that a does not satisfy (A7). Thus, the statement of the theorem is proved.
The assertion of the theorem underlies the Solovey – Strassen simplicity test used in the RSA algorithm in the procedure for finding large primes.
For the Jacobi symbol, the results are similar to those formulated earlier for the Legendre symbol:
• for any odd m > 2 the equality | | = 1,
/ _- | (t-1) W)
• for any a, o and odd m > 2, if a = b (mod m), then - 1 = 1 -;
m) t)
t) mjmj t ) t )
n) t)
The latter property is called the law of reciprocity. It allows one to significantly simplify the procedure for calculating the Jacobi symbol and is widely used in the Solovey – Strassen method for checking a number for simplicity (see Appendix B).
Appendix B
An integer a divides another integer b, symbolically this is denoted a | B if and only if b = da for some integer d. In this case, a is called a divisor or factor of b.
Let a - an integer greater than 1. Then, as called simple number if its only divisors are 1 and itself as well. Otherwise, a is called a composite number. Any integer n > 1 can be represented uniquely up to the order of factors as a product of primes (the main theorem of arithmetic).
The greatest common divisor of the numbers a and b (denoted by GCD (a, b), or simply (a, b)) is the largest integer dividing a and b at the same time . In other words, (a, b) is the only natural number that divides a and b and itself is divisible by any integer dividing both a and b.
The least common multiple of a and b, LCM (a, b), is the smallest natural number divisible by both a and b.
The greatest common divisor of the numbers a and b (a > b) can be calculated using the Euclidean algorithm. The algorithm is represented by the following chain of equalities:
| a = bq l + c 15 | 0 < | = C1 * | 'B; |
| B = csh 2 + c 2 , | 0 < | ' С 2 < | = q; |
| С 1 = * -2 ^ 3 + | 0 < | ' С 3 < | = s 2 ; |
| C k-2 = C k-1 Chk + C k> | 0 < | : Ck < | ' C k-1> |
Ql - C kQ.k + l-
The stopping of the algorithm is guaranteed, since the remainders from division with, form a strictly decreasing sequence of natural numbers.
From the above chain of equations we obtain that c k = (a, b). Indeed, from the last lower equation of the chain it follows that c fc | c fc _p From the penultimate equation, taking into account that | with to _ 1; we obtain that c fc | c fc _ 2 . Climbing upwards, we will successively prove that c fc | c fc _ 3 , ..., c k | with g , with k | B, with k | a. In other words, c k is a common divisora and b.
Now let r divide a and b (r is an arbitrary divisor of a and b). Then from the first equation of the chain we obtain that r | with 15 out of the second - what r | from 2 . Descending to the lower equation, we obtain that r | c k , that is, we will prove that c k = (a, b).
Obviously, from the chain of equations с, = c, +1 q, +1 + с, +2 , taking into account the decreasing sequence с, the inequality с,> 2с, +2 follows . From this we obtain that a > 2 '" / 2 , where m is the number of equations in the chain, and that, therefore, to find (a, b), it is required to perform no more than 21og 2 a divisions with a remainder (log 2 x denotes the logarithm of a positive real number x to the base 2, that everywhere in this register denoted logx).
Since division, like multiplication, of two numbers having a length of I bits in binary representation requires O (Z 2 ) elementary processor operations, finding the greatest common divisor of a and b numbers requires O ((log a) 3 ). An elementary operation is understood to be an "atomic" operation for a computer processor (for example, shifting a data line to the left by one bit, adding a zero bit to the right, adding two bits, etc.).
Here and below, for two functions f (x) and g (x)> 0 defined in the domain D, we use the notation f (x) = O (g (x)) if there exists a constant K > 0 such that | / ( x) | <Kg (x) for all x g?>.
Finally, we will show that indeed O ((logn) 2 ) elementary operations are required to multiply two numbers modulo n . Indeed, multiplication "in a column" of two numbers that have O (logn) signs in the binary representation will reduce first to performing O (logn) left shifts of the row representing the first factor of the product, and then to summing O (log and) resulting shifts lines. Both row shift and their summation require O ((logn) 2 ) elementary operations.
Another important result follows from the chain of equations presented above. From the upper equation of the chain it is easy to express the quantity c } as a linear combination of the quantities a and b and substitute it into the second equation of the chain. Then, from the second equation of the chain, we can express the quantity c 2 as a linear combination of the quantities a and b and substitute it into the third equation of the chain. As a result, going down to the last equation, we get that:
(a, b) = xa + yb, (A1)
for some integers x and y. Obviously, to find such a representation of the greatest common divisor of the numbers a and b , O ((log a) 3 ) operations are required .
Two integers a and b are called coprime if (a, b) = 1. The fact mutually prime numbers and and b has denoted a ± b.
Two integers a and b are called comparable modulo a natural number m if their difference a - b is divisible by m without a remainder. This is expressed by the following notation:
a = b (mod t) (A2)
The number m is called the modulus of comparison. If we fix the comparison module m, then any integer c can be unambiguously represented as:
s = kt + g, (AZ)
where r is the remainder coinciding with one of the m numbers 0, ..., m - 1. The remainder r is also called the residue of the number c modulo m.
The set of all integers c satisfying equation (A3) is called the residue class r modulo m. In other words,
r - {c: c = r (mod m)}.
The set of all residues 0, 1, ..., (m - 1) modulo m is denoted by Z m .
If (a, m) - 1, then (A1) implies the existence of integers x and y such that 1 - xa 4- ym. Hence xa = 1 (mod m). The number x from the last comparison is called the inverse of a modulo m and is denoted by a, n . The complexity of finding the reciprocal is the same as that of Euclid's algorithm - O ((logm) 3 ). It also follows that the comparison az = b (mod m) with (a, m) = 1 can be solved with respect to z in cubic time of the length of the binary representation m . To find zfirst we calculate a ' 1 , and then we multiply it on the right by b. Any z of the form z = a ~ „b + + tm, where t is an arbitrary integer, is a solution of the equation under consideration.
Note that if (a, m) = 1, then u (a,; 1 , m) - 1.
Let pits be relatively prime positive integers. Then the system of equations
x = a (mod u)
x = b (mod m)
has a unique solution x in the residue class Z nm .
The last statement is called the Chinese remainder theorem. Below is a proof of this theorem.
From the first equation of the system follows x - Nn + a. Substituting this expression for x into the second equation, we get:
Nn = (b - a) (mod m).
Since the pits are coprime numbers, there exists n ~ such that the equality nn " 1 = 1 (mod m) holds . Hence, we obtain:
N = (b - a} n m l (mod m)
or for some integer M:
N = (b - a) n “ 1 4- Mt.
Substituting the last equality in the expression for x, we get:
x - (b - a) n ~ } + Mmn + a,
Q.E.D.
A group is a non-empty set G of elements of an arbitrary nature, on which a binary operation is specified, usually called multiplication, for which the following properties are satisfied:
- 1. For any two elements a, b ∈ G, their product also belongs to G.
- 2. The law of associativity is fulfilled: for any a, b, with e. G it is true (ab) c = a (bc).
- 3. There is a unit element e in G such that ea = ae - a for any a ∈ G.
- 4. For any a ∈ G there is an inverse element a -1 g G such that a ~ 'a = a' 1 = e.
The following theorem holds.
For the subset H to be a subgroup of the group G, it is necessary and sufficient that two conditions be satisfied:
- 1) if /? I e H and h 2 e H, then iD 2 e H;
- 2) if h e H, then / r -1 e N.
Let us prove the sufficiency. Let Н be a subset of G and conditions (1) and (2) are satisfied. Let us prove that H is a group. Indeed, let us take some element h e H. Then it follows from condition (2) that h ' 1 e H, and hence from condition (1) h / r -1 = e e H.
The associativity condition is easily proved. If h 2 , h 2 , h 3 e H, then from condition (1) it follows (/ r ] / r 2 ) / r 3 e H and g H. Further, since
simultaneously (/ Z] / i 2 ) / i 3 e G and / 1] (/ z 2 / z 3 ) g G, and in the group G the associativity law holds, the equality (/ z x / z 2 ) / z 3 = ^ 1 (^ 2 ^ h) -
Let H - subgroup of G and g e G - arbitrary element of the group G. The set of all possible products gh, where h g H is called the coset (or rather left coset) mod N, and an element g - its representative. The coset with the representative g in the subgroup H is denoted by gH.
For cosets, two things are true:
- 1. In the case of a finite subgroup H, the number of elements in any coset is the same and coincides with the order of the subgroup.
- 2. Any two cosets g } H and g 2 H either coincide or have no common elements.
Let us prove the second statement. Let there exist h 2 , h 2 e H such that gjhi = g 2 h 2 . Then, obviously, for any h ∈ H , g A h = g 2 h 2 h ^ h, that is, gji with g 2 H, and g 2 h = gjijtjh, that is, g 2 H with g x H ...
Thus, from the existence of a common element for two cosets of the same group - g 2 h 2 ), it follows that these cosets coincide (g } H = g 2 H).
In the case when the subgroup H of the group G and G are finite groups of orders m and r, respectively, the representation
c = u "A 1 = 1
and it follows from the statements proved above for cosets that r - m. In other words, the following Lagrange theorem holds: the order of any subgroup of a finite group is a divisor of the order of the group.
Consider the so-called cyclic subgroups that any group possesses. With any element g ∈ G one can associate a cyclic subgroup "generated" by it, which, in essence, is the smallest of the subgroups containing the element g. To define it, we introduce the concept of the degree of an element g. As usual, for any natural k we define g * as k - the multiple product of g and itself. Next, we define g ° = e, g ~ k = (g k ) ~
With such a definition of the degree, the well-known rules of working with degrees apply: for any integers of type, the equalities gT = g m + n > = g mn -
Obviously, if g ∈ G is an element of a finite group, then there exists a natural I such that g 1 = e, a g 'e for i = 1, ..., I - 1. The number I is called the order of an element g in the group G . If for some n we have g "= e, then 1 1 n (if n = kl + t, where I> t > 0, then g c = e, which contradicts the definition of the order of an element).
The degrees g 1 , g 2 , ..., g 1 = е form a cyclic subgroup G g of order I, and the element g is called the generating element of the subgroup. Indeed, the set of degrees g contains the identity ^ = e. For each element g 1 ∈ G ? there is an element g , - 'e G g , which is its inverse. Finally, the associativity law is satisfied for the multiplication operation, and the multiplication operation is closed in G, y for any natural m and n,not exceeding I, the equalities are satisfied g "'g" = g m + n = g * e G g > where 0 <5 < I is the remainder of dividing m 4- n by I.
Since G s is a subgroup of G, by Lagrange's theorem 1 1 n, where n is the order of G.
It may happen that for some element g the cyclic subgroup generated by it coincides with the whole group G. In this case, the group G is called cyclic, and the element g is called a generator element of the group.
It follows from Lagrange's theorem that if the order of the group G is a prime number, then the group is cyclic, and every element of the group, with the exception of the identity element e, is its generating element. Such a group contains only two subgroups: G itself and {e}.
Euler's function <p
of a natural number n is defined as the number of natural numbers a <n, such that (a, u) = 1. If n = p, where p is a prime number, then <p (p) = p - 1. If n = p ' n , where p is a prime number, then φ (p' n ) = p t - p t -Let us prove the last equality. Obviously, a number a <p m is not coprime with p m if and only if a = cp for some
integer 1 < r <p '" -1 . Then the number of numbers coprime to p' n is equal to p m - 1 - (p m-1 - 1) = p ' n - p m-1 , which was required to prove.
For the Euler function, the following important statement is fulfilled, which makes it possible to calculate the value of the function for any natural n. If (m, u) = 1, then φ (mn) = φ (m) φ
.Indeed, (x, mn) = 1 if and only if simultaneously (x, m) = 1 and (x, u) = 1. Let a and b be the remainders of dividing x by n and m, respectively. Then comparisons are made:
x = a (mod u)
x = b (mod t)
(A4)
Obviously, from (x, n) = 1 and (x, m) = 1 it follows (a, u) - 1 and (b, m) = 1.
Conversely, let (a, u) = 1 and (b, m) = 1 for some pair a <u and b <m. Then, by the Chinese remainder theorem, in the residue class Z nm there is a unique solution x satisfying the system of comparisons (A4 ). In addition, due to (a, n) = 1 and (b, m) = 1, (x, mn) = 1.
Thus, we have proved that for any x < mn such that (x, mn) = 1, there is a unique pair a <n and b <m such that (a, n) - 1 and (b, m) - 1. Moreover, the converse is also true: for any pair a <n and b <m such that (a, n) - 1 and (b, m) = 1, there is a unique non-negative x < mn such that (x, mn) = 1. Hence follows the assertion φ (mn) = φ (m) φ
for (m, n) = 1.For some natural number η, consider the set U
of natural numbers a <u, coprime to u. As a binary operation defined on (Di), we consider the usual multiplication mod n. Let us show that U is a group of order φ . Obviously, the unit of the group is the number 1. Further, as shown above, for any a <u coprime to n, there is a number a ' 1 < n such that na' 1 = 1 (mod n) and a - 1 e U . Finally, the associativity of the operation follows from the associativity of the multiplication.Take an arbitrary number a ∈ U
. Let its order be equal to I, i.e. a 1 = 1 (mod n). Since the elements a ' (mod n) for i = 1, ..., I form a subgroup U , it follows from Lagrange's theorem that 1 1 φ . But then for all a ∈ U is true a vW = 1 (mod n).If we now consider any positive integer c coprime to n, then obviously c = b (mod n) for some integer be E7
. Then the equality holds with φ = b φ = 1 (mod u). In other words, we have proved Euler's theorem: if (c, n) = 1, then c vWl = 1 (mod u).Euler's theorem implies that if n is a prime number not dividing c, then c n-1 = 1 (mod n). This result is called Fermat's little theorem and is widely used in cryptography.
Let us continue our brief excursion into algebra and introduce the concept of a ring. A ring is a non-empty set K, on which two operations are defined, conditionally called addition and multiplication, which have the following properties:
- 1. The set K forms a commutative group with respect to the addition operation.
- 2. Multiplication is associative, that is, for any a, b, c e K (ab) c = a (bc).
- 3. Addition and multiplication obey the distributive law, that is, for any a, b, c e K , the equalities (a + b) c = ac + bc and c (a + b) = ca + cb hold.
Important examples of rings are the set of integers with addition and multiplication operations, the set of residue classes modulo n.
The definition of a ring does not require multiplication to be commutative. In the case when the multiplication has this additional property, the ring is called commutative.
Multiplication in a ring, like in a group, is an associative operation, but other properties of group multiplication in a ring may not be fulfilled. True, most of the rings important in practice contain a unit element with respect to multiplication. But even such rings contain elements for which there is no converse (irreversible elements). In any ring, the element 0 is irreversible, which is the unit element of the additive group of the ring. Nonzero ring elements can also be irreversible.
A commutative ring with unity in which every nonzero element is invertible is called a field. By virtue of this definition, the set of nonzero elements of the field forms a commutative group with respect to multiplication, which is called the multiplicative group of the field.
It is easy to prove that the residue ring modulo a prime p is a field, which is called the field of residues modulo p.
In algebra, it is proved that in an arbitrary finite field the number of elements q is always a prime power: q = p p . The converse is also true: for any q that is a prime power, there is a field with q elements.
Finite fields are called Galois fields and are denoted by GF (q), where q is the number of field elements. An important property of finite fields used in cryptography and coding theory is that the multiplicative group of the Galois field is a cyclic group of order q - 1. The generating element of the multiplicative group of the Galois field is called the primitive element of the field.
To illustrate what was said above, we prove that the multiplicative group of the residue field modulo a prime p is cyclic. Let us also describe an algorithm for finding all generating elements of this multiplicative group.
We first prove the following lemma.
Lemma 1. If an abelian group G contains two elements of orders r and s, then the group contains an element whose order is equal to the LCM (r, s) (the least common multiple of r and s).
We denote by a and b the elements of the group G of orders r and s, respectively. Let us decompose the orders of r and s into prime factors:
Γ = p e 1 '• - -Pk and s = p { ] • ... -p ?,
where p b , ..., p a - prime numbers appearing in the representation of r and s.
Without loss of generality, the prime factors in the representations r and s are written in such an order that for some 1 < m <k the following inequalities hold:
e 1 - / 1> e 2 - A> •••> e m - fm And e m + l < fn + b •••> e k < fk-
We denote r 0 = p? ? ... • p% and s 0 = p?; • ... •
Obviously, (r 0 , s 0 ) = 1. Further, we denote r = r o r b s = and c = a r 'b c '. Let n be the order of the element c, i.e.
with n = e. (A5)
Obviously, c r, | S ° = e, that is, n | r o s o . Let us raise both sides of equality (A5) to the power r 0 :
c r o n _ QVin ^ s ^ on _ e
Note that the resulting representation is valid only if the multiplication operation in the group commutes.
Since a r ° r ' n = e, we obtain b s ' r ° n = e, and hence 5 0 | r 0 n. Since (r 0 , s 0 ) - 1, it follows that $ 0 1 n.
Similarly, raising both sides of equality (A5) to the power s 0 , one can prove that r 0 | n. Taking into account n | r o s o , we obtain that n = r 0 $ 0 . Thus, the statement of Lemma 1 is proved.
Let us now prove Lemma 2: Let f (x) be a polynomial of degree k with integer coefficients and the leading coefficient (coefficient at x *) equal to 1. If p is a prime number, then f (x) has at most k roots in the ring Z p.
We prove the lemma by induction on the degree of the polynomial m. If m = 1, then f (x) = x + b and the corresponding equation has only one solution -b in Z p , that is, the lemma is true.
Suppose now that any polynomial of degree k - 1 with leading coefficient 1 has at most k - 1 roots in Z p . Let us show that this assumption implies a similar statement for a polynomial of degree k with leading coefficient 1.
Let f (x) be a polynomial of degree k with leading coefficient 1. If f (x) has no roots in Z p , then the assertion is proved. Let f (x) still have a root a e Z p , that is, f (a) = 0 (mod p) (here a is a representative of the residue class a). Then, obviously, the representation f (x) takes place:
/ (x) = (xa) q (x) + / (a),
where the degree of q (x) is k - 1.
The last equality is equivalent to:
/ (x) = (x - a) q (x) (mod p). (A6)
Let p a e the Z p - is another root of / (x) in the 7th district (if there is such a root, the lemma is proved). This means that f (p) = 0 (modp), but p a (mod p).
Substituting in (A6) P instead of x, we get:
О = ЛР) = (Р - a) q (p) (mod р).
Since p is a prime number, it follows from the last equation that q (P) = 0 (mod p). In other words, since P is a root of a polynomial different from a, it follows that p is also a root of the polynomial q (x) in Z p . Hence it follows that in Z p the function f (x) can have only one root more than q (x). And since, by the induction hypothesis, q (x) has at most k - 1 roots in Z p , the polynomial f (x) has at most k roots in Z p , as required.
We now denote by E7 (p) the set of all nonzero residues modulo p. Then the theorem on primitive roots holds: if p is a prime number, then U (p) is a cyclic group.
Take an element a 1 e (p) of order k r . If k r = p - 1, then the assertion of the theorem is proved. If k } <p - 1, then cc e <7 (p) satisfies the equation
x k ' - 1 = O in Z p . Since p is a prime number, it follows from Lemma 2 that the equation x k ' - 1 = 0 has at most roots in Z p . On the other hand, all elements of the set H - {1, of, ..., are different and are the roots of the equation x k ' - 1 = 0 in Z p .
Because, by assumption, to } <p - 1, in group [Ap) contains an element b x e [Ap) such that b & N. Let r - procedure b. Obviously, r does not altogether divide k b since otherwise b is a root x k ' - 1 = 0 in Z p and, therefore, b & H, which contradicts the assumption. But then, in accordance with the result of Lemma 1, using a, e [Dp) and b e [Dp), one can construct an element [Dp) of order k 2 = LCM (k15 d)> k } .
Further, if k 2 = p - 1, the resulting element is a generator of the group u (p). Otherwise, everything is repeated with the constructed element of order k 2 . Obviously, since the sequence k is bounded from above, after a finite number of steps an element of the group of order p - 1 will be found, which is the generating element of the group [Ap).
Let g ∈ [Δp) be a generating element of the group U (p), I be a number coprime to p - 1. Then g l is also a generating element of the group [Δp). Let s be the order of the element g l , that is, g ls = 1. Since р - 1 is the order of the element g, the relation (р - 1) | Is. Since by construction (Cp - 1), /) = 1, it follows from this that (p - 1) | s. On the other hand, equality = 1 holds. Hence it follows that s = р - 1, that is, the order of the element g ' is equal to p - 1, and therefore g 1 is a generating element of the group [7 (p).
It follows from what was proved above that the group [Ap) contains φ (p - 1) different generators.
Consider some prime p> 2. If for a ∈ GF (p) there exists an element xe GF (p) such that a = x ^ (modp), then a is called a quadratic residue modulo p. Otherwise, when the equation a = N (mod p) has no solutions, but is called a quadratic nonresidue mod p.
The above definition of a quadratic residue can also be formulated as follows. If g is a generator element of the multiplicative group of the field GF (p), then a is called a quadratic residue modulo p if a = g * (mod p) for some natural k. If for a ∈ GF (p) for some natural k, a - g 2k + i (mod p), then a is called a quadratic nonresidue mod p.
Indeed, in this case it is impossible to find an x ∈ GF (p) such that a = x 2 (mod p), because if such x existed, then it would immediately follow the equality a = g 2k (mod p) for some k. Thus, there are altogether (p - 1) / 2 quadratic residues and non-residues.
The Legendre symbol in the case of an integer a and a prime p > 2 is determined by the equality:
Oh, if p | a
• 1 if a is a quadratic residue modulo p -1, if a is a quadratic nonresidue mod p.
It is clear that the meaning of the Legendre symbol is the same for two integers comparable to each other modulo p.
Let us prove the following result: if m is a prime number, then for all a the equality holds:
(—1 = a (, n “ 1) / 2 (mod zn). (A7)
m)
If t | a, then equality (A7) is obvious. If a is a quadratic residue modulo m, then the left side of equality (A7) is equal to 1 and, in addition, a can be represented as a - g 2k (mod m) for some natural k. Taking this into account, the right side of equality (A7 ) takes the form g k (m-1) (mod m) and, by Fermat's little theorem, g fc (m-1) = 1 (mod m). Thus, (A7) is proved.
If a is a quadratic nonresidue modulo m, then the left side of (A7) is equal to -1 and, in addition, a can be represented as a = g 2k +} (mod m) for some natural k. Taking this into account, the right side of (A7 ) takes the form g ^^ - D + t " 1 - 1 ^ 2 and in the FORM of Fermat's little theorem g« m - 1 ) + < m - 1 ^ 2 = g (ra - 1) / 2 (mod m).
Fermat's little theorem implies the equality:
^ op-n / r + _ 1} = 0 (mod m y
Since the second factor of the last equality cannot be compared with zero modulo m, since m - 1 is the order of the generating element g, we obtain from this that
g (m ' 1) / 2 = ( mod
Thus, equality (A7) is proved in this case as well.
It follows from the proved statement that
In addition, the following properties of the Legendre symbol can be proved:
- for any a, b and prime p > 2, if a = b, then | - | = | - 1;
- P) P)
- property of multiplicativity: for any a, b and prime p> 2
- (ab (aV
{P) [Pj [P)
• for any primes p> 2 and q> 2, the equality - =
/ (PD (qI)
= - • (-1) 4 , which expresses the reciprocity law for square
<1)
technical deductions.
The Jacobi symbol is a generalization of the Legendre symbol for the case of an arbitrary odd number. Consider an integer a and an odd m > 2. Let m = pj 1 • ... • p k k be the factorization of m into prime factors. Then the Jacobi symbol is defined as the product of the corresponding powers of the Legendre symbols:
a
Pi
a
P to
Let us prove the following theorem: if m is an odd composite number, then at most half of the integers a, where (a, m) = 1 and 1 <a <m, satisfy condition (A7), in which the transformation on the left-hand side of the comparison is now understood as Jacobi symbol.
First, we construct a such that (A7) does not hold for a = a. Depending on the representation m = p ['• ...? p k k consider two cases.
Case 1. Suppose that among the numbers q, ..., i k there is a number that is strictly greater than 1. Without loss of generality, we assume q > 2. Then we put a = 1 + m / p { .
„(Os'},„ „
Let us prove that - = 1. Really,
m I
(A8)
Because for everyone; = 1, ..., k , by virtue of the definition of a, the comparison a = 1 (mod p ; ) holds , then it follows from (A7) that each factor in the right
I OS]
part (A8) is equal to 1, whence it follows - = 1.
On the other side,
a (ml) / 2 = (1 + m / pi) (mD / 2 =
(t-1) t (t t ~ 1 Y 2 (t-1) t
= 1 + - + ... + - = 1 + - (mod t).
- 2 Pl [ P1 J 2 Р1
- (t-1) <™ -1) ™
ennogo element and wrong.
Case 2. The equalities = ... = i k = 1 hold, that is, m = P1 • ... • Pk . Let s be an arbitrary quadratic nonresidue modulo Р1 . Let us construct an element a so that it simultaneously satisfies two comparisons: a = s (mod P1 ) and a = 1 (mod m / P1 ).
Since the moduli of the above congruences are coprime numbers, in accordance with the Chinese remainder theorem, there is a unique element a up to comparison modulo m that simultaneously satisfies these congruences.
From the comparison a = 1 (mod m / P] ) it follows that a = 1 (mod Pj ) for all; - 2, ..., k. It is easy to see that
_ ( aa
- (OS |
- - I = 1
f a ^ for all j - 2, ..., k. Further, by virtue of a = 5 (mod P1 ), we have - = -1.
(а 1 v J
So - = -1.
(m)
If equality (A7) was valid, then from the obtained result it would follow that a (m “ 1) / 2 = -1 (mod m), ie there would be an integer C such that a ( '"' 1) / 2 = cC P -1.
j = i
Since a = 1 (mod m / P1 ) holds, the relation a (m-1) / 2 = 1 to
(mod m / P1 ), that is, there exists an A such that a (m-1) / 2 = A] ^ [ Pj + 1. Hence, we obtain k > 2
it is assumed that P [ P / (C P] - A) = 2, which is not true for any integer values> 2
A and C. Consequently, the assumption a ( '"“ 1) / 2 = -1 (mod m) is incorrect.
Thus, for any number of composite T was constructed as such that equation (A7) with a = not performed.
Consider now all integers 1 <ω, < m, (ω ,, m) - 1, 1 < i <t, satisfying (A7). Then, obviously, all numbers of the form
u = ω, a (mod m), 1 < i <t
are different and satisfy the conditions 1 <u, < m, (u if m) = 1.
If some satisfies (A7), then this means that the comparison is performed:
(mod t).
Since ω, satisfy (A7), it follows from this:
(t-1) / 2 =
OS
T
(mod m),
which contradicts the fact that a does not satisfy (A7). Thus, the statement of the theorem is proved.
The assertion of the theorem underlies the Solovey – Strassen simplicity test used in the RSA algorithm in the procedure for finding large primes.
For the Jacobi symbol, the results are similar to those formulated earlier for the Legendre symbol:
• for any odd m > 2 the equality | | = 1,
/ _- | (t-1) W)
- - = (- 1р ";
- (t )
• for any a, o and odd m > 2, if a = b (mod m), then - 1 = 1 -;
m) t)
- property of multiplicativity: for any a, b and odd m > 2
- (ab (a (by (a 2 b (b
t) mjmj t ) t )
- for any odd and coprime m> 2 and n > 2,
- ( t ( n Op-Np-P
n) t)
The latter property is called the law of reciprocity. It allows one to significantly simplify the procedure for calculating the Jacobi symbol and is widely used in the Solovey – Strassen method for checking a number for simplicity (see Appendix B).
Appendix B
