X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/12208248afbfcdedac9494a68ab83f203335c1a3..a6d8eb54f8da26e372aa56951e4731ec00903f77:/math/gfreduce.h diff --git a/math/gfreduce.h b/math/gfreduce.h index b60c8fab..ef075c45 100644 --- a/math/gfreduce.h +++ b/math/gfreduce.h @@ -60,7 +60,8 @@ typedef struct gfreduce { mpw mask; /* Mask for degree word */ mp *p; /* Copy of the polynomial */ size_t in; /* Number of instruction words */ - gfreduce_instr *iv, *liv; /* Vector of instructions */ + gfreduce_instr *iv; /* Vector of instructions */ + gfreduce_instr *fiv; /* Final-pass instruction suffix */ } gfreduce; /*----- Functions provided ------------------------------------------------*/ @@ -128,7 +129,10 @@ extern mp *gfreduce_sqrt(gfreduce */*r*/, mp */*d*/, mp */*x*/); * @mp *x@ = some polynomial * * Returns: The trace of @x@. (%$\Tr(x)=x + x^2 + \cdots + x^{2^{m-1}}$% - * if %$x \in \gf{2^m}$%). + * if %$x \in \gf{2^m}$%). Since the trace is invariant under + * the Frobenius automorphism (i.e., %$\Tr(x)^2 = \Tr(x)$%), it + * must be an element of the base field, i.e., %$\gf{2}$%, and + * we only need a single bit to represent it. */ extern int gfreduce_trace(gfreduce */*r*/, mp */*x*/); @@ -153,6 +157,17 @@ extern mp *gfreduce_halftrace(gfreduce */*r*/, mp */*d*/, mp */*x*/); * @mp *x@ = some polynomial * * Returns: A polynomial @y@ such that %$y^2 + y = x$%, or null. + * + * Use: Solves quadratic equations in a field with characteristic 2. + * Suppose we have an equation %$y^2 + A y + B = 0$% where + * %$A \ne 0$%. (If %$A = 0$% then %$y = \sqrt{B}$% and you + * want @gfreduce_sqrt@ instead.) Use this function to solve + * %$z^2 + z = B/A^2$%; then set %$y = A z$%, since + * %$y^2 + y = A^2 z^2 + A^2 z = A^2 (z^2 + z) = B$% as + * required. + * + * The two roots are %$z$% and %$z + 1$%; this function always + * returns the one with zero scalar coefficient. */ extern mp *gfreduce_quadsolve(gfreduce */*r*/, mp */*d*/, mp */*x*/);