A.1
16. APPENDIX
ALGEBRA and NUMBER THEORY INTRODUCTION
In this appendix several simple and basic concepts
and methods of algebra and number theory are summarized.
Basic algebraic structures, such as groups, rings and
fields play key role in theory of error-correcting codes
and in cryptography.
The number theory concepts, methods and results
introduced in the following play an important role
in modern considerations concerning cryptography,
cryptographic protocols and randomness.
The key concept is that of primality. The key methods
are based on randomized algorithms.
A.1.01
GROUPS
A group G is a set of elements and an operation, call it *, with the
following properties:
• G is closed under *; that is if a, b ∈ G, so is a ∗ b.
• The operation * is associative (a∗(b∗c) = (a∗b)∗c, for any a, b, c ∈ G.
• G has an identity element e such that e ∗ a = a ∗ e = a for any a ∈ G.
• Every element a ∈ G has an inverse a−1
∈ G, so that a ∗ a−1
=
a−1
∗ a = e.
A group G is called Abelian group if the operation ∗ is commutative
(a ∗ b = b ∗ a for any a, b ∈ G).
Example Which of the following sets is an (Abelian) group:
• The set of real numbers with ∗ being: (a) addition; (b) multiplication.
• The set of matrices of degree n and an operations (a) addition; (b)
multiplication.
• What happens if we consider only matrices with determinants not equal
zero?
A.1.02
RINGS and FIELDS
A ring R is a set with two operations + (addition) and · (multiplication)
, with the following properties:
• R is closed under + and ·.
• R is an Abelian group under + (with the unity element for addition
called zero).
• The associative law for multiplication holds.
• R has an identity element 1 for multiplication
• The distributive law holds (a · (b + c) = a · b + a · c for all a, b, c ∈ R.
A ring is called commutative ring if multiplication is commutative
A field F is a set with two operations + (addition) and · (multiplication)
, with the following properties:
• F is a commutative ring.
• Non-zero elements of F form an Abelian group with respect to multiplication.
A non-zero element g is a primitive element of a field F if all non-zero
elements of F are powers of g.
A.1.03
FINITE FIELDS
Finite field are very well understood.
Theorem If p is a prime, then the integers modp, GF(p), constitute a
field. Every finite field F contains a subfield that is GF(p), up to relaabeling,
for some prime p and p · α = 0 for every α ∈ F.
If a field F contains the prime field GF(p), then p is called the characteristic
of F.
Theorem (1) Every finite field F has pm
elements for some prime p and
some m.
(2) For any prime p and any integer m there is a unique (up to isomorphism)
field of pm
elements GF(pm
).
(3) If f(x) is an irreducible polynomial of degree m in Fp[x], then the set
of polynomials in Fp[x] with additions and multiplications modulo f(x) is a
field with pm
elements.
A.1.04
FINITE FIELDS GF(pn)
There are two important ways GF(4), the Galois field of four elements, is
realized.
1. It is easy to verify that such a field is the set
GF(4) = {0, 1, ω, ω2
}
with operations + and · satisfying laws
• 0 + x = x for all x;
• x + x = 0 for all x;
• 1 · x = x for all x;
• ω + 1 = ω2
2. Let Z2[x] be the set of polynomials whose coefficients are integers mod
2. GF(4) is also Z2[x] (mod x2
+ x + 1) therefore the set of polynomials
0, 1, x, x + 1
where addition and multiplication are (mod x2
+ x + 1).
3. Let p be a prime and Zp[x] be the set of polynomials with coefficients
mod p. If p(x) is a irreducible polynomial modp of degree n, then Zp[x]
(mod p(x)) is a GF(pn
) with pn
elements.
A.1.1
Ceiling and floor functions
Flour ⌊x⌋ – the largest integer ≤ x
Ceiling ⌈x⌉ – the smallest integer ≥ x
Example ⌊3.14⌋ = 3 = ⌊3.75⌋ ⌊−3.14⌋ = −4 = ⌊−3.75⌋
⌈3.14⌉ = 4 = ⌈3.75⌉ ⌈−3.14⌉ = −3 = ⌈−3.75⌉
Exercise ⌈x⌉ − ⌊x⌋ =?
Modulo operations
The remainder if n is divided by m is defined by
n mod m =



n − m n
m m = 0
0 m = 0
Example 7 mod 5 = 2 7 mod −5 = 2
−7 mod 5 = 3 − 7 mod −5 = 3
Properties • (a + b) mod n = ((a mod n) + (b mod n)) mod n
• (a · b) mod n = ((a mod n) · (b mod n)) mod n
• ab
mod n = (a mod n)b
) mod n.
Exercise 3123456789
mod 26 =?
A.2
EUCLID’S ALGORITHM
to compute gcd(m, n), 0 ≤ m < n
gcd(0, n) = n (9)
gcd(m, n) = gcd(n mod m, m) for m > 0 (10)
Theorem T(n) = O(log n) for the number of steps of Euclid’s algoritm.
Proof Aftrer the first step arguments are (n1, m), where
n1 = n mod m.
After the second step arguments are (m1, n1), where
m1 = m mod n1.
Since a mod b < a
2 if 0 < b < a, we have:
n1 ≤
n
2
, m1 ≤
m
2
.
This analysis was made more precisse by E. Lucas (1884) and Lam´e (1884),
in perhaps the first deeper analysis of algorithms.
Theorem (1) If n > m ≥ 0, and an application of Euclid’s algorithm to
arguments m, n results in k recursive steps, then n ≥ Fk+2, m ≥ Fk+1.
(2) If n > m ≥ 0, m < Fk+1, then the application of Euclid’s algorithm to
arguments n, m requires less than k steps.
Corollary T(n) = Θ(log n) for the number of steps of Euclid’s algoritm.
Properties Is there an asymptotycally faster algorithm to compute
gcd(m, n)?
A.3
Modified Euclid’s algorithm
gcd(0, n) = n (11)
gcd(m, n) = gcd(m, n − m), 0 < m < n. (12)
Lemma T(n) = Θ(n) for the number of steps of the modified Euclid
algoritm.
Corollary Modified Euclid’s algorithm is of exponential complexity.
Extended Euclid’s algorithm
Theorem For all 0 < m < n there exist integers x and y such that
gcd(m, n) = xm + yn.
Moreover, x and y can be computed in polynomial time.
Proof If m = 0, then x = 0, y = 1.
If m > 0, take r = n mod m and compute recursively x′
, y′
such that
x′
m + y′
r = gcd(r, m).
Since r = n − n
m m we have:
gcd(m, n) = x′
m + y′
n −
n
m
m = x′
+ y′ n
m
m + y′
n.
An extention of Euclid’s algorithm, which computes x and y together with
gcd(m, n) is sometimes referred to as extended Euclid’s algorithm.
A.4
Exponentiation
Exponentiation (modular) plays the key role in many cryptosystems. If
n =
k−1
i=0
bi2i
, bi ∈ {0, 1}
then
e = an
= a
k−1
i=0 bi2i
=
k−1
i=0
abi2i
=
k−1
i=0
(a2i
)bi
Algorithm for exponentiation
begin e ← 1; p ← a;
for i ← 0 to k − 1
do if bi = 1 then e ← e · p;
p ← p · p
od
end
Modular exponentiation: an
mod m = ((a mod m)n
) mod m
Modular multiplication: ab mod n = ((a mod n)(b mod n) mod n)
Exercise 31000
mod 19 = 16
310000
mod 13 = 3
3340
mod 11 = 1
3100
mod 79 = 51
A.5
PRIMES
A positive integer p > 1 is called prime if it has just two divisors: 1 and p.
Fundamental theorem of arithmetic: Each integer n has a unique decomposition
n =
k
i=1
pei
i
where pi < pi+1 are primes and ei are integers.
How many primes Π(n) are there among the first n integers?
Estimations Π(n) ˙= n
ln n (due to Gauss)
Prime number theorem.
Π(n) =
n
ln n
+
n
(ln n)2
+
2!n
(ln n)3
+
3!n
(ln n)4
+ Θ


n
(ln n)6


The largest known prime:1994: 2859433
− 1; (258716 digits)
1996: 21257787
− 1; (378632 digits)
1997: 22976221
− 1;
The largest computed value of Π(x): Π(1018
) = 24739954287860
How difficult is to determine whether a given integer is a prime?
• Only in 2002 it has been shown that there is a (O(m12
)) deterministic algorithm
to recognize whether an m bit integer is a prime.
• There are (very) simple randomized algorithm to decide fast and with large probability
correctly whether a given integer is a prime.
A.6
Chinese Remainder Theorem
Theorem Let m1, . . . , mt be integers, gcd(mi, mj) = 1 if i = j and
a1, . . . , at be integers, 0 < ai < mi, 1 ≤ i ≤ t.
Then the system of congruences
x ≡ ai (mod mi), 1 ≤ i ≤ t
has the solution
x =
t
i=1
aiMiNi (⋆)
where
M =
t
i=1
mi, Mi =
M
Mi
, Ni = M−1
i mod mi
and the solution (⋆) is unique up to the congruence modulo M.
Corollary Each integer 0 < x < M is uniquelly represented by t-tuple:
x mod m1, . . . , x mod mt.
Example If m1 = 2, m2 = 3, m3 = 5, then (1, 0, 2) represents 27.
Advantage: With such a modular representation addition, substraction
and multiplication can be done componentwise in parallel time.
A.7
Euler totient function
Φ(n) = |Z⋆
n| = |{m|1 ≤ m ≤ n, gcd(m, n) = 1}|
Basic properties: • Φ(1) = 1
• Φ(p) = p − 1, if p is a prime;
• Φ(pk
) = pk−1
(p − 1), if p is prime, k > 0;
• Φ(nm) = Φ(n)Φ(m), if gcd(m, n) = 1;
Theorem Computation of Φ(n) and factorization of n are computationally
polynomially related problems.
Proof (1) If factorization of n = k
i=1 pei
i is known, then
Φ(n) =
k
i=1
pei−1
i (pi − 1) = n
k
i=1
pi − 1
pi
is easy to compute.
(2) The opposite assertion will be shown only for the case n = p1p2. In such
a case
Φ(n) = (p1 − 1)(p2 − 1)
and
p1 + p2 = p1p2 + 1 − Φ(n) = n + 1 − Φ(n)
Given p1 + p2 and p1p2 it is easy to determine p1 and p2.
In addition, it holds
Φ(n)
n
= Ω


1
log n


A.8
Basic theorems
Theorem (Lagrange) If (H, ◦) is a subgroup of a group (G, ◦), then |H|
divides |G|).
Theorem (Euler’s Totient Theorem)
nΦ(m)
≡ 1 (mod m)
if n < m, gcd(m, n) = 1
Corollary n−1
≡ nΦ(m)−1
(mod m) if n < m, gcd(m, n) = 1
Theorem (Fermat’s Little Theorem)
ap
≡ a (mod p)
if p is prime.
Proof Theorem is true for a = 1. Assume it is true for some a.
By induction
(a + 1)p
≡ ap
+ 1 ≡ a + 1 mod p.
Example If x ≡ y mod p − 1, where p is a prime, then x − y = k(p − 1)
and therefore for any a < p, ax−y
= ak(p−1)
≡ 1 mod p
A.9
Discrete square roots and logarithms
Three problems are related with the equation
y = xa
(mod n).
Exponentiation problem Given x, a, n, compute y
Easy: it can be done in polynomial time
Discrete logarithm problem Given x, y, n, compute a
Very hard. It is believed that the discrete logarithm problem is NP-hard even
in the average case. (A formal proof of it would imply that exponentiation
is a one-way function.)
Root finding problem Given y, a, n, compute x
Hard.
Square root finding problem Given y, a = 2, n, compute x
This problem is in general as hard as factorization.
Square root finding can be done by a randomized polynomial time algorithm
if
• n is a prime;
or
• the prime decomposition of n is know.
A.10
Groups Zn and Z⋆
n
Two integers a, b are congruent modulo n if
a mod n = b mod n.
Notation: a ≡ b(mod n)
Let +n, ×n denote addition and multiplication modulo n
a +n b = (a + b) mod n
a ×n b = (ab) mod n
Zn = {0, 1, . . . , n − 1} is a group under the operation +n.
Z⋆
n = {x|1 ≤ x ≤ n, gcd(x, n) = 1} is a group under the operation ×n
Z⋆
n is a field under the operations +n, ×n if n is a prime
Theorem For any n, the multiplicative inverse of any z ∈ Z⋆
n can be
computed in polynomial time.
Proof Computation can be done by the extended Euclid algorithm.
Theorem In the group (Z⋆
n, ×n) the exponentiation can be performed in
polynomial time.
A.11
Properties of the group Z⋆
n
Definition (1) For any group (G, ◦) and any x ∈ G
ord(x) = min{k > 0|xk
= 1}
(2) The group (G, ◦) is called cyclic if it contains an element g, called generator, such
that ord(g) = |G|.
Theorem If the multiplicative group (Z
⋆
n, ×n) is cyclic, then it is isomorphic to the
additive group (ZΦ(n), +Φ(n)). (However, no effective way is known, given n, to create
such an isomorphism!)
Theorem The mutliplicative group (Z
⋆
n, ×n) is cyclic iff n is either 1, 2, 4, pk
or 2pk
for some k ∈ N
+
and an odd prime p > 2.
Theorem Let p be a prime. Given the prime factorization of p − 1 a generator for
group (Z⋆
p, ×p) can be found in polynomial time by a randomized algorithm.
Proof (1) Pick randomly x ∈ Z
⋆
p and checks whether its order is p − 1. If yes, it is a
generator. The probability to find a generator in a single trial is
Φ(p − 1)
p − 1
= Ω
1
p
.
How to check whether the order of x is p − 1? Let p1, . . . , pt be different prime factors
of p − 1. If ord(x) < p − 1, then ord(x) has to be proper divisor of p − 1, that is for
some pi,
ord(x)
p − 1
pi
To verify that ord(x) = p − 1, it suffices to check for each pi, that
x
p−1
pi ≡ 1 (mod p).
A.16
Quadratic residues and nonresidues
An integer x ∈ Z⋆
m is called a quadratic residue modulo m if
x ≡ y2
(mod m)
for some y ∈ Z⋆
m, otherwise x is a quadratic nonresidue.
Notation: QRm – the set of all quadratic residues modulo m. QRm is
therefore subgroup of squares in Zm.
QNRm – the set of all quadratic nonresidues modulo m.
How to decide whether an x is a quadratic residue?
Theorem If p > 2 is a prime and g ∈ Z⋆
p a generator, then gk
is a
quadratic residue iff k is even.
Proof If k is even, then g
k
2 is the square root of gk
.
Let k = 2l + 1 and x ∈ Z⋆
p be such that x2
= g2k+1
(mod p).
If x = gm
, then g2m
≡ g2k+1
(mod p) and therefore in the additive group
modulo Φ(p) it holds
2m = 2l + 1(mod Φ(p))
Since Φ(p) = p − 1, this is impossible.
Theorem If p is a prime, then a ∈ Z⋆
p is a quadratic residue iff
a
p−1
2 ≡ 1(mod p).
Proof (1) If a ∈ QRp, a = q2k
(mod p) for some generator q,
a
p−1
2 ≡p qk(p−1)
≡p (qp−1
)k
≡p 1k
≡ 1.
A.16
(2) If a ∈ QNRp, a = q2k+1
(mod p) for some generator q, then
a
p−1
2 ≡p qk(p−1)
q
p−1
2 ≡p q
p−1
2 ≡p −1.
A.16
Euler’s criterion
Theorem Let p > 2 be a prime. Then x is a quadratic residue modulo
p if and only if
x(p−1)/2
≡ 1 (mod p).
Proof First suppose that x ≡ y2
(mod p). From Fermat theorem it
follows that xp−1
≡ 1 (mod p) if x ≡ 0 (mod p). Therefore
x(p−1)/2
≡ (y2
)(p−1)/2
(mod p) (13)
≡ yp−1
(mod p) (14)
≡ 1 (15)
Secondly, let x(p−1)/2
≡ 1 (mod p). Then x ≡ bi
(mod p) for some
primitive element modulo p and some i. Therefore
x(p−1)/2
≡ (bi
)(p−1)/2
(mod p) (16)
≡ bi(p−1)/2
(mod p) (17)
Since b has order p − 1, it must be the case that p − 1 divides i(p − 1)/2
and therefore i has to be even. Therefore the square roots of x are ±bi/2
.
A.12
Examples
n = 8 Z⋆
8 = {1, 3, 5, 7}
12
≡ 1 mod 8, 22
≡ 4 mod 8, 32
≡ 1 mod 8, 42
≡ 0 mod 8,
52
≡ 1 mod 8, 62
≡ 4 mod 8, 72
≡ 1 mod 8
QR8 = {1}
n = 9 Z⋆
9 = {1, 2, 4, 5, 7, 8}
12
≡ 1 mod 9, 22
≡ 4 mod 9, 32
≡ 0 mod 9, 42
≡ 7 mod 9,
52
≡ 7 mod 9, 62
≡ 0 mod 9, 72
≡ 4 mod 9, 82
≡ 1 mod 9
QR9 = {1, 4, 7}
n = 15 Z⋆
15 = {1, 2, 4, 7, 8, 11, 13, 14}
12
≡ 1 mod 15, 22
≡ 4 mod 15, 32
≡ 9 mod 15, 42
≡ 1 mod 15,
52
≡ 10 mod 15, 62
≡ 6 mod 15, 72
≡ 4 mod 15, 82
≡ 4 mod 15,
92
≡ 6 mod 15, 102
≡ 10 mod 15, 112
≡ 1 mod 15, 122
≡ 9 mod 15,
132
≡ 4 mod 15, 142
≡ 1 mod 15
QR15 = {1, 4}
A.13
FINDING of QUADRATIC (NON)RESIDUES
Let p be a prime.
How to find (1) a quadratic residue in QRp?
(2) How to find a quadratic nonresidue in QNRp
?
(1) Very easy: choose a, compute a2
(2) Very easy using a randomized algorithm because exactly half of elements
are quadratic nonresidues.
If the generalized Riemann Hypothesis holds, then Z⋆
p has to contain a
quadratic nonresidue among its O(log2
p) smallest elements.
A.14
Legendre and Legendre-Jacobi symbols
The following notation is useful to deal with quadratic residues and
nonresidues:
(x|m)



