Unless otherwise stated F denotes an arbitrary field.

Algorithm: UnivariateDivision (Version I: Long division)

Input: f, g ∈ F [x] with g ≠ 0. Output: q, r ∈ F [x] such that f = qg + r with r = 0 or deg r < deg g. BEGIN q := 0; r := f; while deg r ≮ deg g do

(∗ Recall that deg 0 < deg p for all non-zero polynomials p ∈ F [x]. ∗) (∗ Loop invariant: f = qg + r. ∗) t := lt r/ lt g; (∗ lt(tg) = lt r ∗) q := q + t; r := r − tg;

end while; return q, r; END

Algorithm: UnivariateDivision (Version II)

Input: f, g ∈ F [x] with g ≠ 0. Output: q, r ∈ F [x] such that f = qg + r with r = 0 or deg r < deg g. BEGIN q := 0; r := 0; p := f; while p ≠ 0 do

(∗ Loop invariant: f = p + qg + r. ∗)

if lt g | lt p then (∗ Equivalent condition: deg g ⩽ deg p. ∗) t := lt p/ lt g; (∗ lt(tg) = lt p. ∗)

q := q + t;
p := p − tg;

else

r := r + lt p;
p := p − lt p;

end if; end while; return q, r; END

Algorithm: EuclideanAlgorithm (Extended; Version I)

Input: f, g ∈ F [x]. Output: h, a, b ∈ F [x] such that h = af + bg and h is a g.c.d. of f and g). BEGIN p_{0} := f; p_{1} := g; a_{0} := 1; a_{1} := 0; b_{0} := 0; b_{1} := 1; j := 1; while p_{j} ≠ 0 do

(∗ Invariant: p_{i} = a_{i}f + b_{i}g for all i. ∗) q_{j}, p_{j+1} := UnivariateDivision(p_{j−1}, p_{j}); (∗ Quotient q_{j}, remainder p_{j+1}. We have p_{j+1} = p_{j−1} − q_{j}p_{j}. ∗) a_{j+1} := a_{j−1} − q_{j}a_{j}; b_{j+1} := b_{j−1} − q_{j}b_{j}; j := j + 1; (∗ Writable as j+ := 1; ∗)

end while; h := p_{j−1}; a := a_{j−1}; b := b_{j−1}; return h, a, b; END

Algorithm: EuclideanAlgorithm (Extended; Version II)

Input: f, g ∈ F [x]. Output: h, a, b ∈ F [x] such that h = af + bg and h is a g.c.d. of f and g). BEGIN p_{0} := f; p_{1} := g; a_{0} := 1; a_{1} := 0; b_{0} := 0; b_{1} := 1; while p_{1} ≠ 0 do

(∗ Invariant: p_{i} = a_{i}f + b_{i}g for all i. ∗)

    q, p_{2} := UnivariateDivision(p_{0}, p_{1});

(∗ Quotient q, remainder p_{2}. We have p_{2} = p_{0} − qp_{1}. ∗)

a_{2} := a_{0} − qa_{1}; b_{2} := b_{0} − qb_{1}; (∗ Now to place the current working values for the ps, namely

p_{1} and p_{2}, into p_{0} and p_{1}. Similarly for the as and bs. ∗)

p_{0} := p_{1}; a_{0} := a_{1}; b_{0} := b_{1}; p_{1} := p_{2}; a_{1} := a_{2}; b_{1} := b_{2}; (∗ Above two lines cannot be swapped. ∗)

end while; h := p_{0}; a := a_{0}; b := b_{0}; return h, a, b; END

Algorithm: MultivariateDivision

Input: f, f_{1}, f_{2}, …, f_{s} ∈ F [x_{1}, x_{2}, …, x_{n}] such that 0 ∉ {f_{1}, f_{2}, …, f_{s}}. Output: q_{1}, q_{2}, …, q_{s}, r ∈ F [x_{1}, x_{2}, …, x_{n}] such that

(i) f = q_{1}f_{1} + ⋯ + q_{s}f_{s} + r, and

for 1 ⩽ i ⩽ s if q_{i}f_{i} ≠ 0 then mdeg f ⩾ mdeg(q_{i}f_{i})

(ii) r = 0 or r = ∑_{β∈B} b_{β}\underline{x}^{β}, where 0 ≠ b_{β} ∈ F for all β ∈ B

and lt f_{i} ∤ b_{β}\underline{x}^{β} for each β ∈ B and i ∈ \{1, 2, …, s\}.

BEGIN for i ∈ {1, 2, …, s} do

q_{i} := 0; end for; r := 0; p := f; while p ≠ 0 do

(∗ Loop invariant: f = p + q_{1}f_{1} + ⋯ + q_{s}f_{s} + r. ∗) if there exists j ∈ {1, 2, …, s} such that lt f_{j} | lt p then i := least j ∈ {1, 2, …, s} such that lt f_{j} | lt p; t := lt p/ lt f_{i}; (∗ lt(tf_{i}) = t lt f_{i} = lt p. ∗)

q_{i} := q_{i} + t;
p := p − tf_{i};

else

r := r + lt p;
p := p − lt p;

end if; end while; return q_{1}, q_{2}, …, q_{s}, r; END

Algorithm: GröbnerBasis

Input: Non-zero f_{1}, f_{2}, …, f_{s} ∈ R = F [x_{1}, x_{2}, …, x_{n}]

and a monomial order ⩽ for R.

Output: A Gröbner basis G for ⟨f_{1}, f_{2}, …, f_{s}⟩

with respect to ⩽ such that f_{1}, f_{2}, …, f_{s} ∈ G.

