Chapter 5.8: Computing An Explicit Square Root in ℤ[θ].

To reemphasize the statements at the beginning of Chapter 5, it should be noted that the computations performed in this section for determining an explicit value of β ∈ ℤ[θ] for the β of Note 2.4.1 are never actually performed in practice. Since the value n = 45,113 in this running example is small, however, the value for β may be computed to check the methods of §5.9, §5.10, and §5.11.

Begin by finding an explicit representation for the product of the a + bθ values corresponding to the (a, b) pairs found in Table 5.5:

δ = 2051543129764485 ⋅ θ² + 15388377355799440 ⋅ θ + 24765692886531904

= (−1 + θ) ⋅ (3 + θ) ⋅ (13 + θ) ⋅ (104 + θ) ⋅ (3 + 2 ⋅ θ) ⋅ (25 + 2 ⋅ θ) ⋅ (−8 + 3 ⋅ θ) ⋅ (48 + 5 ⋅ θ) ⋅ (54 + 5 ⋅ θ) ⋅ (−43 + 6 ⋅ θ) ⋅ (−8 + 7 ⋅ θ) ⋅ (11 + 7 ⋅ θ) ⋅ (856 + 11 ⋅ θ)

where all the computations are treated as multiplication of polynomials modulo 𝑓(x) = x⋅3 + 15⋅x² + 29⋅x + 8 with θ substituted for x. Next, the value 𝑓′(θ)² = 138 ⋅ θ² + 363 ⋅ θ + 481 ∈ ℤ[θ] is computed and multiplied by (5.2) to yield

𝑓′(θ)² ⋅ δ = 22455983949710645412 ⋅ θ² + 54100105785512562427 ⋅ θ + 22939402657683071224

which is the square of an element β ∈ ℤ[θ]. Indeed, without too much more effort it is seen that

β = 599923511 ⋅ θ² + 3686043120 ⋅ θ + 3889976768

satisfies β² = 𝑓′(θ)² ⋅ δ in ℤ[θ].

Applying the ring homomorphism φ : ℤ[θ] → ℤ/45113ℤ of Proposition 2.4.1 to β gives

x = 43922 ≡ 694683807559 ≡ 599923511 ⋅ 312 + 3686043120 ⋅ 31 + 3889976768 ≡ φ(β) (mod 45331)

and it is this value x = 43,922 that should result from the square root techniques of §5.9, §5.10, and §5.11.

Chapter 5.9: Determining Applicable Finite Fields.

The first stage in computing x = φ(β) (mod p) using the methods outlined in §4.6, §4.7, and §4.8 is to find a number of finite fields that are “compatible” with Q(θ), which boils down to finding prime integers p for which 𝑓(x) remains irreducible modulo p. First, 𝑓(x) = x³ + 15 ⋅x2 + 29 ⋅x + 8 will be tested for irreducibility modulo the prime p = 9929 using the techniques of §4.9.

Begin by computing xᵖ − x modulo 𝑓(x)

x⁹²⁹⁹ − x ≡ 7449 ⋅ x² + 4697 ⋅ x + 5984 (mod 𝑓(x))

and then taking the greatest common divisor with 𝑓(x) gives

gcd(7449 ⋅ x² + 4697 ⋅ x + 5984, x³ + 15 ⋅ x² + 29 ⋅ x + 8) = 1

when considered modulo 9929. Thus, 𝑓(x) is irreducible over ℤ/9929ℤ by Theorem 4.9.5 and the finite field F99293 may be used in the methods of §4.6, §4.7, and §4.8.

As an example of a value for p for which 𝑓(x) does not turn out to be irreducible, if p = 9923 then

x⁹²⁹³ − x ≡ 7726 ⋅ x² + 1477 ⋅ x + 7301 (mod 𝑓(x))

and the greatest common divisor turns out to be

gcd(7726 ⋅ x² + 1477 ⋅ x + 7301, x³ + 15 ⋅ x² + 29 ⋅ x + 8) = x − 847 modulo 9923.

Hence 847 is a root of 𝑓(x) modulo 9923 and therefore 𝑓(x) is not irreducible over ℤ/9923ℤ.

Table 5.6 lists the three primes pi for which the finite field Fₚi3 will be used in §5.10 and §5.11 for computing x in §5.8.

Chapter 5.10: Square Roots in a Finite Field.