1 if x ∈ QRm and m is prime
−1 if x ∈ QNRm and m is prime
n
i=1(x|pi) if m = n
i=1 pi, pi are primes, gcd(x, m) = 1
(x|m) is called the Legendre symbol if m is prime and the Legendre-Jacobi
symbol otherwise.
Rules to compute (x|m)
1. Euler’s criterion: x|p ≡ x
p−1
2 (mod p) if p > 2 is prime, x ∈ Z⋆
p
2. If x ≡ y(mod m), then (x|m) = (y|m).
3. (x|m) · (y|m) = (xy|m).
4. (−1|m) = (−1)
m−1
2 , if m is odd.
5. (2|m) = (−1)
m2−1
8 , if m is odd
6. Law of quadratic reciprocity: If gcd(m, n) = 1, m, n are odd, then
(n|m)(m|n) = (−1)
(m−1)(n−1)
4
Example
(28|97) = (2|97)(2|97)(7|97) = (7|97)
= (97|7)(−1)
(97−1)(7−1)
4 = (6|7)
= (2|7)(3|7) = (−1)6
(3|7) = (7|3)(−1)3
= −(1|3) = −1
A.15
Solovay-Strassen’s prime recognition algorithm
It follows from the Lagrange theorem that if the following fast Monte
Carlo algorithm — based on the fact that computation of Legendre-Jacobi
symbols can be done fast — reports that a given number n is composite,
then this is 100%, true and if it reports that it is a prime, then the error is
at most 1
2
.
begin choose randomly an integer a ∈ {1, . . . , n}
if gcd(a, n) = 1 then return “composite”
else if (a|n) ≡ a
n−1
2 (mod n)
then return “composite”;
return “prime”
end
Indeed, if n is composite, then all integers a ∈ Z⋆
n such that
(a|n) ≡ a
n−1
2 (mod n)
form a proper subgroup of the group Z⋆
n. This implies that most of the
elements a ∈ Z⋆
n are such that
(a|n) ≡ a
n−1
2 (mod n)
and therefore they can “witness” compositness of n, if n is composite.
A.16
How many square roots there exist?
Theorem
(1) If p > 2 is a prime, k ≥ 1, then any quadratic residue modulo pk
has
exactly two distinct square roots x, −x = pk
− x
(2) If p = 2, k ≥ 1, then any quadratic residue modulo 2k
has
• 1 square root if k = 1;
• 2 square root if k = 2;
• 4 square root if k > 2.
Theorem If an odd number n has exactly t distinct factors, then any
quadratic residue a modulo n has exactly 2t
distinct square roots.
We show the theorem only for the case n = p · q where p > 2, q > 2 are
primes.
Let a ∈ QRn, a ≡ a2
1(mod n).
By the Chinese Remainder Theorem there are integers u, v such that
u ≡ a1 mod p u ≡ −a1 mod q
v ≡ a1 mod q v ≡ −a1 mod p
Since p, q are odd, u, v have to be distinct. Moreover,
u2
≡ v2
≡ a2
1 mod pq
and therefore a1, −a1, u, v are 4 different square roots.
A.17
COMPUTATION of DISCRETE SQUARE ROOTS
Theorem (Adleman-Manders-Miller)
There exists a randomized polynomial time algorithm to compute the square
root of modulo p, where a ∈ QRp, and p is a prime.
Theorem There is a polynomial algorithm which computes, given
x, u, v, p, q such that
x ≡ u2
mod p, x ≡ v2
mod q, p, q-primes
a w such that x ≡ w2
mod pq.
Proof Let x, u, v, p, q satisfy the above conditions.
Using Euclid’s algorithm we can compute a, b such that
ap + bq = 1
If we denote
c = bq = 1 − ap, d = ap = 1 − bq,
then
c ≡ 0 mod q, d ≡ 0 mod p, c ≡ 1 mod p, d ≡ 1 mod q.
We show now that for w = cu + dv we have
x ≡ w2
mod p, x ≡ w2
mod q
and therefore
x ∈ QRp, x ∈ QRq ⇒ x ∈ QRpq.
Case 1. w2
= (cu + dv)2
= c2
u2
+ 2cduv + d2
v2
≡ u2
≡ x(mod p)
Case 2. w2
= (cu + dv)2
= c2
u2
+ 2cduv + d2
v2
≡ v2
≡ x(mod q)
A.18
Blum’s integers
Blum’s integers have the form
n = p · q, p, q are primes, p ≡ q ≡ 3(mod 4).
Why are Blum integers of importance?
Theorem If n is a Blum integer, then the mapping
x → x2
mod n
is a permutation on QRn.
(In other words, in such a case each quadratic residue has a unique square
root that is also a quadratic residue and it is called its principal square root.)
A.19
RABIN’S ALGORITHM
Theorem (Rabin) The following statements are equivalent:
(1) There is a polynomial time randomized algorithm to factor Blum integers.
(2) There is a polynomial time randomized algorithm to compute the principal square
root for x ∈ QRn, if n is a Blum integer.
Proof (1) Assume, that a polynomial time randomized algorithm A to compute the
principal square root modulo Blum integers is given.
A Blum integer n can be factorized as follows:
1. Choose randomly a y such that (y|n) = −1.
2. Compute x ≡ y2
mod n.
3. Find, using A, a z ∈ QRn such that x = z2
mod n.
We show that gcd(y + z, n) is a prime factor of n = pq.
Clearly pq divides (y − z)(y + z). Since
(−z|n) = (−1|n)(z|n) = (−1)
p−1
2 (−1)
q−1
2 (z|n) =??
we have y ≡ −z mod n and therefore gcd (y + z, n) has to be one of the prime factor
of n.
(2) Assume we can effeciently factor n = pq.
We show how to compute effeciently principal square roots modulo n.
Let x ∈ QRn. Using Adleman-Manders-Miller’s algorithm compute
u ∈ QRp, v ∈ QRq such that x = u2
mod p, y = v2
mod q.
Using extended Euclid’s algorithm compute a, b such that ap + bq = 1.
Compute c = bq, d = ap.
We show that w = cu + dv ∈ QRn and it is a square root of x. Since
c ≡ 1 mod p, d ≡ 1 modq
and
w2
≡ u2
≡ x mod p, w2
≡ v2
≡ x mod q
we have
w2
≡ x mod n.
To show w ∈ QRn : (w|pq) = (w|p)(w|q) = (u|p)(v|q) = 1.
A.20
INVERTING INTEGER MATRICES modulo n
The basic idea to compute M−1
(mod n) is simple:
Use the usual method to invert M in terms of rational numbers, and then
replace each a/b by ab−1
, where bb−1
≡ 1 (mod n). Example, To compute
M =







