[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sun Jan 19 15:20:13 UTC 2014
details: /var/hg/gmp/rev/8ccc38f90c0c
changeset: 16229:8ccc38f90c0c
user: Torbjorn Granlund <tege at gmplib.org>
date: Sun Jan 19 16:18:21 2014 +0100
description:
Reorder NEWS item more logically.
details: /var/hg/gmp/rev/1aab49d7b882
changeset: 16230:1aab49d7b882
user: Torbjorn Granlund <tege at gmplib.org>
date: Sun Jan 19 16:20:10 2014 +0100
description:
Rename mpn_sec_minvert => mpn_sec_invert, many files affected.
diffstat:
AUTHORS | 2 +-
ChangeLog | 3 +
NEWS | 18 ++--
configure.ac | 2 +-
doc/gmp.texi | 6 +-
gmp-h.in | 8 +-
mpn/generic/sec_invert.c | 180 ++++++++++++++++++++++++++++++++++++++++++++++
mpn/generic/sec_minvert.c | 180 ----------------------------------------------
tests/mpn/t-minvert.c | 11 +-
tune/common.c | 4 +-
tune/speed.c | 2 +-
tune/speed.h | 2 +-
12 files changed, 210 insertions(+), 208 deletions(-)
diffs (truncated from 549 to 300 lines):
diff -r b2faa9fedbdb -r 1aab49d7b882 AUTHORS
--- a/AUTHORS Sun Jan 19 14:46:09 2014 +0100
+++ b/AUTHORS Sun Jan 19 16:20:10 2014 +0100
@@ -40,7 +40,7 @@
matrix22_mul1_inverse_vector.c,
toom_interpolate_7pts, mulmod_bnm1.c, dcpi1_bdiv_qr.c,
dcpi1_bdiv_q.c, sbpi1_bdiv_qr.c, sbpi1_bdiv_q.c,
- sec_minvert.c,
+ sec_invert.c,
toom_eval_dgr3_pm1.c, toom_eval_dgr3_pm2.c,
toom_eval_pm1.c, toom_eval_pm2.c, toom_eval_pm2exp.c,
divexact.c, mod_1_1.c, div_qr_2.c,
diff -r b2faa9fedbdb -r 1aab49d7b882 ChangeLog
--- a/ChangeLog Sun Jan 19 14:46:09 2014 +0100
+++ b/ChangeLog Sun Jan 19 16:20:10 2014 +0100
@@ -1,5 +1,8 @@
2014-01-19 Torbjorn Granlund <tege at gmplib.org>
+ * Rename mpn_sec_minvert => mpn_sec_invert, many files affected.
+ * mpn/generic/sec_invert.c: New name for sec_minvert.c.
+
* doc/gmp.texi: Undocument mpz_array_init.
* acinclude.m4 (GMP_C_STDARG): Comment out.
diff -r b2faa9fedbdb -r 1aab49d7b882 NEWS
--- a/NEWS Sun Jan 19 14:46:09 2014 +0100
+++ b/NEWS Sun Jan 19 16:20:10 2014 +0100
@@ -37,20 +37,20 @@
* Support for ARM64 alias Aarch64 alias ARMv8.
- * New functions mpn_cnd_add_n and mpn_cnd_sub_n. Side-channel silent
+ * New public functions mpn_sec_mul and mpn_sec_sqr, implementing side-channel
+ silent multiplication and squaring.
+
+ * New public functions mpn_sec_div_qr and mpn_sec_div_r, implementing
+ side-channel silent division.
+
+ * New public functions mpn_cnd_add_n and mpn_cnd_sub_n. Side-channel silent
conditional addition and subtraction.
- * New function mpn_sec_powm, implementing side-channel silent modexp.
+ * New public function mpn_sec_powm, implementing side-channel silent modexp.
- * New function mpn_sec_minvert, implementing side-channel silent
+ * New public function mpn_sec_invert, implementing side-channel silent
modular inversion.
- * New functions mpn_sec_mul and mpn_sec_sqr, implementing side-channel silent
- multiplication and squaring.
-
- * New functions mpn_sec_div_qr and mpn_sec_div_r, implementing side-channel
- silent division.
-
* Better support for applications which use the mpz_t type, but nevertheless
need to call some of the lower-level mpn functions. See the documentation
for mpz_limbs_read and related functions.
diff -r b2faa9fedbdb -r 1aab49d7b882 configure.ac
--- a/configure.ac Sun Jan 19 14:46:09 2014 +0100
+++ b/configure.ac Sun Jan 19 16:20:10 2014 +0100
@@ -2835,7 +2835,7 @@
bdiv_q bdiv_qr broot brootinv bsqrt bsqrtinv \
divexact bdiv_dbm1c redc_1 redc_2 redc_n powm powlo sec_powm \
sec_mul sec_sqr sec_div_qr sec_div_r sec_pi1_div_qr sec_pi1_div_r \
- sec_add_1 sec_sub_1 sec_minvert \
+ sec_add_1 sec_sub_1 sec_invert \
trialdiv remove \
and_n andn_n nand_n ior_n iorn_n nior_n xor_n xnor_n \
copyi copyd zero sec_tabselect \
diff -r b2faa9fedbdb -r 1aab49d7b882 doc/gmp.texi
--- a/doc/gmp.texi Sun Jan 19 14:46:09 2014 +0100
+++ b/doc/gmp.texi Sun Jan 19 16:20:10 2014 +0100
@@ -5783,8 +5783,8 @@
@var{dn})} limbs to be passed in the @var{tp} parameter.
@end deftypefun
- at deftypefun int mpn_sec_minvert (mp_limb_t *@var{rp}, mp_limb_t *@var{ap}, const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_bitcnt_t @var{nbcnt}, mp_limb_t *@var{tp})
- at deftypefunx mp_size_t mpn_sec_minvert_itch (mp_size_t @var{n})
+ at deftypefun int mpn_sec_invert (mp_limb_t *@var{rp}, mp_limb_t *@var{ap}, const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_bitcnt_t @var{nbcnt}, mp_limb_t *@var{tp})
+ at deftypefunx mp_size_t mpn_sec_invert_itch (mp_size_t @var{n})
Set @var{R} to @m{@var{A}^{-1} \bmod @var{M}, the inverse of @var{A} modulo
@var{M}}, where @var{R} = @{@var{rp}, at var{n}@}, @var{A} = @{@var{ap}, at var{n}@},
and @var{M} = @{@var{mp}, at var{n}@}. @strong{This function's interface is
@@ -5799,7 +5799,7 @@
@times{} @var{n} @times{} GMP_NUMB_BITS}, but a smaller value might improve
performance if @var{M} or @var{A} are known to have leading zero bits.
-This function requires scratch space of @code{mpn_sec_minvert_itch(@var{n})}
+This function requires scratch space of @code{mpn_sec_invert_itch(@var{n})}
limbs to be passed in the @var{tp} parameter.
@end deftypefun
diff -r b2faa9fedbdb -r 1aab49d7b882 gmp-h.in
--- a/gmp-h.in Sun Jan 19 14:46:09 2014 +0100
+++ b/gmp-h.in Sun Jan 19 16:20:10 2014 +0100
@@ -1664,10 +1664,10 @@
#define mpn_sec_div_r_itch __MPN(sec_div_r_itch)
__GMP_DECLSPEC mp_size_t mpn_sec_div_r_itch (mp_size_t, mp_size_t) __GMP_ATTRIBUTE_PURE;
-#define mpn_sec_minvert __MPN(sec_minvert)
-__GMP_DECLSPEC int mpn_sec_minvert (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_bitcnt_t, mp_ptr);
-#define mpn_sec_minvert_itch __MPN(sec_minvert_itch)
-__GMP_DECLSPEC mp_size_t mpn_sec_minvert_itch (mp_size_t) __GMP_ATTRIBUTE_PURE;
+#define mpn_sec_invert __MPN(sec_invert)
+__GMP_DECLSPEC int mpn_sec_invert (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_bitcnt_t, mp_ptr);
+#define mpn_sec_invert_itch __MPN(sec_invert_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_invert_itch (mp_size_t) __GMP_ATTRIBUTE_PURE;
/**************** mpz inlines ****************/
diff -r b2faa9fedbdb -r 1aab49d7b882 mpn/generic/sec_invert.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/sec_invert.c Sun Jan 19 16:20:10 2014 +0100
@@ -0,0 +1,180 @@
+/* mpn_sec_invert
+
+ Contributed to the GNU project by Niels Möller
+
+Copyright 2013 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+static mp_size_t
+mpn_cnd_neg_itch (mp_size_t n)
+{
+ return n;
+}
+
+/* FIXME: Ought to return carry */
+static void
+mpn_cnd_neg (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n,
+ mp_ptr scratch)
+{
+ mpn_lshift (scratch, ap, n, 1);
+ mpn_cnd_sub_n (cnd, rp, ap, scratch, n);
+}
+
+static void
+mpn_cnd_swap (int cnd, volatile mp_limb_t *ap, volatile mp_limb_t *bp,
+ mp_size_t n)
+{
+ volatile mp_limb_t mask = - (mp_limb_t) (cnd != 0);
+ mp_size_t i;
+ for (i = 0; i < n; i++)
+ {
+ mp_limb_t a, b, t;
+ a = ap[i];
+ b = bp[i];
+ t = (a ^ b) & mask;
+ ap[i] = a ^ t;
+ bp[i] = b ^ t;
+ }
+}
+
+static int
+mpn_sec_eq_ui (mp_srcptr ap, mp_size_t n, mp_limb_t b)
+{
+ mp_limb_t d;
+ ASSERT (n > 0);
+
+ d = ap[0] ^ b;
+
+ while (--n > 0)
+ d |= ap[n];
+
+ return d == 0;
+}
+
+mp_size_t
+mpn_sec_invert_itch (mp_size_t n)
+{
+ return 4*n;
+}
+
+/* Compute V <-- A^{-1} (mod M), in data-independent time. M must be
+ odd. Returns 1 on success, and 0 on failure (i.e., if gcd (A, m) !=
+ 1). Inputs and outputs of size n, and no overlap allowed. The {ap,
+ n} area is destroyed. For arbitrary inputs, bit_size should be
+ 2*n*GMP_NUMB_BITS, but if A or M are known to be smaller, e.g., if
+ M = 2^521 - 1 and A < M, bit_size can be any bound on the sum of
+ the bit sizes of A and M. */
+int
+mpn_sec_invert (mp_ptr vp, mp_ptr ap, mp_srcptr mp,
+ mp_size_t n, mp_bitcnt_t bit_size,
+ mp_ptr scratch)
+{
+ ASSERT (n > 0);
+ ASSERT (bit_size > 0);
+ ASSERT (mp[0] & 1);
+ ASSERT (! MPN_OVERLAP_P (ap, n, vp, n));
+#define bp (scratch + n)
+#define up (scratch + 2*n)
+#define m1hp (scratch + 3*n)
+
+ /* Maintain
+
+ a = u * orig_a (mod m)
+ b = v * orig_a (mod m)
+
+ and b odd at all times. Initially,
+
+ a = a_orig, u = 1
+ b = m, v = 0
+ */
+
+
+ up[0] = 1;
+ mpn_zero (up+1, n - 1);
+ mpn_copyi (bp, mp, n);
+ mpn_zero (vp, n);
+
+ ASSERT_CARRY (mpn_rshift (m1hp, mp, n, 1));
+ ASSERT_NOCARRY (mpn_sec_add_1 (m1hp, m1hp, n, 1, scratch));
+
+ while (bit_size-- > 0)
+ {
+ mp_limb_t odd, swap, cy;
+
+ /* Always maintain b odd. The logic of the iteration is as
+ follows. For a, b:
+
+ odd = a & 1
+ a -= odd * b
+ if (underflow from a-b)
+ {
+ b += a, assigns old a
+ a = B^n-a
+ }
+
+ a /= 2
+
+ For u, v:
+
+ if (underflow from a - b)
+ swap u, v
+ u -= odd * v
+ if (underflow from u - v)
+ u += m
+
+ u /= 2
+ if (a one bit was shifted out)
+ u += (m+1)/2
+
+ As long as a > 0, the quantity
+
+ (bitsize of a) + (bitsize of b)
+
+ is reduced by at least one bit per iteration, hence after (bit_size of
+ orig_a) + (bit_size of m) - 1 iterations we surely have a = 0. Then b
+ = gcd(orig_a, m) and if b = 1 then also v = orig_a^{-1} (mod m).
+ */
+
+ ASSERT (bp[0] & 1);
+ odd = ap[0] & 1;
+
+ swap = mpn_cnd_sub_n (odd, ap, ap, bp, n);
+ mpn_cnd_add_n (swap, bp, bp, ap, n);
+ mpn_cnd_neg (swap, ap, ap, n, scratch);
+
+ mpn_cnd_swap (swap, up, vp, n);
+ cy = mpn_cnd_sub_n (odd, up, up, vp, n);
+ cy -= mpn_cnd_add_n (cy, up, up, mp, n);
+ ASSERT (cy == 0);
+
+ cy = mpn_rshift (ap, ap, n, 1);
+ ASSERT (cy == 0);
+ cy = mpn_rshift (up, up, n, 1);
+ cy = mpn_cnd_add_n (cy, up, up, m1hp, n);
+ ASSERT (cy == 0);
+ }
+ /* Should be all zeros, but check only extreme limbs */
+ ASSERT ( (ap[0] | ap[n-1]) == 0);
+ /* Check if indeed gcd == 1. */
+ return mpn_sec_eq_ui (bp, n, 1);
+#undef bp
+#undef up
+#undef m1hp
+}
diff -r b2faa9fedbdb -r 1aab49d7b882 mpn/generic/sec_minvert.c
--- a/mpn/generic/sec_minvert.c Sun Jan 19 14:46:09 2014 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,180 +0,0 @@
-/* mpn_sec_minvert
-
More information about the gmp-commit
mailing list