math/mp-arith.c: New function `mp_leastcongruent'.

Return the least representative of a congruence class not less than a
given lower bound.

diff --git a/math/mp-arith.c b/math/mp-arith.c
index 61780b0f44d928c6de5a16577847eafa9ff3ad75..470620efb0f023e3bdeb423fcbb3af984141e10b 100644 (file)
--- a/math/mp-arith.c
+++ b/math/mp-arith.c
@@ -667,6 +667,35 @@ mp *mp_odd(mp *d, mp *m, size_t *s)
   return (mp_lsr(d, m, ss));
 }
 
+/* --- @mp_leastcongruent@ --- *
+ *
+ * Arguments:  @mp *d@ = pointer to destination
+ *             @mp *b@ = lower bound
+ *             @mp *r@ = representative
+ *             @mp *m@ = modulus
+ *
+ * Returns:    The smallest integer %$x \equiv r \pmod{m}$% such that
+ *             %$x \ge b$%.
+ */
+
+mp *mp_leastcongruent(mp *d, mp *b, mp *r, mp *m)
+{
+  /* --- Strategy --- *
+   *
+   * Start by finding %$u \equiv b - r \pmod{m}$% with %$0 < u \le m$%.  Then
+   * %$b \le x = b + m - u < b + m$%, and %$x \equiv r \pmod{m}$% as
+   * required.
+   */
+
+  MP_COPY(b); MP_COPY(m);
+  d = mp_sub(d, b, r);
+  mp_div(0, &d, d, m);
+  if (MP_ZEROP(d)) { MP_DROP(d); d = MP_COPY(b); }
+  else { d = mp_sub(d, b, d); d = mp_add(d, d, m); }
+  MP_DROP(b); MP_DROP(m);
+  return (d);
+}
+
 /*----- Test rig ----------------------------------------------------------*/
 
 #ifdef TEST_RIG

diff --git a/math/mp.h b/math/mp.h
index ad4309e915ec89bea760fb707da4152ac12dda88..0434c28243b7b914913c5cadf9ea74c69d78f290 100644 (file)
--- a/math/mp.h
+++ b/math/mp.h
@@ -892,6 +892,19 @@ extern mp *mp_exp(mp */*d*/, mp */*a*/, mp */*e*/);
 
 extern mp *mp_odd(mp */*d*/, mp */*m*/, size_t */*s*/);
 
+/* --- @mp_leastcongruent@ --- *
+ *
+ * Arguments:  @mp *d@ = pointer to destination
+ *             @mp *b@ = lower bound
+ *             @mp *r@ = representative
+ *             @mp *m@ = modulus
+ *
+ * Returns:    The smallest integer %$x \equiv r \pmod{m}$% such that
+ *             %$x \ge b$%.
+ */
+
+extern mp *mp_leastcongruent(mp */*d*/, mp */*b*/, mp */*r*/, mp */*m*/);
+
 /*----- More advanced algorithms ------------------------------------------*/
 
 /* --- @mp_sqrt@ --- *