Manuel Kauers Hagenberg, December 17, 2002 RISC-Linz

Computer Algebra Exercises

Solution 4

Ex. (16) Given the problem to find a minimal r ∈ ℤ such that

r ≡ 62 mod 79,
r ≡ 66 mod 83,
r ≡ 72 mod 89.

We note that the moduli are pairwise coprime as required. To solve this problem by Lagrange, we first compute ((u_{kj}))_{kj} such that

1 = u_{kj}m_{k} + u_{jk}m_{j} (k ≠ j)

using the Extended Euclidean Algorithm. We get

((u_{kj})) = (\begin{matrix}∗ & −21 & −9 \\ 20 & ∗ & −15 \\ 8 & 14 & ∗ \end{matrix}) .

We plug these results into

l_{k} = ∏_{{j=0 \atop j≠k}}^{2} u_{jk}m_{j} mod m_{k}

obtaining

l_{0} = 1 181 920,  l_{1} = −2 067 114,  l_{2} = 885 195.

Finally,

r = ∑_{k=0}^{2} r_{k}l_{k} = 62 · 1 181 920 − 66 · 2 067 114 + 72 · 885 195 = 583 556.

Using Newton’s algorithm, we get the same result: Denote by M_{k} the product of all m_{i} (i < k) and by M_{k}^{−1} its inverse modulo m_{k}. Furthermore, let

s_{k} := ((r_{k} − R_{k} mod m_{k}) · M_{k}^{−1}) mod m_{k}

and R_{k} := R_{k−1} + s_{k} · M_{k} starting with R_{0} = M_{0}. Then R_{2} provides the solution.

\begin{matrix}k & r_{k} & m_{k} & M_{k} & M_{k}^{−1} & s_{k} & R_{k} \\ 0 & 62 & 79 & 1 & 1 & – & 62 \\ 1 & 66 & 83 & 79 & 62 & 82 & 6 540 \\ 2 & 72 & 89 & 6 557 & 46 & 88 & 583 556 \end{matrix}

Fortunately, the solution is the same.

Ex. (17) Given the problem to find a polynomial p ∈ ℚ[x] of minimum degree with

p ≡ 7x − 2 mod x^{2} + x − 1,
p ≡ 11x + 8 mod x^{2} − x − 1,
p ≡ −3x mod x^{2} + x + 1.

To find a solution via Lagrange, we first compute the ((u_{kj})) as before. There existence also proves that the moduli are coprime. We get

((u_{kj})) = (\begin{matrix}∗ & 1/2x − 1/2 & −1/2 \\ −1/2x − 1/2 & ∗ & 1/2x \\ 1/2 & −1/2x + 1 & ∗ \end{matrix}) .

Plugging these results into

l_{k} = ∏_{{j=0 \atop j≠k}}^{2} u_{jk}m_{j} mod m_{k}

gives

l_{0} = −\frac{1}{4}(x + 1)(x^{2} − x − 1)(x^{2} + x + 1),
l_{1} = −\frac{1}{4}(x − 1)(x^{2} + x − 1)(x − 2)(x^{2} + x + 1),
l_{2} = −\frac{1}{4}(x^{2} + x − 1)(x^{2} − x − 1)

which leads to the solution

p = ∑_{k=0}^{2} r_{k}l_{k} = −\frac{1}{4}(11x^{7} + x^{6} − 36x^{5} − 13x^{4} + 23x^{2} + x − 14).

Again, the steps of Newton’s algorithm are presented as a table, using the same notation as in Exercise 16 above.

\begin{matrix}k & r_{k} & m_{k} & M_{k} & M_{k}^{−1} & s_{k} & R_{k} \\ 0 & 7x − 2 & x^{2} + x − 1 & 1 & 1 & – & 7x − 2 \\ 1 & 11x + 8 & x^{2} − x − 1 & m_{0} & \frac{1}{2}x − \frac{1}{2} & 5x − 3 & 5x^{3} + 2x^{2} − x + 1 \\ 2 & −3x & x^{2} + x + 1 & m_{0}m_{1} & −\frac{1}{4}x & x & x^{5} + 2x^{3} + 2x^{2} + 1 \end{matrix}

