* 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
/* --- @mpbarrett_reduce@ --- *
*
- * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * Arguments: @const mpbarrett *mb@ = pointer to Barrett reduction context
* @mp *d@ = destination for result
* @mp *m@ = number to reduce
*
* Use: Performs an efficient modular reduction.
*/
-extern mp *mpbarrett_reduce(mpbarrett */*mb*/, mp */*d*/, mp */*m*/);
+extern mp *mpbarrett_reduce(const mpbarrett */*mb*/, mp */*d*/, mp */*m*/);
/* --- @mpbarrett_exp@ --- *
*
- * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * Arguments: @const mpbarrett *mb@ = pointer to Barrett reduction context
* @mp *d@ = fake destination
* @mp *a@ = base
* @mp *e@ = exponent
* Returns: Result, %$a^e \bmod m$%.
*/
-extern mp *mpbarrett_exp(mpbarrett */*mb*/, mp */*d*/, mp */*a*/, mp */*e*/);
+extern mp *mpbarrett_exp(const mpbarrett */*mb*/, mp */*d*/,
+ mp */*a*/, mp */*e*/);
/* --- @mpbarrett_mexp@ --- *
*
- * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * Arguments: @const mpbarrett *mb@ = pointer to Barrett reduction context
* @mp *d@ = fake destination
* @const mp_expfactor *f@ = pointer to array of factors
* @size_t n@ = number of factors supplied
* %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
*/
-extern mp *mpbarrett_mexp(mpbarrett */*mb*/, mp */*d*/,
+extern mp *mpbarrett_mexp(const mpbarrett */*mb*/, mp */*d*/,
const mp_expfactor */*f*/, size_t /*n*/);
/*----- That's all, folks -------------------------------------------------*/