1 1 1
1 2 3
1 4 9







(mod 11).
Standard inverse of M in rational numbers yields
1
2







6 −5 1
−6 8 −2
2 −3 1







Since 2−1
≡ 6 (mod 11), the resulting matrix has the form
M−1
=







3 3 6
8 4 10
1 4 6







(mod 11).
A.21
COMPUTATION of SQUARE ROOTS mod PRIMES
Theorem Let p ≡ 3 (mod 4) be a prime and y an integer. Let x ≡
y(p+1)/4
(mod p).
1. If y has a square root modp, then the square roots of y modp are ±x.
2. If y has no square root mod p, then −y has a square root mod p, and
the square roots of −y are ±x.
In case of Blum integers m = pq, where p ≡ 3 (mod 4) and q ≡ 3
(mod 4), then to solve the equation x2
≡ a( mod pq), one needs to compute
squares of a modulo p and q and then to use the Chinese remainder theorem
to solve equation x2
= a (mod pq).
Example To solve equation x2
≡ 71 (mod 77), one needs to solve
equation x2
≡ 71 ≡ 1 (mod 7) to get x ≡ ±1(mod 7) and x2
≡ 71 ≡
5 (mod 11) to get x ≡ ±4 (mod 11). Using the Chinese Remainder
Theorem then we get
x ≡ ±15, ±29 (mod 77).