15.2 INVERSION IN GF(p)
For relatively small p, the value of x−1 for all x {1, …,p − 1} can be computed in advance and stored within a look-up table. For larger values of p, Algorithm 8.16 can be used. As was already mentioned in Section 8.2, the value of c(i) belongs to the interval −p/2 < c(i) < p/2, so that
and all c(i) can be represented with n digits in reduced B's complement form. The value of r(i) belongs to the interval p ≥ r(i)≥1 so that all r(i) are n-digit base B numbers. The data path of the corresponding circuit is shown in Figure 15.11.
Example 15.7 (Complete VHDL source code available.) Generate the VHDL model of a circuit that computes z = x−1 modulo p, where x and p are two n-bit numbers, with x ≤ p. The structure of the data path is shown in Figure 15.11.
entity inv_data_path is port ( x: in std_logic_vector(n-1 downto 0); clk, first_step, enable: in std_logic; gt_one: out std_logic; z: out std_logic_vector(n-1 downto 0) ); end inv_data_path; architecture circuit of inv_data_path is signal r_i, r_iplus1, r_iplus2, c_i, c_iplus1, c_iplus2, next_r_i, next_r_iplus1, next_c_i, next_c_iplus1, zero, one, module, q: std_logic_vector(n-1 downto 0); component functional_divider…end component; component functional_multiplier…end component; begin zero<=conv_std_logic_vector(0, ...
Get Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.