to be the output of A on input n and a value ± chosen at random from

ker(Jn ) \ (Z— )2 , and Yn is de¬ned to be the output of A on input n and a

n

value ± chosen at random from (Z— )2 . In both cases, the value of the random

n

variable is determined by the random choice of ±, as well as the random

298 Computational problems related to quadratic residues

choices made by the algorithm. De¬ne (n) := |P[Xn = 1] ’ P[Yn = 1]|.

Show how to use A to design a probabilistic, expected polynomial time

algorithm A that takes as input n as above and ± ∈ ker(Jn ), and outputs

either “square” or “non-square,” with the following property:

if (n) ≥ 0.001, then for all ± ∈ ker(Jn ), the probability that

A correctly identi¬es whether ± ∈ (Z— )2 is at least 0.999.

n

Hint: use the Cherno¬ bound.

Exercise 13.13. Assume the same notation as in the previous exercise.

De¬ne the random variable Xn to be the output of A on input n and a value

± chosen at random from ker(Jn ). Show that |P[Xn = 1] ’ P[Yn = 1]| =

(n)/2. Thus, the problem of distinguishing ker(Jn ) from (Z— )2 is essentially

n

— )2 from (Z— )2 .

equivalent to the problem of distinguishing ker(Jn ) \ (Zn n

13.5 Notes

Exercise 13.2 is based on Solovay and Strassen [94].

The probabilistic algorithm in §13.3.1 for computing square roots modulo

p can be made deterministic under a generalization of the Riemann hypothe-

sis. Indeed, as discussed in §10.7, under such a hypothesis, Bach™s result [10]

implies that the least positive integer that is not a quadratic residue modulo

p is at most 2 log p (this follows by applying Bach™s result with the sub-

group (Z— )2 of Z— ). Thus, we may ¬nd the required element γ ∈ Z— \ (Z— )2

p p p n

in deterministic polynomial time, just by brute-force search. The best un-

conditional bound on the smallest positive integer that is not a quadratic

residue modulo p is due to Burgess [22], who gives a bound of p±+o(1) , where

√

± := 1/(4 e) ≈ 0.15163.

Goldwasser and Micali [39] introduced the quadratic residuosity assump-

tion to cryptography (as discussed in §13.4). This assumption has subse-

quently been used as the basis for numerous cryptographic schemes.

14

Modules and vector spaces

In this chapter, we introduce the basic de¬nitions and results concerning

modules over a ring R and vector spaces over a ¬eld F . The reader may

have seen some of these notions before, but perhaps only in the context of

vector spaces over a speci¬c ¬eld, such as the real or complex numbers, and

not in the context of, say, ¬nite ¬elds like Zp .

14.1 De¬nitions, basic properties, and examples

Throughout this section, R denotes a ring.

De¬nition 14.1. An R-module is an abelian group M , which we shall write

using additive notation, together with a scalar multiplication operation

that maps a ∈ R and ± ∈ M to an element a± ∈ M , such that the following

properties are satis¬ed for all a, b ∈ R and ±, β ∈ M :

(i) a(b±) = (ab)±,

(ii) (a + b)± = a± + b±,

(iii) a(± + β) = a± + aβ,

(iv) 1R ± = ±.

One may also call an R-module M a module over R. Elements of R are

often referred to as scalars, and elements of M may be called vectors.

Note that for an R-module M , for ¬xed a ∈ R, the map that sends ± ∈ M

to a± ∈ M is a group homomorphism with respect to the additive group

operation of M ; likewise, for ¬xed ± ∈ M , the map that sends a ∈ R to

a± ∈ M is a group homomorphism from the additive group of R into the

additive group of M .

The following theorem summarizes a few basic facts which follow directly

299

300 Modules and vector spaces

from the observations in the previous paragraph, and basic facts about group

homomorphisms (see Theorem 8.20):

Theorem 14.2. If M is a module over R, then for all a ∈ R, ± ∈ M , and

m ∈ Z, we have:

(i) 0R ± = 0M ,

(ii) a0M = 0M ,

(iii) (’a)± = ’(a±) = a(’±),

(iv) (ma)± = m(a±) = a(m±).

Proof. Exercise. 2

The de¬nition of a module includes the trivial module, consisting of just

the zero element 0M . If R is the trivial ring, then any R-module is trivial,

since for all ± ∈ M , we have ± = 1R ± = 0R ± = 0M .

Example 14.1. A simple but extremely important example of an R-module

is the set R—n of n-tuples of elements of R, where addition and scalar multi-

plication are de¬ned component-wise ” that is, for ± = (a1 , . . . , an ) ∈ R—n ,

β = (b1 , . . . , an ) ∈ R—n , and a ∈ R, we have

± + β = (a1 + b1 , . . . , an + bn ) and a± = (aa1 , . . . , aan ). 2

Example 14.2. The ring of polynomials R[X] over R forms an R-module

in the natural way, with addition and scalar multiplication de¬ned in terms

of the addition and multiplication operations of the polynomial ring. 2

Example 14.3. As in Example 9.34, let f be a monic polynomial over R

of degree ≥ 0, and consider the quotient ring E := R[X]/(f ). Then E is

a module over R, with addition de¬ned in terms of the addition operation

of R, and scalar multiplication de¬ned by a[g]f := [ag]f , for a ∈ R and

g ∈ R[X]. If f = 1, then E is trivial. 2

Example 14.4. If E is any ring containing R as a subring (i.e., E is an

extension ring of R), then E is a module over R, with addition and scalar

multiplication de¬ned in terms of the addition and multiplication operations

of E. 2

Example 14.5. If M1 , . . . , Mn are R-modules, then so is the direct product

M1 — · · · — Mn , where addition and scalar product are de¬ned component-

wise. 2

Example 14.6. Any abelian group G, written additively, can be viewed as

14.2 Submodules and quotient modules 301

a Z-module, with scalar multiplication de¬ned in terms of the usual integer

multiplication map (see parts (vi)“(viii) of Theorem 8.3). 2

Example 14.7. Let G be any group, written additively, whose exponent

divides n. Then we may de¬ne a scalar multiplication that maps [m]n ∈ Zn

and ± ∈ G to m±. That this map is unambiguously de¬ned follows from the

fact that G has exponent dividing n, so that if m ≡ m (mod n), we have

m± ’ m ± = (m ’ m )± = 0G , since n | (m ’ m ). It is easy to check that

this scalar multiplication operation indeed makes G into a Zn -module. 2

Example 14.8. Of course, viewing a group as a module does not depend on

whether or not we happen to use additive notation for the group operation.

If we specialize the previous example to the group G = Z— , where p is prime,

p

then we may view G as a Zp’1 -module. However, since the group operation

itself is written multiplicatively, the “scalar product” of [m]p’1 ∈ Zp’1 and

± ∈ Z— is the power ±m . 2

p

14.2 Submodules and quotient modules