From: Mark Wooding <mdw@distorted.org.uk>
Date: Thu, 26 May 2016 08:26:09 +0000 (+0100)
Subject: math/mp-arith.c: New function `mp_leastcongruent'.
X-Git-Tag: 2.2.4~21
X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/commitdiff_plain/0c4f06c08a965b4c07e4075d974808a6a266d534

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 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
diff --git a/math/mp.h b/math/mp.h
index ad4309e9..0434c282 100644
--- 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@ --- *