# Example for division. This will be over Z_5, i.e. mod 5. # # a := x^4 + 3*x^2 + 2; b := 2*x^2 + 1; rec4a := 1 + 3*x^2 + 2*x^4; rec2b := 2+ x^2; # Here I've used the Extended Euclidean Algorithm to compute 1/rec2b mod x^3. # A "fast" algorithm would use Netwon iteration for polynomial inversion. # (Why?) print(`gcdex(rec2b,x^3,x,'rec2b_inv_rat','dummy')`, gcdex(rec2b,x^3,x,'rec2b_inv_rat','dummy')); # But we get rational coefficients. We must take them mod 5. print(`rec2b_inv_rat = `,rec2b_inv_rat); rec2b_inv := rec2b_inv_rat mod 5; print( `rec2q is expand(rem((rec4a * rec2b_inv),x^3,x)) mod 5 `, expand(rem((rec4a * rec2b_inv),x^3,x)) mod 5); rec2q := expand(rem((rec4a * rec2b_inv),x^3,x)) mod 5; # I did the reciprocal by hand, after I saw that rec2q was 3; q := 3*x^2; print(`r is expand(a-q*b) mod 5`, expand(a-q*b) mod 5); r := expand(a-q*b) mod 5; print(`q*b+r = `, expand(q*b + r) mod 5); print(`a =`, a);