The techniques of §4.8 will be illustrated for the prime p = 9929 and the finite field Fₚ3, where the elements of the latter field may be represented as polynomials in θₚ where θₚ is a root of 𝑓(x) in the splitting field of 𝑓(x) = x³ + 15 ⋅ x² + 29 ⋅ x + 8 over ℤ/pℤ by Theorem 4.7.2. Denote Fₚ3 by Fₚ(θₚ) as well.

Begin by letting q = p³ so that q − 1 = 2ʳ ⋅ s where r = 3 and s = 122356359011.

The first task is to find a quadratic non-residue in Fₚ(θₚ), which is very easy since exactly half the elements satisfy this property. A direct search immediately yields θₚ + 1 as a non-residue by Theorem 4.8.1 since

(θₚ + 1)^(9929⁽³⁻¹⁾ᐟ²) ≡ −1 (mod 9929)

From Theorem 4.8.3 it follows that the Sylow 2-subgroup S₈ of Fₚ(θₚ) can then be represented by the set

S₈ = {1, (θₚ + 1)ˢ, (θₚ + 1)²ˢ, (θₚ + 1)³ˢ, . . . , (θₚ + 1)⁷ˢ}

Next, the element δ of §5.8 is computed in Fₚ(θₚ) as

δₚ = 2027 ⋅ θ² p + 3891 ⋅ θₚ + 6659

≡ 𝑓′(θₚ)² ⋅ (−1 + θₚ) ⋅ (3 + θₚ) ⋅ (13 + θₚ)⋅ (104 + θₚ) ⋅ (3 + 2 ⋅ θₚ) ⋅ (25 + 2 ⋅ θₚ) ⋅ (−8 + 3 ⋅ θₚ) ⋅ (48 + 5 ⋅ θₚ) ⋅ (54 + 5 ⋅ θₚ) ⋅ (−43 + 6 ⋅ θₚ) ⋅ (−8 + 7 ⋅ θₚ) ⋅ (11 + 7 ⋅ θₚ) ⋅ (856 + 11 ⋅ θₚ)

The immediate goal is then to find an element ζ ∈ S₈ with ζ² ≡ δˢ. By direct computation in Fₚ(θₚ) it is seen that δˢ ≡ 9928 (mod 9929) and from Table 5.7 it follows that ζ = (θₚ + 1)²ˢ ≡ 2102 (mod 9929) is an element with the desired property.

If ω = δ⁽ˢ⁺¹⁾ᐟ² then ν = ω ⋅ ζ⁻¹ is a square root of δ since

ν² ≡ ω² ⋅ ζ⁻² ≡ δˢ ⋅ δ ⋅ δ⁻ˢ ≡ δ

since ζ was found such that ζ² ≡ δˢ.

Computing out ν explicitly involves computing the multiplicative inverse 7827 of ζ = 2102 modulo 9929 and then multiplying out

ν = ω ⋅ ζ⁻¹ ≡ 7827 ⋅ δ⁽ˢ⁺¹⁾ᐟ² ≡ 3402⋅θₚ² + 1160⋅θₚ + 3077

Note that the other square root of δ is simply −ν in Fₚ(θₚ), which is seen to be 6527⋅θₚ² + 8769⋅θₚ + 6852

In the above description, the element ζ was found from the list of all its possible values in Table 5.7.

The actual square root algorithm employed in §4.8 uses an iterative approach to avoid the explicit computation of all elements in S₈. First, λ₀ is initialized as λ₀ = −1 ≡ δˢ (mod 9929) and ω₀ is initialized as ω₀ = 2124⋅θₚ² + 5175⋅θₚ + 4075 ≡ δ⁽ˢ⁺¹⁾ᐟ². Finally, the variable m is set to 1 since the order of λ₀ in F ∗ p3 is seen to be 2. The iterative process begins by calculating λ₁ and ω₁ from λ₀ and ω₀. Letting ζ = (θₚ + 1)ˢ ≡ 1273 (mod 9929) then

λ₁ ≡ λ₀ζ²ʳ⁻ᵐ ≡ −1 ⋅ 127323⁻¹ ≡ −1 ⋅ 12734 ≡ 1 (mod 9929)

and

ω₁ = ω₀ζ²ʳ⁻ᵐ-1 ≡ ω₀ ⋅ 1273^2⁽³⁻¹⁾-1 ≡ ω₀ ⋅ 12732 ≡ 6527⋅θₚ² + 8769⋅θₚ + 6852.

Since λ₁ = 1 it follows that ω₁ is a square root of δ, which is verified from the earlier calculation using Table 5.7.