D. Hints to Selected Exercises

The greatest thing in family life is to take a hint when a hint is intended and not to take a hint when a hint isn’t intended.

—Robert Frost

Teachers open the door, but you must enter by yourself.

—Chinese Proverb

Imagination grows by exercise, and contrary to common belief, is more powerful in the mature than in the young.

—W. Somerset Maugham

2.11 (a)	Apply Theorem 2.3 to the restriction to H of the canonical homomorphism G → G/K.
2.11 (b)	Apply Theorem 2.3 to the canonical homomorphism G/H → G/K, aH ↦ aK, .
2.14 (c)	Consider the canonical surjection G → G/H.
2.17 (a)	Let i ≠ j and . Then ord g divides both and and so is equal to 1, that is, g = e. Now let hi, and with . But then . Thus #(HiHj) = (#Hi)(#Hj). Generalize this argument to show that #(H1 · · · Hr) = n.
2.18	First consider the special case #G = pr for some and . For each , the order ordG g is of the form psg for some sg ≤ r. Let s be the maximum of the values sg, . Take any element with ordG h = ps. Then e, h, . . . , hps–1 are all the elements x that satisfy xps = e. But by the choice of s every element satisfies xps = e. Hence we must have s = r. This proves the assertion for the special case. For the general case, use this special case in conjunction with Exercise 2.17.
2.19 (b)	Show that , (h1, . . . , hr) ↦ h1 . . . hr, is a group isomorphism.
2.23	Use Zorn’s lemma.
2.24 (c)	Let be the intersection of all prime ideals of R. First show that . To prove the reverse inclusion take and consider the set S of all non-unit ideals of R such that for all . If f is a non-unit, the set S is non-empty and by Zorn’s lemma has a maximal element, say . Show that is a prime ideal of R.
2.25	For , the map R → R, b ↦ ab, is injective and hence surjective by Exercise 2.4.
2.30	Apply the isomorphism theorem to the canonical surjection , .
2.33	[(1)⇒(2)] Let be an ascending chain of ideals of R. Consider the ideal which is finitely generated by hypothesis. [(3)⇒(1)] Let be an ideal of R. Consider the set of all finitely generated ideals of R contained in .
2.36	Use the pigeon-hole principle: If there are n + 1 pigeons in n holes, then there exists at least one hole containing more than one pigeons.
2.37	Consider the integer satisfying 2t ≤ n < 2t+1.
2.39 (e)	12 ≡ (n – 1)2 (mod n).
2.39 (f)	Apply Wilson’s theorem.
2.40	Use Fermat’s little theorem.
2.41	Use Wilson’s theorem or Euler’s criterion.
2.45	Reduce to the case y2 ≡ α (mod p).
2.49 (a)	Consider the canonical group homomorphism and the fact that a surjective group homomorphism from a cyclic group G onto G′ implies that G′ is cyclic.
2.49 (b)	Let be a primitive element modulo p. The residue class of a in has order k(p – 1) for some . Show that the order of b := p + 1 modulo pe is pe–1. So the order of akb modulo pe is pe–1(p – 1) = φ(pe).
2.50	Use the Chinese remainder theorem in conjunction with Exercises 2.20 and 2.49.
2.53	Take . The interpolating polynomial is . Use Exercise 2.52 to establish the uniqueness.
2.56 (b)	is irreducible in if and only if f(X + 1) is irreducible in .
2.58	Use the fundamental theorem of algebra.
2.63	Consider the set of all linearly independent subsets of V that contain T. Show that every chain in has an upper bound in . By Zorn’s Lemma, there exists a maximal element . Show that S generates V.
2.64 (b)	Use Exercise 2.63.
2.68	Let p1, . . . , pn be n distinct primes. Take and ai := a/pi for i = 1, . . . , n.
2.72 (a)	If N is the -submodule of generated by ai/bi, i = 1, . . . , n, with gcd(ai, bi) = 1, then for any prime p that does not divide b1 · · · bn we have 1/p ∉ N.
2.72 (b)	Any two distinct elements of are linearly dependent over . Now use Exercise 2.69.
2.74 (b)	Let the conjugates of over F be α1 = α, α2, . . . , αn. Since is injective, it follows from (a) that makes a permutation of α1, . . . , αn. So is surjective.
2.75 (a)	Use Exercise 2.61.
2.76 (b)	The if part follows from Exercise 2.61. For proving the only if part, take . If the polynomial f(X) := Xp – a splits over F, we are done. So suppose that there exists an irreducible divisor of f(X) of degree ≥ 2. By the separability of F, there exist two distinct roots α, β of g(X). Let K := F (α, β). Show that the Frobenius map , , is an endomorphism of K. Also there exists a field isomorphism τ : F (α) → F (β) which fixes F element-wise and takes α ↦ β. But then . Since any field homomorphism is injective, α equals β, a contradiction. Thus no g(X) chosen as above can exist.
2.77 (a)	Let be an irreducible polynomial with g(α) = 0 for some . Let β be another root of g. We show that . By Lemma 2.5, there is an isomorphism μ : F(α) → F(β). Clearly, K is the splitting field of f over F(α). Let K′ be the splitting field of μ*(f) over F (β). By Proposition 2.33, K ≅ K′. If are the roots of f, then K′ ≅ F (β, γ1, . . . , γd) = K(β). But then K ≅ K(β).
2.78 (a)	Consider transcendental numbers.
2.78 (b)	Let . For , we have , implying that for a, with a ≤ b. Now assume for some . Choose a rational number b with . Then , a contradiction. Thus . Similarly .
2.80	Use the binomial theorem and induction on n.
2.82	Follow the proof of Theorem 2.37.
2.90	Example 2.18.
2.91 (b)	By the fundamental theorem of Galois theory, # . Now show that are distinct -automorphisms of .
2.92 (a)	Assume r > 1. We have the extensions , where is the splitting field of f over and hence over . Consider the minimal polynomial of a root of f over . Conversely, let f be reducible over . Choose an irreducible factor of f with deg h = s < d. Now h has one (and hence all) roots in and, therefore, d|sm.
2.93	Use Corollary 2.18.
2.98	In each case, the defining polynomial is quadratic in Y (and with coefficients in K[X]). If this polynomial admits a non-trivial factorization, one can reach a contradiction by considering the degrees of X in the coefficients of Y1 and Y0.
2.103	For simplicity, consider the case char K ≠ 2, 3. Show that the curves Y2 + Y = X3 and Y2 = X3 + X have j-invariants 0 and 1728 respectively. Finally, if , 1728, then the curve has j-invariant . One must also argue that these are actually elliptic curves, that is, have non-zero discriminants.
2.111	Use Theorem 2.51.
2.112 (a)	Pair a point with its opposite. This pairing fails for points of orders 1 and 2.
2.112 (c)	Consider the elliptic curve E : Y2 = X3 + 3 over . We have , whereas X3 + 3 is irreducible modulo 13.
2.113 (a)	Every element of has a unique square root.
2.115 (a)	Use Theorem 2.49 or Exercise 2.17.
2.115 (b)	Use Theorem 2.50.
2.115 (c)	The trace of Frobenius at q is 0 in this case. Now, use Theorem 2.50.
2.123	Factor N(G) in .
2.127	Let . For each i, write , . But then det , where , δij being the Kronecker delta.
2.128 (b)	Use Part (a) and Exercise 2.126(c).
2.128 (c)	Let . By Exercise 2.130, is integral over . Let be the ideal generated by in and let and be the ideals of generated respectively by and . Now, use Part (b).
2.133 (b)	In a PID, non-zero prime ideals are maximal.
2.137 (a)	Since and are maximal, we have , that is, a1 + a2 = 1 for some and . Now use the fact that (a1 + a2)e1 + e2 = 1.
2.137 (b)	Use CRT.
2.138 (a)	Since is invertible, for some fractional ideal .
2.140 (a)	For , let constitute a complete residue system of modulo . Then also form a complete residue system of modulo .
2.142 (d)	Take in Part (b).
2.143 (a)	Reduce modulo 4.
2.143 (c)	Let divide this gcd. Then divides 2y and . Take norms.
2.144 (b)	Look at the expansion of a – 1 in base p. More precisely, let a < pN for some . Then –a = (pN – a) – pN = [(pN – 1) – (a – 1)] – pN.
2.152 (c)	First show that .
2.153	Use unique factorization of rationals.
2.154	Show by induction on n that pn+1 divides apn+1 – apn in for all .
2.161	There exists an irreducible polynomial in of every degree .
3.7	The implication is obvious. For the reverse implication, use Proposition 2.5.
3.18 (b)	Consider the binary expansion of m.
3.19	if n is a pseudoprime to base a and not a pseudoprime to base b, then n is not a pseudoprime to base ab.
3.20 (a)	If p2|n for some , take with ordn(a) = p. If n is square-free, consider a prime divisor p of n and take with and a ≡ 1 (mod n/p).
3.20 (b)	if n is an Euler pseudoprime to base a and not an Euler pseudoprime to base b, then n is not an Euler pseudoprime to base ab.
3.21 (a)	Let be the prime factorization of n with r and each αi in . Then, . For odd pi, the group is cyclic of order and hence contains an element of order pi – 1.
3.21 (b)	ordn(–1) = 2.
3.21 (c)	Let vp(n) ≥ 2 for some odd prime p. Construct an element with ordn(a) = p.
3.28	Proceed by induction on i = 1, . . . , r. For 1 ≤ i ≤ r, define νi := n1 · · · ni and let be a solution of the congruences bi ≡ aj (mod nj) for j = 1, . . . , i. If i < r, use the combining formula given in Section 2.5 to find such that bi+1 ≡ bi (mod νi) and bi+1 ≡ ai+1 (mod ni+1).
3.31	Apply Newton’s iteration to compute a zero of x2 – n.
3.32 (a)	Apply Newton’s iteration to compute a zero of xk – n.
3.34 (b)	The updating d(X) := d(X) – Xi–sb(X) needs to consider only the non-zero words of b.
3.36 (b)	First consider b = 0 and note that the roots of X(q–1)/2 – 1 (resp. X(q–1)/2 + 1) are all the quadratic residues (resp. non-residues) of .
3.36 (c)	First consider b = 0.
3.40	For , we have ord(a)|m and for each i = 1, . . . , r the multiplicity vpi (ord(a)) is the smallest of the non-negative integers k satisfying .
3.41 (a)	Use the CRT.
3.43 (a)	Use the CRT and the fact that for an odd prime r ≡ 3 (mod 4).
4.1 (a)	Using the CRT, reduce to the case that n is prime. Then is bijective ⇔ the restriction is bijective. Now, if gcd(a, φ(n)) = 1, the inverse of is given by , where ab ≡ 1 (mod φ(n)). On the other hand, if q is a prime divisor of gcd(a, φ(n)), choose an element with ord(y) = q. But then ya ≡ 1 (mod n), that is, is not injective. This exercise provides the foundation for the RSA cryptosystems.
4.1 (b)	In view of the CRT, reduce to the case n = pα for and α > 1. Then (pα–1)a ≡ 0 (mod n).
4.6	Consider the integral .
4.9	Use the CRT and lifting.
4.10	For proving , let n be an odd composite integer, choose a random and compute a square root x of y2 modulo n. By Exercise 4.9, the probability that x ≡ ±y (mod n) is at most 1/2.
4.12 (d)	Eliminate a from T (a, b, c) using a + b + c = 0. For each fixed c, allow b to vary and use a sieve to find out all the values of b for which T (a, b, c) is smooth for the fixed c.
4.13	You may use the prime number theorem and the fact that the sum of the reciprocals of the first t primes asymptotically approaches ln ln t.
4.15	If a < a1 or a > am, then no i exists. So assume that a1 ≤ a ≤ am and let d := ⌊(1 + m)/2⌋. If a = ad, return d, else if a < ad, recursively search a among the elements a1, . . . , ad–1, and if a > ad, recursively search a among the elements ad+1, . . . , am.
4.16 (a)	Use Lagrange’s interpolation formula (Exercise 2.53).
4.18 (a)	One may precompute the values σi := p rem qi, i = 1, . . . , t. Note that qi|(gα + kp) if and only if ρk,i = 0.
4.19 (a)	Use the approximation T (c1, c2) ≈ (c1 + c2)H.
4.21 (c)	T (a, b, c) = –b2 – c(x + cy)b + (z – c2x).
4.21 (d)	Imitate the second stage of the LSM.
4.23	Let the factor base consist of all irreducible polynomials over of degrees ≤ m together with the polynomials of the form Xk + h(X), , deg h ≤ m. The optimal running time of this algorithm corresponds to .
4.24 (b)	is square-free.
4.24 (c)	Use the fact Xm – 1 = (Xm/pvp(m) – 1)pvp(m).
4.24 (d)	Theorem 2.39.
4.25 (a)	Look at the roots of the polynomials on the two sides.
4.25 (c)	If ord ω = m, then ord(–ω) = 2m.
4.25 (d)	ω, ωq, . . . , ωql–1 are all the roots of the minimal polynomial of ω over .
4.26 (b)	Use the Mordell–Weil theorem.
4.26 (c)	Use Theorem 4.2.
5.2 (a)	Solve the simultaneous congruences x ≡ ci (mod ni), i = 1, . . . , e, and then take the integer e-th root of the solution x, 1 ≤ x ≤ n1 · · · ne.
5.2 (b)	Append (different) pseudorandom bit strings to m before encryption. This process is often referred to as salting.
5.3 (a)	In view of the Chinese remainder theorem, reduce to the case n = pr for some and .
5.4	ue1 + ve2 = 1 for some u, .
5.6	If the same session key is used to generate the ciphertext pairs (r1, s1) and (r2, s2) on two plaintext messages m1 and m2, then m1/m2 = s1/s2.
5.7 (c)	Let x = (xl–1 . . . x1x0)2. Define x′ := (xl–1 . . . x2x1)2 and y′ := gx′ (mod p). Then, y ≡ y′2gx0 (mod p). Since x0 is easily computable, y′ can be obtained by obtaining a square root of y modulo p. Argue that a call of the oracle helps us choose the correct square root y′ of y. Now, use recursion.
5.8	Let g′ be any randomly chosen generator of , where q := ph. One computes for i = 0, 1, . . . , p – 1. We then have the equality of the sets modulo q – 1, where l := indg′ g. But then for each i we have a (yet unknown) j such that . Show that trying all possibilities for i and j one can effectively recover l and hence g = g′l and hence π.
5.9	Let g′, and l be as in Exercise 5.8. Now, we have the equality of the sets modulo q – 1.
5.11	(mod β) are polynomials with small coefficients.
5.15 (a)	If Alice generates the signatures (M1, s1) and (M2, s2) on two messages M1 and M2, then her signature on a message M with H(M) ≡ H(M1)H(M2) (mod n) is s1s2 (mod n). Thus, without knowing the private key of Alice, an intruder can generate a valid signature (M, s1s2) of Alice, provided that such an M can be computed. Of course, here the intruder has little control over the message M. The PKC standards form RSA Laboratories add some redundancy to the hash function output before signing. The product of two hash values with redundancy is, in general, expected not to have the redundancy. This increases the security of the scheme against existential forgeries beyond that provided by the first pre-image resistance of the underlying hash function.
5.15 (b)	For any , a valid signature is (M, s), where H(M) ≡ s2 (mod n).
5.15 (c)	Choose random integers u, v with gcd(v, n) = 1 and take d′ := u + dv. Of course, d and hence d′ are unknown to Carol, but she can compute s = gd′ = gu(gd)v and t ≡ –H(s)v–1 (mod n). But then (M, s, t) is a valid ElGamal signature on a message M for which H(M) ≡ tu (mod n).
5.16	Obviously, c itself could be a possible choice, but that is not random and Bob might refuse to sign c. Carol should hide c by cre (mod n) for some randomly chosen r known to her.
5.23 (a)	by the CRT.
5.25 (a)	Replace the random challenge of the verifier by the hash value of the string obtained by concatenating the message to be signed with the witness.
5.26 (d)	Bob finds a random b′ with and sends a := (b′)2 (mod n) to Alice. But then Alice’s response b yields a non-trivial factor gcd(b – b′, n) of n.
7.5	(mod n) and m ≡ se (mod n).
7.9 (a)	Use Exercise 2.44(b).
7.9 (c)	Again use Exercise 2.44(b).
7.9 (d)	Use Part (c) in conjunction with the CRT, and separately consider the three cases v2(p–1) = v2(q – 1), v2(p – 1) > v2(q – 1) and v2(p – 1) < v2(q – 1).
A.2	for all X, J. One does not have to look at the S-boxes for proving this.
A.9 (c)	For i = 0, 1, 2, 3, 4Nr, 4Nr + 1, 4Nr + 2, 4Nr + 3, take . For other values of i, take .
A.14 (b)	Let DL(X) := XdCL(1/X) = a0 + a1X + a2X2 + · · · + ad–1Xd–1 + Xd. Consider the -algebra , where x := X + 〈DL(X)〉. The -linear transformation λx : A → A defined by g(x) ↦ xg(x) has the matrix ΔL with respect to the polynomial basis (1, x, . . . , xd–1). If is the minimal polynomial of λx, then [f(λx)](1) = f(x) = 0. Now, use the fact that 1, x, . . . , xd–1 are linearly independent over .
A.16 (b)	[only if] Take σ ≠ 00 · · · 01. Since σ is non-zero, si = 1 for some . Construct an LFSR with d – 1 stages initialized to s0s1 · · · sd–2 to generate σ.
A.19	Suppose that we want to compute a second pre-image for H2(x). If , any is a second pre-image for H2(x). If , computing a second pre-image for H2(x) is equivalent to computing a second pre-image for H(x). The density of the (finite) set S is 0 in the (infinite) set of all bit strings. Thus, H2 is second pre-image resistant. On the other hand, for any two distinct x, we have a collision (x, x′) for H2.
A.20	Collision resistance of H implies that of H3. On the other hand, for a positive fraction (half) of the (n + 1)-bit strings y, it is easy to compute a pre-image of y under H3.
A.21	If y is a square root of a modulo m, then so is m – y too.
A.22	Use the birthday paradox (Exercise 2.172).
A.23 (d)	Let L := F1(L′) and R := F1(R′) with both R and R′ non-zero. Then, F1(L ‖ R) = F2(L′ ‖ R′).
A.25	Let h(i) denote the column vector of dimension 160 having the bits of H(i) as its elements and m(i) the column vector of dimension 512 + 160 = 672 having the bits of M(i) and of H(i) as its elements. Show that the modified design of SHA-1 leads to the relation h(i) ≡ Am(i–1) + c (mod 2) for some constant 160 × 672 matrix A over and for some constant vector c. So what then?
C.6	For α, , call α ≤ β if and only if |α| < |β| or |α| = |β| and α is lexicographically smaller than β. This ≤ produces a well-ordering of Σ*. For a one-way function f, look at the language for some with γ ≤ β}.