+#ifdef BERKELEY_MP
+#include "mp.h"
+#endif
+
+
+/* set c <- (a*b)/R^n mod m c has to have at least (2n) allocated limbs */
+static void
+#if __STDC__
+mpz_redc (mpz_ptr c, mpz_srcptr a, mpz_srcptr b, mpz_srcptr m, mp_limb_t Nprim)
+#else
+mpz_redc (c, a, b, m, Nprim)
+ mpz_ptr c;
+ mpz_srcptr a;
+ mpz_srcptr b;
+ mpz_srcptr m;
+ mp_limb_t Nprim;
+#endif
+{
+ mp_ptr cp, mp = PTR (m);
+ mp_limb_t cy, cout = 0;
+ mp_limb_t q;
+ size_t j, n = ABSIZ (m);
+
+ ASSERT (ALLOC (c) >= 2 * n);
+
+ mpz_mul (c, a, b);
+ cp = PTR (c);
+ j = ABSIZ (c);
+ MPN_ZERO (cp + j, 2 * n - j);
+ for (j = 0; j < n; j++)
+ {
+ q = cp[0] * Nprim;
+ cy = mpn_addmul_1 (cp, mp, n, q);
+ cout += mpn_add_1 (cp + n, cp + n, n - j, cy);
+ cp++;
+ }
+ cp -= n;
+ if (cout)
+ {
+ cy = cout - mpn_sub_n (cp, cp + n, mp, n);
+ while (cy)
+ cy -= mpn_sub_n (cp, cp, mp, n);
+ }
+ else
+ MPN_COPY (cp, cp + n, n);
+ MPN_NORMALIZE (cp, n);
+ SIZ (c) = SIZ (c) < 0 ? -n : n;
+}