[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