BEGIN G := {f_{1}, f_{2}, …, f_{s}}; repeat

T := {}; t := |G|;

order the elements of G somehow as g_{1}, …, g_{t};

for i := 1, …, t − 1 do
for j := i + 1, …, t do

r := S(g_{i}, g_{j}) rem (g_{1}, …, g_{t}); if r ≠ 0 then

T := T ∪ {r};

end if; end for;

end for; G := G ∪ T;

until T = {}; return G; END

Algorithm: ReducedGröbnerBasis

Input: A Gröbner basis H = {h_{1}, …, h_{s}} w.r.t. ⩽ for the ideal

I of R = F [x_{1}, x_{2}, …, x_{n}] and the monomial order ⩽ of R.

Output: The reduced Gröbner basis G = {g_{1}, …, g_{m}} for I w.r.t. ⩽. BEGIN G := {h_{1}, h_{2}, …, h_{s}}; order G = {g_{1}, …, g_{s}} so that lt g_{1} ⩽ lt g_{2} ⩽ ⋯ ⩽ lt g_{s}. for j := s, s − 1, …, 1 do

if exists k ∈ { i : 1 ⩽ i ⩽ j − 1 | (lt g_{i} | lt g_{j}) } then

remove g_{j} from G;

end if; end for; rename the g_{i} so that G = {g_{1}, …, g_{m}} (m ⩽ s) and lt g_{1} ⩽ ⋯ ⩽ lt g_{m}; for j := 1, …, m do g_{j} := g_{j}/(lc g_{j}); end for; for j := 2, …, m do

flag := true; while flag do

if exists term t of g_{j} − lt g_{j} such that lt g_{i} | t for some i then choose such t so that lm t is maximal w.r.t. ⩽; let i be minimal such that lt g_{i} | t; (∗ We have 1 ⩽ i < j. Also t = lt t. ∗) g_{j} := g_{j} − (t/ lt g_{i})g_{i};

else

flag := false; end if;

end while; end for; return G = {g_{1}, …, g_{m}}; END

Algorithm: GramSchmidtOrthogonalisation

Input: Linearly independent vectors v_{1}, …, v_{r} ∈ F^{n} where r ⩽ n, F ⊆ ℂ. Output: Vectors v_{1}^{∗}, …, v_{r}^{∗} ∈ F^{n} satisfying v_{i}^{∗} · v_{j}^{∗} = 0 for 1 ⩽ i < j ⩽ r

such that v_{k} − v_{k}^{∗} ∈ ⟨v_{1}, …, v_{k−1}⟩_{F} for 1 ⩽ k ⩽ r.

BEGIN v_{1}^{∗} := v_{1}; (∗ If r ≠ 0. ∗) for i := 2, …, r do

for j := 1, …, i − 1 do

μ_{ij} := (v_{i} · v_{j}^{∗})/(v_{j}^{∗} · v_{j}^{∗});

end for;

(∗ We can also define μ_{ii} = 1 and μ_{ij} = 0 if j > i. ∗) v_{i}^{∗} := v_{i} − ∑_{j=1}^{i−1} μ_{ij}v_{j}^{∗};

end for; return v_{1}^{∗}, v_{2}^{∗}, …, v_{r}^{∗}; END

Algorithm: BasisReduction (Variant of LLL)

Input: ℝ-linearly independent vectors v_{1}, …, v_{n} ∈ ℤ^{n}. Output: A reduced basis (w_{1}, …, w_{n}) of the lattice L = ⟨v_{1}, …, v_{n}⟩_{ℤ} such

that if ((w_{1}^{∗}, …, w_{n}^{∗}), (μ_{st})) is the Gram–Schmidt orthogonalisation of (w_{1}, …, w_{n}) then |μ_{st}| ⩽ \frac{1}{2} for 1 ⩽ t < s ⩽ n.

BEGIN (w_{1}, …, w_{n}) := (v_{1}, …, v_{n}); ((w_{1}^{∗}, …, w_{n}^{∗}), (μ_{st})) := GramSchmidtOrthogonalisation(w_{1}, …, w_{n}); i := 2; while i ⩽ n do

for j := i − 1, i − 2, …, 1 do (∗ Loop invariant: (w_{1}, …, w_{n}) is a basis for L and has GSO

((w_{1}^{∗}, …, w_{n}^{∗}), (μ_{st})), where |μ_{il}| ⩽ \frac{1}{2} for l = j + 1, …, i − 1. ∗) m := Round(μ_{ij}); (∗ so m ∈ ℤ and |μ_{ij} − m| ⩽ \frac{1}{2}. ∗) w_{i} := w_{i} − mw_{j}; (∗ Does not change ⟨w_{1}, …, w_{m}⟩_{ℤ} or any of the w_{k}^{∗} in the GSO. ∗) for l := 1, …, j do

μ_{il} := μ_{il} − mμ_{jl}; end for;

end for; (∗ Now |μ_{il}| ⩽ \frac{1}{2} for l = 1, 2, …, i − 1. ∗) if i > 1 and |w_{i−1}^{∗}|^{2} > 2|w_{i}^{∗}|^{2} then

Exchange the values of w_{i−1} and w_{i}; Update ((w_{1}^{∗}, …, w_{n}^{∗}), (μ_{st})) to be the GSO of (w_{1}, …, w_{n}); (∗ Think about how to do this efficiently:

only w_{i−1}^{∗}, w_{i}^{∗} and various of the μ_{jk} get altered. ∗) i := i − 1;

else

i := i + 1; end if;

end while; return (w_{1}, …, w_{n}); END