[Gmp-commit] /var/hg/gmp: mpn_sec_powm: Replace exponent limb count argument ...

mercurial at gmplib.org mercurial at gmplib.org
Tue Feb 11 20:49:36 UTC 2014


details:   /var/hg/gmp/rev/08416a6e9ec4
changeset: 16294:08416a6e9ec4
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Tue Feb 11 21:22:07 2014 +0100
description:
mpn_sec_powm: Replace exponent limb count argument with a bit count.

diffstat:

 ChangeLog              |  14 ++++++++++++++
 doc/gmp.texi           |  14 ++++++--------
 gmp-h.in               |   4 ++--
 mpn/generic/sec_powm.c |  11 ++++-------
 mpz/powm_sec.c         |   4 ++--
 tune/tuneup.c          |  11 +++--------
 6 files changed, 31 insertions(+), 27 deletions(-)

diffs (174 lines):

diff -r 1a3494e94d96 -r 08416a6e9ec4 ChangeLog
--- a/ChangeLog	Mon Feb 10 21:41:40 2014 +0100
+++ b/ChangeLog	Tue Feb 11 21:22:07 2014 +0100
@@ -1,3 +1,17 @@
+2014-02-11  Niels Möller  <nisse at lysator.liu.se>
+
+	* doc/gmp.texi (Low-level Functions): Updated mpn_sec_powm docs.
+
+	* mpn/generic/sec_powm.c (mpn_sec_powm): Replaced exponent limb
+	count argument by bit count. Don't leak high exponent bits, and
+	drop the requirement that the most significant exponent limb is
+	non-zero.
+	(mpn_sec_powm_itch): Analogous interface change.
+	* gmp-h.in: Updated prototypes.
+	* mpz/powm_sec.c (mpz_powm_sec): Update mpn_sec_powm* calls.
+	* tune/tuneup.c (tune_powm_sec): Likewise. Also deleted code
+	fiddling with the high exponent bits.
+
 2014-02-10 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* mini-gmp/tests/t-limbs.c: New test for mpz_limbs_*.
diff -r 1a3494e94d96 -r 08416a6e9ec4 doc/gmp.texi
--- a/doc/gmp.texi	Mon Feb 10 21:41:40 2014 +0100
+++ b/doc/gmp.texi	Tue Feb 11 21:22:07 2014 +0100
@@ -5743,20 +5743,18 @@
 @end deftypefun
 
 
- at deftypefun void mpn_sec_powm (mp_limb_t *@var{rp}, const mp_limb_t *@var{bp}, mp_size_t @var{bn}, const mp_limb_t *@var{ep}, mp_size_t @var{en},  const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_limb_t *@var{tp})
- at deftypefunx mp_size_t mpn_sec_powm_itch (mp_size_t @var{bn}, mp_size_t @var{en}, size_t @var{n})
+ at deftypefun void mpn_sec_powm (mp_limb_t *@var{rp}, const mp_limb_t *@var{bp}, mp_size_t @var{bn}, const mp_limb_t *@var{ep}, mp_bitcnt_t @var{ebits},  const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_limb_t *@var{tp})
+ at deftypefunx mp_size_t mpn_sec_powm_itch (mp_size_t @var{bn}, mp_bitcnt_t @var{ebits}, size_t @var{n})
 Set @var{R} to @m{B^E \bmod @var{M}, (@var{B} raised to @var{E}) modulo
 @var{M}}, where @var{R} = @{@var{rp}, at var{n}@}, @var{M} = @{@var{mp}, at var{n}@},
-and @var{E} = @{@var{ep}, at var{en}@}.
-
-It is required that @math{@var{B} > 0}, that @math{@var{E} > 0} specifically
-with @m{@var{ep}[@var{en}-1] @neq 0, @var{ep}[@var{en}-1] != 0}, and that
- at math{@var{M} > 0} is odd.
+and @var{E} consists of the least @var{ebits} in the area pointed to by @var{ep}.
+
+It is required that @math{@var{B} > 0}, and that @math{@var{M} > 0} is odd.
 
 No overlapping between @var{R} and the input operands is allowed.
 
 This function requires scratch space of @code{mpn_sec_powm_itch(@var{bn},
- at var{en}, @var{n})} limbs to be passed in the @var{tp} parameter.  The scratch
+ at var{ebits}, @var{n})} limbs to be passed in the @var{tp} parameter.  The scratch
 space requirements are guaranteed to increase monotonously in the operand
 sizes.
 @end deftypefun
diff -r 1a3494e94d96 -r 08416a6e9ec4 gmp-h.in
--- a/gmp-h.in	Mon Feb 10 21:41:40 2014 +0100
+++ b/gmp-h.in	Tue Feb 11 21:22:07 2014 +0100
@@ -1659,9 +1659,9 @@
 __GMP_DECLSPEC mp_size_t mpn_sec_sqr_itch (mp_size_t) __GMP_ATTRIBUTE_PURE;
 
 #define mpn_sec_powm __MPN(sec_powm)
