Page 320 - Hardware Implementation of Finite-Field Arithmetic

300 Cha pte r T e n

Now, look for two integers a’ and b’ so that
α(P) = α’(τ(P)) + rP with α’ = a’ + b’τ and r ∈ { −1, 0, 1} (10.57)

According to Eqs. (10.55), (10.56), and (10.57)
2
aP + bτ(P) = (a’ + b’τ)τ(P) + rP = a’τ(P) + b’τ (P) + rP
= a’τ(P) + μb’τ(P) − 2b’P + rP = (a’ +μb’)τ(P) − (2b’ − r)P (10.58)

Hence, a = r − 2b’ and b = a’ + μb’, that is,
b’ = (r − a)/2 and a’ = b − μb’ = b + μ(a − r)/2 (10.59)

If a is even, then choose r = 0 so that

b’ = − a/2 a’ = b + μa/2 (10.60)
If a is odd, choose r in such a way that a’ is even, that is, 2a’ = 2b +
μa − μr is a multiple of 4. For that, consider the binary representations
( . . . a 1) and ( . . . b b ) of a and b. Then
1 1 0
2b + a = ( . . . b 0) + ( . . . a 1) = ( . . . a ⊕ b 1)
0 1 1 0
2b − a = ( . . . b 0) + ( . . . a 1) = ( . . . a ⊕ b ⊕ 1 1)
0 1 1 0
where ⊕ stands for the modulo 2 sum. If a ⊕ b = 0, choose r = 1 so that
1 0
2b + a − r = ( . . . 0 1) − 1 = ( . . . 0 0) if μ = 1 and
2b − a + r =( . . . 1 1) + 1 = ( . . . 0 0) if μ = − 1

If a ⊕ b = 1, choose r = − 1 so that
1 0
2b + a − r = ( . . . 1 1) + 1 = ( . . . 0 0) if μ = 1 and
2b − a + r = ( . . . 0 1) − 1 = ( . . . 0 0) if μ = − 1

To summarize:
1. If a is even, then r = 0, b’ = − a/2, and a’ = b − μb’ = b + μa/2.
2. If a is odd and a ⊕ b = 0, then r = 1, b’ = − (a − 1)/2, and a’ =
1 0
b − μb’ = b + μ(a − 1)/2.
3. If a is odd and a ⊕ b = 1, then r = − 1, b’ = − (a + 1)/2 and a’
1 0
= b − μb’ = b + μ(a + 1)/2.
Observe that if a is odd, then a − 2b = ( . . . a 1) − ( . . . b 0) = ( . . . a ⊕
1 0 1
b 1), so that (a − 2b) mod 4 is equal to 1 if a ⊕ b = 0 and equal to 3 if
0 1 0
a ⊕ b = 1. So, an alternative definition of r, when a is odd, is
1 0
r = 2 − ((a − 2b) mod 4) (10.61)