Merge branch '2.5.x'

[catacomb] / math / mp-arith.c

diff --git a/math/mp-arith.c b/math/mp-arith.c
index 61780b0..470620e 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