In fact, MAPLE verifies that both results differ only by a multiple of ∏_{i=0}^{2} m_{i} as they should:

>> p:=(x^2+x-1)*(x^2-x-1)*(x^2+x+1):
>> r:=-1/4*(11*x^7+x^6-36*x^5-13*x^4+23*x^2+x-14):
>> rem(r,p,x);

x^{5} + 2x^{3} + 2x^{2} + 1

Ex. (18) If A_{i} denotes the matrix which is obtained by replacing the ith column of A by b, then Cramer’s rule says that x = (x_{1}, …, x_{n}) with

x_{i} = \frac{det A_{i}}{det A}

is a solution to Ax = b if and only if det A = 0 (otherwise, there is no solution).

The determinant det A may be computed modulo some primes p_{1}, …, p_{m}, which leads to the Chinese Remainder System

det A = r_{i} mod p_{i} (i = 1, …, m),

likewise with the determinants det A_{i}. If the product of all the primes is larger than the value of those determinants in ℤ, then the solution of those CRPs are exactly the desired values.

So, let’s do it.

1. det A:

det A =_{19} |\begin{matrix}7 & 6 & 14 \\ 2 & 10 & 4 \\ 13 & 14 & 13 \end{matrix}| =_{19} 17 + 8 + 12 − 15 − 12 − 4 =_{19} 6,

det A =_{41} |\begin{matrix}7 & 6 & 36 \\ 2 & 32 & 4 \\ 13 & 36 & 35 \end{matrix}| =_{41} 9 + 25 + 9 − 11 − 24 − 10 =_{41} 39,

and hence

det A = 6 mod 19 = 39 mod 41.

which has the solution

det A = 6 + 19 · ((39 − 6) · (19^{−1} mod 41) mod 41) = 367.

2. det A_{1}:

det A_{1} =_{19} |\begin{matrix}3 & 6 & 14 \\ 5 & 10 & 4 \\ 7 & 14 & 13 \end{matrix}| =_{19} 10 + 16 + 11 − 11 − 16 − 10 =_{19} 0,

det A_{1} =_{41} |\begin{matrix}3 & 6 & 36 \\ 5 & 32 & 4 \\ 7 & 36 & 35 \end{matrix}| =_{41} 39 + 4 + 2 − 28 − 22 − 25 =_{41} 11,

and hence

det A_{1} = 0 mod 19 = 11 mod 41.

which has the solution

det A_{1} = 0 + 19 · (11 · (19^{−1} mod 41) mod 41) = 380.

3. det A_{2}:

det A_{2} =_{19} |\begin{matrix}7 & 3 & 14 \\ 2 & 5 & 4 \\ 13 & 7 & 13 \end{matrix}| =_{19} 18 + 4 + 6 − 17 − 6 − 2 =_{19} 3,

det A_{1} =_{41} |\begin{matrix}7 & 3 & 36 \\ 2 & 5 & 4 \\ 13 & 7 & 35 \end{matrix}| =_{41} 36 + 33 + 12 − 3 − 32 − 5 =_{41} 0,

and hence

det A_{2} = 3 mod 19 = 0 mod 41.

which has the solution

det A_{2} = 3 + 19 · (−3 · (19^{−1} mod 41) mod 41) = 41.

4. det A_{3}:

det A_{3} =_{19} |\begin{matrix}7 & 6 & 3 \\ 2 & 10 & 5 \\ 13 & 14 & 7 \end{matrix}| =_{19} 15 + 10 + 8 − 10 − 15 − 8 =_{19} 0,

det A_{3} =_{41} |\begin{matrix}7 & 6 & 3 \\ 2 & 32 & 5 \\ 13 & 36 & 7 \end{matrix}| =_{41} 10 + 21 + 11 − 18 − 30 − 2 =_{41} 33,

