[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