Page 68 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 51

63
62
320
x = (x · 2 + x · 2 + . . . + x · 2 + x )2
383 382 321 320
62
63
256
+ (x · 2 + x · 2 + . . . + x · 2 + x )2
319 318 257 256
63
62
+ (x · 2 + x · 2 + . . . + x · 2 + x )2 192
255 254 193 192
190
+ (x · 2 + x · 2 + . . . + x · 2 + x ) (2.54)
191
191 190 1 0
Then observe that
2 ≡ 2 + 1
192
64
64
256
192
64
128
64
2 = 2 · 2 ≡ (2 + 1) 2 = 2 + 2 64
128
128
128
64
128
192
64
2 = 2 · 2 ≡ 2 (2 + 1) = 2 + 2 ≡ 2 + 2 + 1 (2.55)
320
192
According to Eqs. (2.54) and (2.55),
63
64
62
128
x ≡ (x · 2 + x · 2 + . . . + x · 2 + x )(2 + 2 + 1)
383 382 321 320
62
64
128
63
+ (x · 2 + x · 2 + . . . + x · 2 + x )(2 + 2 )
319 318 257 256
63
64
62
+ (x · 2 + x · 2 + . . . + x · 2 + x )( 2 +1)
255 254 193 192
191
190
+ (x · 2 + x ·2 + . . . + x · 2 + x ) (2.56)
191 190 1 0
Then define
63
191
128
127
x’ = x · 2 + . . . + x · 2 + x · 2 + . . . + x · 2 + x · 2
64
383 320 383 320 383
+ . . . + x
320
191
x’’ = x · 2 + . . . + x · 2 + x · 2 + . . . + x · 2 64
128
127
319 256 319 256
127
x’’’ = x · 2 + . . . + x · 2 + x · 2 + . . . + x
64
63
255 192 255 192
190
191
x’’’’ = x · 2 + x · 2 + . . . + x 2 + x (2.57)
191 190 1 0
Thus,
x ≡ s = x’ + x’’ + x’’’ + x’’’’ (2.58)
An upper limit for s is given by
192
64
s < 2 + (2 – 2 ) + 2 + 2 < 4(2 – 2 − 1) (2.59)
192
64
192
128
192
64
192
so that x mod (2 − 2 − 1) is either
192
64
64
192
64
192
s, s − (2 − 2 − 1), s – 2 · (2 − 2 − 1), or s – 3 · (2 − 2 − 1)
The corresponding circuit is shown in Fig. 2.11.
A VHDL file mod_p192_reducer.vhd is available at www.
arithmetic-circuits.org. The corresponding entity declaration is
entity mod_p192_reducer is
port(
x: in std_logic_vector(383 downto 0);
z: out std_logic_vector(191 downto 0)
);
end mod_p192_reducer;