and hence

det A_{3} = 0 mod 19 = 33 mod 41.

which has the solution

det A_{3} = 0 + 19 · (33 · (19^{−1} mod 41) mod 41) = 361.

Putting things together, we obtain the solution

x = \frac{1}{367}(380, 41, 361) ∈ ℤ^{3}

to the original system.

Ex. (19) First, Alice selects two huge primes p, q, say p = 7 and q = 13 and calculates N = p · q and φ(N) = (p − 1)(q − 1). For security reasons, she then deletes p and q. After that she choses some e ∈ {1, …, N − 1}, say e = 11 and finds d = e^{−1} mod φ(N) by the extended Euclidean algorithm. This is d = 59 in our example. She publishes (N, e) = (91, 11) as her public key and keeps d = 59 private.

To send a message m = 83 to Alice, Bob visits her web page to find her public key (N, e) = (91, 11) there. He sends

E(m) = m^{e} mod N = 83^{11} mod 91 = 34

to Alice.

Suppose now that Alice recieves a message E(m) = 34. In oder to decrypt it she calculates

D(E(m)) = E(m)^{d} mod N = 34^{59} mod 91 = 83 = m

because

E(m)^{d} = (m^{e})^{d} = m^{ed} = m^{1−φ(N)} = m · \underbrace{m^{−φ(N)}}_{=1 mod N} = m.

Ex. (20)

(a) To prove that g = gcd(m_{n}, M) is a unit, assume the contrary. Then g contains some irreducible factor p | g. By the definition of gcd, we have

p | m_{n} ∧ p | M.

But if M = m_{1} · M′ then by the irreducibility of p it follows that

p | m_{1} ∨ p | M′.

The former would contradict the fact that m_{1} and m_{n} are coprime, and to the latter we apply the same argument iteratively until we finally get p | m_{n−1} which is also impossible since m_{n−1} and m_{n} are coprime as well. .

(b) “⇐”: Assume r = r′ mod m_{1}m_{2}. Then:

r = r′ mod m_{1}m_{2}
⟹  m_{1}m_{2} | r − r′
⟹  ∃u : m_{1}m_{2}u = r − r′
⟹  ∃u_{1} = um_{2} : m_{1}u_{1} = r − r′ ∧ ∃u_{2} = um_{2} : m_{2}u_{2} = r − r′
⟹  m_{1} | r − r′ ∧ m_{2} | r − r′
⟹  r = r′ mod m_{1} ∧ r = r′ mod m_{2}.

“⇒”: Now assume r = r′ mod m_{1}, r = r′ mod m_{2}, and gcd(m_{1}, m_{2}) = 1. Then:

r = r′ mod m_{1}, r = r′ mod m_{2}
⟹  m_{1} | r′ − r, m_{2} | r′ − r
⟹  ∃u_{1} : u_{1}m_{1} = r′ − r ∧ ∃u_{2} : u_{2}m_{2} = r′ − r
⟹  u_{1}m_{1} = u_{2}m_{2} = r′ − r.

Furthermore, we know from the coprimarity that

v_{1}m_{1} + v_{2}m_{2} = 1

for some v_{1}, v_{2}. Now,

u_{1}m_{1} = u_{1}m_{1} · 1 = u_{1}m_{1} · (v_{1}m_{1} + v_{2}m_{2})

= u_{1}v_{1}m_{1}^{2} + u_{1}v_{2}m_{1}m_{2}

= v_{1}m_{1} \underbrace{(u_{1}m_{1})}_{=u_{2}m_{2}} +u_{1}v_{2}m_{1}m_{2}

= (v_{1}u_{2} + u_{1}v_{2})m_{1}m_{2},

and thus

(v_{1}u_{2} + u_{1}v_{2})m_{1}m_{2} = u_{1}m_{1} = r′ − r
⟹  m_{1}m_{2} | r′ − r
⟹  r = r′ mod m_{1}m_{2}

which completes the proof. .