Page 121 - Hardware Implementation of Finite-Field Arithmetic

104 Cha pte r F o u r

4.3 Plus-Minus Algorithm
The plus-minus algorithm ([Tak98], [MBQ04], [DS06]) is a modified
version of the binary algorithm. It is based on the following observations:
if a and b are odd, b + a and b − a will be even and their sum (b + a) +
i i i i i i i i
(b − a) = 2b cannot be a multiple of 4 (b is odd), so that either b + a mod
i i i i i i
4 = 0 and b − a mod 4 = 2, or b + a mod 4 = 2 and b − a mod 4 = 0. This
i i i i i i
allows dividing by 4, instead of 2, and possibly speeding up the
computation. Another modification consists of allowing negative
values of a and b, and using a convergence criterion based on their
i
i
absolute values ⏐a⏐ and ⏐b⏐. Actually, logarithmic estimations of ⏐a⏐
i i i
and ⏐b⏐are used, that is, integers α and β such that
i i i
α
a < 2 and b < 2 β i (4.26)
i
i i
Initially α =β = k. As before assume that a is odd and define a = a
0 0 0
and b = b. Two sequences a , a , a , . . . and b , b , b , . . . of integers are
0 1 2 3 1 2 3
generated: given a and b with a odd, then
i i i
If b mod 4 = 0: a = a , b = b /4, α =α and β =β − 2
i i + 1 i i + 1 i i + 1 i i + 1 i
If b mod 4 ≠ 0 and b is even: a = a , b = b /2,
i i i + 1 i i + 1 i
α =α and β =β − 1
i + 1 i i + 1 i
If b is odd, b + a mod 4 = 0 and β ≥α : a = a , b = (b + a )/4,
i i i i i i + 1 i i + 1 i i
α =α and β =β − 1
i + 1 i i + 1 i
If b is odd, b + a mod 4 = 0 and β < α : a = b , b = (b + a )/4,
i i i i i i + 1 i i + 1 i i
α =β and β =α − 1
i + 1 i i + 1 i
If b is odd, b − a mod 4 = 0 and β ≥α : a = a , b = (b − a )/4,
i i i i i i + 1 i i + 1 i i
α =α and β =β − 1
i + 1 i i + 1 i
If b is odd, b − a mod 4 = 0 and β < α : a = b , b = (b − a )/4,
i i i i i i + 1 i i + 1 i i
α =β and β =α − 1
i + 1 i i + 1 i
Obviously a is odd and gcd(a , b ) = gcd(a , b ) so that
i + 1 i + 1 i + 1 i i
gcd(a , b ) = gcd(a , b ) = . . . = gcd(a , b ) = gcd(a, b) (4.27)
i + 1 i + 1 i i 0 0
In order to demonstrate the convergence of this iteration, observe that
α + β < α + β. Observe also that as long as α > 0 and β > 0, α > 0.
i + 1 i + 1 i i i i i + 1
In conclusion, after a finite number of steps β ≤ 0, that is, ⏐b ⏐ < 1, and
i i
thus b = 0, so that gcd(a, b) = gcd(a , 0) =⏐a ⏐.
i i i
Lemma 4.4 After a finite number of steps, ⏐a ⏐= gcd(a, b).
i
In the particular case where a = p and b = y, the gcd is equal to 1, that
is, ⏐a ⏐= 1.
i
− 1
For computing z = xy mod p, two additional set of values c , c ,
1 2
c , . . . and d , d , d , . . . are computed in parallel. The initial values are
3 1 2 3
c = 0 and d = x. Then
0 0