with Gnat.Io; use Gnat.Io; package body Galois is function Divide_By_2(X, P: in Integer) return Integer is Y: Integer; begin if (X mod 2) = 0 then Y := X/2; else Y := (X+P)/2; end if; return Y; end Divide_By_2; function Divide_By_4(X, P: in Integer) return Integer is Y: Integer; begin if (P mod 4) = 1 then if (X mod 4) = 0 then Y := X/4; elsif (X mod 4) = 1 then Y := (X - P)/4; elsif (X mod 4) = 2 then Y := (X + 2*P)/4; else Y := (X + P)/4; end if; elsif (P mod 4) = 3 then if (X mod 4) = 0 then Y := X/4; elsif (X mod 4) = 1 then Y := (X + P)/4; elsif (X mod 4) = 2 then Y := (X + 2*P)/4; else Y := (X - P)/4; end if; end if; return Y; end Divide_By_4; function Degree(A: Polynomial) return Natural is X: Natural; begin for I in 0 .. M loop if A(I) > 0 then X := I; end if; end loop; return X; end Degree; function Subtract(A, B: Polynomial) return Polynomial is C: Polynomial; begin for I in 0 .. M loop C(I) := (A(I)-B(I)) mod P; end loop; return C; end Subtract; function Invert(Y: Natural_Mod_P) return Natural_Mod_P is A, B, C, D, Q, R, Next_D: Integer; begin A := P; B := Y; C := 0; D := 1; while B > 1 loop Q := A/B; R := A mod B; Next_D := C - D*Q; A := B; B := R; C := D; D := Next_D; end loop; return (D mod P); end Invert; function Product(A: Polynomial; B: Natural_Mod_P) return Polynomial is C: Polynomial; begin for I in 0 .. M loop C(I) := (A(I)*B) mod P; end loop; return C; end Product; function Shift_One(A: Polynomial) return Polynomial is B: Polynomial; begin for I in 0 .. M-1 loop B(I) := A(I+1); end loop; B(M) := 0; return B; end Shift_One; function Divide_By_X(A, F: Polynomial) return Polynomial is begin return Shift_One(Subtract(A, Product(F, ((A(0)*Invert(F(0))) mod P)))); end Divide_By_X; function Add(A, B: Polynomial) return Polynomial is C: Polynomial; begin for I in 0 .. M loop C(I) := (A(I)+B(I)) mod P; end loop; return C; end Add; function Multiply_By_X(A, F: Polynomial) return Polynomial is C, D: Polynomial; begin for I in 1 .. M-1 loop C(I) := A(I-1);end loop; C(0) := 0; C(M) := 0; for I in 0 .. M-1 loop D(I) := F(I);end loop; D(M) := 0; return Subtract(C, Product(D, A(M-1))); end Multiply_By_X; function Product_Mod_F(A, B, F: Polynomial) return Polynomial is C: Polynomial; begin for I in 0 .. M loop C(I) := 0; end loop; for I in 0 .. M-1 loop C := Add(Multiply_By_X(C, F), Product(A,B(M-1-I))); end loop; return C; end Product_Mod_F; function Frobenius(J, I: Natural)return Natural_Mod_P is C: constant Natural := 2; T: Natural; B, Z: Natural_Mod_P; begin T := P/M; B := (C**T) mod P; Z := 1; for K in 1 .. I*J loop Z := (Z*B)mod P; end loop; return Z; end Frobenius; function Quotient(Num, Den: Polynomial) return Polynomial is R, Q, A, B: Polynomial; U, V: Natural; begin R := Num; for I in 0 .. M loop Q(I) := 0; end loop; U := Degree(Num); V := Degree(Den); while U >= V loop Q(U-V) := (R(U)*Invert(Den(V))) mod P; A := Product(Den, Q(U-V)); for I in U-V .. M loop B(I) := A(I-U+V); end loop; for I in 0 .. U-V-1 loop B(I) := 0; end loop; R := Subtract(R, B); U := Degree(R); end loop; return Q; end Quotient; function Remainder(Num, Den: Polynomial) return Polynomial is R, Q, A, B: Polynomial; U, V: Natural; begin R := Num; for I in 0 .. M loop Q(I) := 0; end loop; U := Degree(Num); V := Degree(Den); while U >= V loop Q(U-V) := (R(U)*Invert(Den(V))) mod P; A := Product(Den, Q(U-V)); for I in U-V .. M loop B(I) := A(I-U+V); end loop; for I in 0 .. U-V-1 loop B(I) := 0; end loop; R := Subtract(R, B); U := Degree(R); end loop; return R; end Remainder; function Shift(A: Polynomial; T: Natural) return Polynomial is Shifted: Polynomial; begin for I in T .. M loop Shifted(I) := A(I-T); end loop; for I in 0 .. T-1 loop Shifted(I) := 0; end loop; return Shifted; end Shift; function Shift(A, F: Polynomial; T: Natural) return Polynomial is Shifted: Polynomial; begin Shifted := A; for J in 1 .. T loop Shifted := Multiply_By_X(Shifted, F); end loop; return Shifted; end Shift; procedure Swap(A, B: in out Polynomial) is Old_A: Polynomial; begin Old_A := A; A := B; B := Old_A; end Swap; procedure Swap(S, T: in out Natural) is Old_S: Natural; begin Old_S := S; S := T; T := Old_S; end Swap; function Mp(X, Y: in Natural) return Natural is Product, Q, A, Z: Natural; X_Bin: Bit_Vector; begin Q := X; for I in 0 .. Logp-1 loop X_Bin(I) := Q mod 2; Q := Q/2; end loop; Product := 0; for I in 0 .. Logp-1 loop A := Product + X_Bin(I)*Y; Product := (A + (A mod 2)*P)/2; end loop; if Product >= P then Z := Product - P; else Z := Product; end if; return Z; end Mp; end Galois;