-__GMP_DECLSPEC void mpn_sec_powm (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+__GMP_DECLSPEC void mpn_sec_powm (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_bitcnt_t, mp_srcptr, mp_size_t, mp_ptr);
 #define mpn_sec_powm_itch __MPN(sec_powm_itch)
-__GMP_DECLSPEC mp_size_t mpn_sec_powm_itch (mp_size_t, mp_size_t, mp_size_t) __GMP_ATTRIBUTE_PURE;
+__GMP_DECLSPEC mp_size_t mpn_sec_powm_itch (mp_size_t, mp_bitcnt_t, mp_size_t) __GMP_ATTRIBUTE_PURE;
 
 #define mpn_sec_tabselect __MPN(sec_tabselect)
 __GMP_DECLSPEC void mpn_sec_tabselect (volatile mp_limb_t *, volatile const mp_limb_t *, mp_size_t, mp_size_t, mp_size_t);
diff -r 1a3494e94d96 -r 08416a6e9ec4 mpn/generic/sec_powm.c
--- a/mpn/generic/sec_powm.c	Mon Feb 10 21:41:40 2014 +0100
+++ b/mpn/generic/sec_powm.c	Tue Feb 11 21:22:07 2014 +0100
@@ -256,25 +256,22 @@
    Uses scratch space at tp as defined by mpn_sec_powm_itch.  */
 void
 mpn_sec_powm (mp_ptr rp, mp_srcptr bp, mp_size_t bn,
-	      mp_srcptr ep, mp_size_t en,
+	      mp_srcptr ep, mp_bitcnt_t ebi,
 	      mp_srcptr mp, mp_size_t n, mp_ptr tp)
 {
   mp_limb_t ip[2], *mip;
-  mp_bitcnt_t ebi;
   int windowsize, this_windowsize;
   mp_limb_t expbits;
   mp_ptr pp, this_pp;
   long i;
   int cnd;
 
-  ASSERT (en > 0 && ep[en - 1] != 0);
+  ASSERT (ebi > 0);
   ASSERT (n >= 1 && ((mp[0] & 1) != 0));
   /* The code works for bn = 0, but the defined scratch space is 2 limbs
      greater than we supply, when converting 1 to redc form .  */
   ASSERT (bn >= 1);
 
-  MPN_SIZEINBASE_2EXP(ebi, ep, en, 1);
-
   windowsize = win_size (ebi);
 
 #if WANT_REDC_2
@@ -415,7 +412,7 @@
 }
 
 mp_size_t
-mpn_sec_powm_itch (mp_size_t bn, mp_size_t en, mp_size_t n)
+mpn_sec_powm_itch (mp_size_t bn, mp_bitcnt_t eb, mp_size_t n)
 {
   int windowsize;
   mp_size_t redcify_itch, itch;
@@ -425,7 +422,7 @@
      is 3n or 4n depending on if we use mpn_local_sqr or a native
      mpn_sqr_basecase.  We assume 4n always for now.) */
 
-  windowsize = win_size (en * GMP_NUMB_BITS); /* slight over-estimate of exp */
+  windowsize = win_size (eb);
 
   /* The 2n term is due to pp[0] and pp[1] at the time of the 2nd redcify call,
      the (bn + n) term is due to redcify's own usage, and the rest is due to
diff -r 1a3494e94d96 -r 08416a6e9ec4 mpz/powm_sec.c
--- a/mpz/powm_sec.c	Mon Feb 10 21:41:40 2014 +0100
+++ b/mpz/powm_sec.c	Tue Feb 11 21:22:07 2014 +0100
@@ -76,14 +76,14 @@
     }
 
   TMP_MARK;
-  tp = TMP_ALLOC_LIMBS (n + mpn_sec_powm_itch (bn, en, n));
+  tp = TMP_ALLOC_LIMBS (n + mpn_sec_powm_itch (bn, en * GMP_NUMB_BITS, n));
 
   rp = tp;  tp += n;
 
   bp = PTR(b);
   ep = PTR(e);
 
-  mpn_sec_powm (rp, bp, bn, ep, en, mp, n, tp);
+  mpn_sec_powm (rp, bp, bn, ep, en * GMP_NUMB_BITS, mp, n, tp);
 
   rn = n;
 
diff -r 1a3494e94d96 -r 08416a6e9ec4 tune/tuneup.c
--- a/tune/tuneup.c	Mon Feb 10 21:41:40 2014 +0100
+++ b/tune/tuneup.c	Tue Feb 11 21:22:07 2014 +0100
@@ -1881,7 +1881,7 @@
   k = 1;
 
   winsize = 10;			/* the itch function needs this */
-  itch = mpn_sec_powm_itch (n_max, n_max, n_max);
+  itch = mpn_sec_powm_itch (n_max, n_max * GMP_NUMB_BITS, n_max);
 
   rp = TMP_ALLOC_LIMBS (n_max);
   bp = TMP_ALLOC_LIMBS (n_max);
@@ -1923,16 +1923,11 @@
       for (i = 0; i < n; i++)
 	ep[i] = ~CNST_LIMB(0);
 
-      /* Truncate E to be exactly nbits large.  */
-      if (nbits % GMP_NUMB_BITS != 0)
-	mpn_rshift (ep, ep, n, GMP_NUMB_BITS - nbits % GMP_NUMB_BITS);
-      ep[n - 1] |= CNST_LIMB(1) << (nbits - 1) % GMP_NUMB_BITS;
-
       winsize = k;
       for (i = 0; i < n_measurements; i++)
 	{
 	  speed_starttime ();
-	  mpn_sec_powm (rp, bp, n, ep, n, mp, n, tp);
+	  mpn_sec_powm (rp, bp, n, ep, nbits, mp, n, tp);
 	  ttab[i] = speed_endtime ();
 	}
       tk = median (ttab, n_measurements);
@@ -1942,7 +1937,7 @@
       for (i = 0; i < n_measurements; i++)
 	{
 	  speed_starttime ();
-	  mpn_sec_powm (rp, bp, n, ep, n, mp, n, tp);
+	  mpn_sec_powm (rp, bp, n, ep, nbits, mp, n, tp);
 	  ttab[i] = speed_endtime ();
 	}
       tkp1 = median (ttab, n_measurements);


More information about the gmp-commit mailing list