X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/429bb008068e94288da5328132b35bcfa20771ee..7b0d1a63587f3cb1ae3bb8b248bbb1b82bdca7bd:/math/mp-arith.c

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