X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a..f48fb6a6b1e0f29a45b42beae638ef9886312579:/math/mpbarrett.h

diff --git a/math/mpbarrett.h b/math/mpbarrett.h
index 40e0fe42..b3ab798e 100644
--- a/math/mpbarrett.h
+++ b/math/mpbarrett.h
@@ -40,6 +40,28 @@
  * modexp routine provided which uses Barrett reduction rather than
  * Montgomery reduction.  This is handy when you're working on indices in an
  * even-order cyclic group or something.
+ *
+ * In more detail: suppose that %$b^{k-1} \le m < b^k$%.  Let %$\mu = {}$%
+ * %$\lfloor b^{2k}/m \rfloor$%; %$\mu$% is a scaled approximation to the
+ * reciprocal %$1/m$%.  Now, suppose we're given some %$a$% with
+ * %$0 \le a < b^{2k}$%.  The first step is to calculate an approximation
+ * %$q = \lfloor \mu \lfloor a/b^{k-1} \rfloor/b^{k+1} \rfloor$% to the
+ * quotient %$a/m$%.  Then we have:
+ *
+ *	%$\lfloor a/m - a/b^{2k} - b^{k-1}/m + 1/b^{k+1} \rfloor \le {}$%
+ *		%$q \le \lfloor a/m \rfloor
+ *
+ * But by assumption %$a < b^{2k}$% and %$2^{k-1} \le m$% so
+ *
+ *	%$\lfloor a/m \rfloor - 2 \le q \le \lfloor a/m \rfloor$%
+ *
+ * Now we approximate the remainder by calculating %$r = a - q m$%.
+ * Certainly %$r \equiv a \pmod{m}$%; and
+ *
+ *	%$0 \le r \le (a - m \lfloor a/m \rfloor) + 2 m < 3 m$%.
+ *
+ * So the remainder can be fixed up with at most two conditional
+ * subtractions.
  */
 
 #ifndef CATACOMB_MPBARRETT_H