X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/5a19b5dfdde3f31feef4443442cc1c5c0bad6484..HEAD:/math/gfreduce.c

diff --git a/math/gfreduce.c b/math/gfreduce.c
index 83ffeb10..f29c1048 100644
--- a/math/gfreduce.c
+++ b/math/gfreduce.c
@@ -297,7 +297,7 @@ void gfreduce_destroy(gfreduce *r)
 
 /* --- @gfreduce_dump@ --- *
  *
- * Arguments:	@gfreduce *r@ = structure to dump
+ * Arguments:	@const gfreduce *r@ = structure to dump
  *		@FILE *fp@ = file to dump on
  *
  * Returns:	---
@@ -305,7 +305,7 @@ void gfreduce_destroy(gfreduce *r)
  * Use:		Dumps a reduction context.
  */
 
-void gfreduce_dump(gfreduce *r, FILE *fp)
+void gfreduce_dump(const gfreduce *r, FILE *fp)
 {
   size_t i;
 
@@ -327,7 +327,7 @@ void gfreduce_dump(gfreduce *r, FILE *fp)
 
 /* --- @gfreduce_do@ --- *
  *
- * Arguments:	@gfreduce *r@ = reduction context
+ * Arguments:	@const gfreduce *r@ = reduction context
  *		@mp *d@ = destination
  *		@mp *x@ = source
  *
@@ -350,7 +350,7 @@ static void run(const gfreduce_instr *i, const gfreduce_instr *il,
   }
 }
 
-mp *gfreduce_do(gfreduce *r, mp *d, mp *x)
+mp *gfreduce_do(const gfreduce *r, mp *d, mp *x)
 {
   mpw *v, *vl;
   const gfreduce_instr *il;
@@ -392,14 +392,14 @@ mp *gfreduce_do(gfreduce *r, mp *d, mp *x)
 
 /* --- @gfreduce_sqrt@ --- *
  *
- * Arguments:	@gfreduce *r@ = pointer to reduction context
+ * Arguments:	@const gfreduce *r@ = pointer to reduction context
  *		@mp *d@ = destination
  *		@mp *x@ = some polynomial
  *
  * Returns:	The square root of @x@ modulo @r->p@, or null.
  */
 
-mp *gfreduce_sqrt(gfreduce *r, mp *d, mp *x)
+mp *gfreduce_sqrt(const gfreduce *r, mp *d, mp *x)
 {
   mp *y = MP_COPY(x);
   mp *z, *spare = MP_NEW;
@@ -430,7 +430,7 @@ mp *gfreduce_sqrt(gfreduce *r, mp *d, mp *x)
 
 /* --- @gfreduce_trace@ --- *
  *
- * Arguments:	@gfreduce *r@ = pointer to reduction context
+ * Arguments:	@const gfreduce *r@ = pointer to reduction context
  *		@mp *x@ = some polynomial
  *
  * Returns:	The trace of @x@. (%$\Tr(x)=x + x^2 + \cdots + x^{2^{m-1}}$%
@@ -440,7 +440,7 @@ mp *gfreduce_sqrt(gfreduce *r, mp *d, mp *x)
  *		we only need a single bit to represent it.
  */
 
-int gfreduce_trace(gfreduce *r, mp *x)
+int gfreduce_trace(const gfreduce *r, mp *x)
 {
   mp *y = MP_COPY(x);
   mp *spare = MP_NEW;
@@ -462,7 +462,7 @@ int gfreduce_trace(gfreduce *r, mp *x)
 
 /* --- @gfreduce_halftrace@ --- *
  *
- * Arguments:	@gfreduce *r@ = pointer to reduction context
+ * Arguments:	@const gfreduce *r@ = pointer to reduction context
  *		@mp *d@ = destination
  *		@mp *x@ = some polynomial
  *
@@ -471,7 +471,7 @@ int gfreduce_trace(gfreduce *r, mp *x)
  *		if %$x \in \gf{2^m}$% with %$m$% odd).
  */
 
-mp *gfreduce_halftrace(gfreduce *r, mp *d, mp *x)
+mp *gfreduce_halftrace(const gfreduce *r, mp *d, mp *x)
 {
   mp *y = MP_COPY(x);
   mp *spare = MP_NEW;
@@ -494,7 +494,7 @@ mp *gfreduce_halftrace(gfreduce *r, mp *d, mp *x)
 
 /* --- @gfreduce_quadsolve@ --- *
  *
- * Arguments:	@gfreduce *r@ = pointer to reduction context
+ * Arguments:	@const gfreduce *r@ = pointer to reduction context
  *		@mp *d@ = destination
  *		@mp *x@ = some polynomial
  *
@@ -512,7 +512,7 @@ mp *gfreduce_halftrace(gfreduce *r, mp *d, mp *x)
  *		returns the one with zero scalar coefficient.
  */
 
-mp *gfreduce_quadsolve(gfreduce *r, mp *d, mp *x)
+mp *gfreduce_quadsolve(const gfreduce *r, mp *d, mp *x)
 {
   unsigned long m = mp_bits(r->p) - 1;
   mp *t;
@@ -554,12 +554,16 @@ mp *gfreduce_quadsolve(gfreduce *r, mp *d, mp *x)
      *
      * Choose %$\rho \inr \gf{2^m}$% with %$\Tr(\rho) = 1$%.  Let
      * %$z = \sum_{0\le i<m} \rho^{2^i} \sum_{0\le j<i} x^{2^j} = {}$%
+     * %$\sum_{1\le i<m} \rho^{2^i} (x + \sum_{1\le j<i} x^{2^j} = {}$%
      * %$\rho^2 x + \rho^4 (x + x^2) + \rho^8 (x + x^2 + x^4) + \cdots + {}$%
      * %$\rho^{2^{m-1}} (x + x^2 + x^{2^{m-2}})$%.  Then %$z^2 = {}$%
      * %$\sum_{0\le i<m} \rho^{2^{i+1}} \sum_{0\le j<i} x^{2^{j+1}} = {}$%
-     * %$\sum_{1\le i\le m} \rho^{2^i} \sum_{1\le j\le i} x^{2^j}$% and,
-     * somewhat miraculously, %$z^2 + z = \sum_{0\le i<m} \rho^{2^i} x + {}$%
-     * %$\rho \sum_{1\le i<m} x^{2^i} = x \Tr(\rho) + \rho \Tr(x)$%.  Again,
+     * %$\sum_{1\le i\le m} \rho^{2^i} \sum_{1\le j<i} x^{2^j} = {}$%
+     * %$\sum_{1\le i<m} \rho^{2^i} \sum_{1\le j<i} x^{2^j} + {}$%
+     * %$\rho^{2^m} \sum_{1\le j<m} x^{2^j}$%; and, somewhat miraculously,
+     * %$z^2 + z = \sum_{1\le i<m} \rho^{2^i} x + {}$%
+     * %$\rho \sum_{1\le i<m} x^{2^i} = x (\Tr(\rho) + \rho) + {}$%
+     * %$\rho (\Tr(x) + x) = x \Tr(\rho) + \rho \Tr(x)$%.  Again,
      * this gives us the root we want whenever %$\Tr(x) = 0$%.
      *
      * The loop below calculates %$w = \Tr(\rho)$% and %$z$% simultaneously,
@@ -616,7 +620,7 @@ mp *gfreduce_quadsolve(gfreduce *r, mp *d, mp *x)
 
 /* --- @gfreduce_exp@ --- *
  *
- * Arguments:	@gfreduce *gr@ = pointer to reduction context
+ * Arguments:	@const gfreduce *gr@ = pointer to reduction context
  *		@mp *d@ = fake destination
  *		@mp *a@ = base
  *		@mp *e@ = exponent
@@ -624,7 +628,7 @@ mp *gfreduce_quadsolve(gfreduce *r, mp *d, mp *x)
  * Returns:	Result, %$a^e \bmod m$%.
  */
 
-mp *gfreduce_exp(gfreduce *gr, mp *d, mp *a, mp *e)
+mp *gfreduce_exp(const gfreduce *gr, mp *d, mp *a, mp *e)
 {
   mp *x = MP_ONE;
   mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;