---------------------------------------------------------------- -- Pseudo Euclidean Algorithm (pseudo_Euclidean_algorithm.adb) -- -- -- ---------------------------------------------------------------- with Gnat.Io; use Gnat.Io; with Polynomials; use Polynomials; procedure Pseudo_Euclidean_Algorithm is F, G, H, C, D, E, Z, Y, Zero: Polynomial; N_A, N_B, N_R: Polynomial; Deg_A, Deg_B, Deg_R, Dif: Natural; Coef: Natural_Mod_P; begin for I in 0 .. M loop G(I) := 0; H(I) := 0; F(I) := 0; end loop; --F(0) := 237; F(17) := 1; F(0) := 237; F(7) := 29; F(14) := 42; F(17) := 1; G(1) := 1; G(5) := 47; G(9) := 230; G(15) := 117; H(3) := 211; H(9) := 123; H(11) := 7; H(15) := 189; for I in 0 .. M loop Zero(I) := 0; end loop; ---------------------------------------------------------------------------- --n_a := f; deg_a := m; n_b := h; deg_b := m; c := zero; d := g; N_A := F; Deg_A := M; N_B := Multiply_By_X(H); Deg_B := M-1; C := Zero; D := G; --previous step: while N_B(M) = 0 loop N_B := Multiply_By_X(N_B); Deg_B := Deg_B-1; end loop; ---- while Deg_B > 0 loop Dif := Deg_A - Deg_B; Coef := (N_A(M)*Invert(N_B(M))) mod P; --thread1: N_R := Subtract(N_A, Product(N_B,Coef)); Deg_R := Deg_A; while N_R(M) = 0 loop N_R := Multiply_By_X(N_R); Deg_R := Deg_R-1; end loop; --thread2: E := D; for I in 1 .. Dif loop E := Multiply_By_X(E, F); end loop; E := Subtract(C, Product(E,Coef)); ---- if Deg_B >= Deg_R then N_A := N_B; Deg_A := Deg_B; N_B := N_R; Deg_B := Deg_R; C := D; D := E; else N_A := N_R; Deg_A := Deg_R; C := E; end if; end loop; Z := Product(D,Invert(N_B(M))); ----------------------------------------------------------------------------- Y := Product_Mod_F(Z, H, F); Put("g = "); for I in 0 .. M-1 loop Put(G(I)); Put(" "); end loop; New_Line; Put("h = "); for I in 0 .. M-1 loop Put(H(I)); Put(" "); end loop; New_Line; Put("z = "); for I in 0 .. M-1 loop Put(Z(I)); Put(" "); end loop; New_Line; Put("z.h = "); for I in 0 .. M-1 loop Put(Y(I)); Put(" "); end loop; New_Line; end Pseudo_Euclidean_Algorithm;