On a computer with word size w, multiplication modulo n where n < w/2 can he performed...

On a computer with word size w, multiplication modulo n where n < w/2 can he performed as outlined. Let , and t = T2− n. For each computation, show that all the required compute] arithmetic can be done without exceeding the word size.(This method was described by Head [He80].

a) Show that 0 < t ≤ T.

---

b) Show that if x and y are nonnegative integers less than n. then

,

where a, b, c, and d are integers such that 0 ≤ a ≤ T,0 ≤ b < T,0 ≤ c ≤ T, and 0 ≤ d < T.

---

c) Let z = ad + be (mod n). such that 0 ≤ z < n. Show that

.

---

d) Let ac = eT+ f, where e and f are integers with 0 ≤ e ≤ T and 0 ≤ f < T. Show that

.

---

e) Let v = z + et (mod n), such that 0 ≤ υ < n. Show that we can write

.

where g and h are integers with 0 ≤ g ≤ T,0 ≤ h < 7, and such that

.

---

f) Show that the right−hand side of the congruence of part (e) can be computed without exceeding the word size, by first finding j such that

and 0 ≤ j < n, and then finding k such that

and 0 ≤ k < n, so that

This gives the desired result.