---------------------------------------------------------------- -- finite_fields package body (finite_fields.adb) -- -- Defines several usefull funtions for finite fields operations -- of Chapter 3 examples ---------------------------------------------------------------- package body finite_fields is function b_table(m: digit) return digit_vector is b: digit_vector; begin b(0) := 1; for i in 1 .. s-1 loop b(i) := (2**(i*k)) mod m; end loop; return b; end b_table; function mod_m_addition(x, y, m, k: natural) return natural is z1, z2, c1, c2: natural; begin z1 := x + y; z2 := (z1 mod 2**k) + (2**k - m); c1 := z1/2**k; c2 := z2/2**k; if c1 = 0 and c2 = 0 then return (z1 mod 2**k); else return (z2 mod 2**k); end if; end mod_m_addition; procedure csa_mod_addition(xc, xs, y: in natural; rc, rs: out natural) is procedure csa(a, b, c: in natural; next_a, next_b: out natural) is binary_a, binary_b, binary_c, binary_next_a, binary_next_b: bit_vector(0 .. k+1); quotient, accumulator: natural; begin --natural to binary: quotient := a; for i in 0 .. k+1 loop binary_a(i) := quotient mod 2; quotient := quotient/2; end loop; quotient := b; for i in 0 .. k+1 loop binary_b(i) := quotient mod 2; quotient := quotient/2; end loop; quotient := c; for i in 0 .. k+1 loop binary_c(i) := quotient mod 2; quotient := quotient/2; end loop; --carry save addition: for i in 0 .. k+1 loop binary_next_a(i) := (binary_a(i) + binary_b(i) + binary_c(i)) mod 2; end loop; binary_next_b(0) := 0; for i in 1 .. k+1 loop binary_next_b(i) := (binary_a(i-1) + binary_b(i-1) + binary_c(i-1)) / 2; end loop; --binary to natural accumulator := 0; for i in 0 .. k+1 loop accumulator := accumulator + binary_next_a(i)*(2**i); end loop; next_a := accumulator; accumulator := 0; for i in 0 .. k+1 loop accumulator := accumulator + binary_next_b(i)*(2**i); end loop; next_b := accumulator; end csa; function quotient(ss, sc: in natural) return integer is ss_high, sc_high, t: natural; begin ss_high := ss / (2**(k-1)); sc_high := sc / (2**(k-1)); --with 4 bits: t := (ss_high + sc_high) mod 16; if t <= 3 then return 1; elsif t < 15 then return -1; else return 0; end if; end quotient; ws, wc, minus_m: natural; begin csa(xc, xs, y, wc, ws); minus_m := (2**(k+3)) - m; if quotient(ws, wc) = 1 then csa(wc, ws, minus_m, rc, rs); elsif quotient(ws, wc) = 0 then csa(wc, ws, 0, rc, rs); else csa(wc, ws, m, rc, rs); end if; rc := rc mod 2**(k+2); rs := rs mod 2**(k+2); end csa_mod_addition; procedure csa_mod_doubling(xc, xs: in natural; rc, rs: out natural) is procedure csa(a, b, c: in natural; next_a, next_b: out natural) is binary_a, binary_b, binary_c, binary_next_a, binary_next_b: bit_vector(0 .. k+1); quotient, accumulator: natural; begin --natural to binary: quotient := a; for i in 0 .. k+1 loop binary_a(i) := quotient mod 2; quotient := quotient/2; end loop; quotient := b; for i in 0 .. k+1 loop binary_b(i) := quotient mod 2; quotient := quotient/2; end loop; quotient := c; for i in 0 .. k+1 loop binary_c(i) := quotient mod 2; quotient := quotient/2; end loop; --carry save addition: for i in 0 .. k+1 loop binary_next_a(i) := (binary_a(i) + binary_b(i) + binary_c(i)) mod 2; end loop; binary_next_b(0) := 0; for i in 1 .. k+1 loop binary_next_b(i) := (binary_a(i-1) + binary_b(i-1) + binary_c(i-1)) / 2; end loop; --binary to natural accumulator := 0; for i in 0 .. k+1 loop accumulator := accumulator + binary_next_a(i)*(2**i); end loop; next_a := accumulator; accumulator := 0; for i in 0 .. k+1 loop accumulator := accumulator + binary_next_b(i)*(2**i); end loop; next_b := accumulator; end csa; function quotient(ss, sc: in natural) return integer is ss_high, sc_high, t: natural; begin ss_high := ss / (2**(k-1)); sc_high := sc / (2**(k-1)); --with 4 bits: t := (ss_high + sc_high) mod 16; if t <= 3 then return 1; elsif t < 15 then return -1; else return 0; end if; end quotient; ws, wc, minus_m: integer; begin ws := 2*xs; wc := 2*xc; minus_m := (2**(k+3)) - m; if quotient(ws, wc) = 1 then csa(wc, ws, minus_m, rc, rs); elsif quotient(ws, wc) = 0 then csa(wc, ws, 0, rc, rs); else csa(wc, ws, m, rc, rs); end if; rc := rc mod 2**(k+2); rs := rs mod 2**(k+2); end csa_mod_doubling; function mp(x, y: natural) return natural is product, q: natural; begin Product := X*Y; Q := (Product + ((Product*Minus_Inv_M) mod R)*M) / R; if Q >= M then return Q-M; else return Q; end if; end mp; end finite_fields;