[Gmp-commit] /var/hg/gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue May 25 19:11:39 UTC 2021
details: /var/hg/gmp/rev/81cfab60f824
changeset: 18218:81cfab60f824
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue May 25 19:48:50 2021 +0200
description:
mpn/generic/sec_powm.c (sec_binvert_limb): New static function.
details: /var/hg/gmp/rev/038a3f72d228
changeset: 18219:038a3f72d228
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue May 25 21:07:11 2021 +0200
description:
mpn/generic/{sec_,}powm.c (win_size): Remove the unused value from array.
details: /var/hg/gmp/rev/1b45731027e8
changeset: 18220:1b45731027e8
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue May 25 21:11:14 2021 +0200
description:
ChangeLog
diffstat:
ChangeLog | 7 ++++
mpn/generic/powm.c | 6 ++--
mpn/generic/sec_powm.c | 73 +++++++++++++++++++++++++++++++++++++++++--------
3 files changed, 70 insertions(+), 16 deletions(-)
diffs (143 lines):
diff -r 6e3c30a9f38f -r 1b45731027e8 ChangeLog
--- a/ChangeLog Sat May 15 08:57:53 2021 +0200
+++ b/ChangeLog Tue May 25 21:11:14 2021 +0200
@@ -1,3 +1,10 @@
+2021-05-25 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpn/generic/sec_powm.c (sec_binvert_limb): New static function.
+
+ * mpn/generic/powm.c (win_size): Remove the unused value from array.
+ * mpn/generic/sec_powm.c (win_size): Likewise.
+
2021-05-08 Marc Glisse <marc.glisse at inria.fr>
* doc/gmp.texi: Mention shifts in bit manipulation.
diff -r 6e3c30a9f38f -r 1b45731027e8 mpn/generic/powm.c
--- a/mpn/generic/powm.c Sat May 15 08:57:53 2021 +0200
+++ b/mpn/generic/powm.c Tue May 25 21:11:14 2021 +0200
@@ -6,7 +6,7 @@
SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
-Copyright 2007-2012, 2019, 2020 Free Software Foundation, Inc.
+Copyright 2007-2012, 2019-2021 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -163,8 +163,8 @@
win_size (mp_bitcnt_t eb)
{
int k;
- static mp_bitcnt_t x[] = {0,7,25,81,241,673,1793,4609,11521,28161,~(mp_bitcnt_t)0};
- for (k = 1; eb > x[k]; k++)
+ static mp_bitcnt_t x[] = {7,25,81,241,673,1793,4609,11521,28161,~(mp_bitcnt_t)0};
+ for (k = 0; eb > x[k++]; )
;
return k;
}
diff -r 6e3c30a9f38f -r 1b45731027e8 mpn/generic/sec_powm.c
--- a/mpn/generic/sec_powm.c Sat May 15 08:57:53 2021 +0200
+++ b/mpn/generic/sec_powm.c Tue May 25 21:11:14 2021 +0200
@@ -3,7 +3,7 @@
Contributed to the GNU project by Torbjörn Granlund.
-Copyright 2007-2009, 2011-2014, 2018-2019 Free Software Foundation, Inc.
+Copyright 2007-2009, 2011-2014, 2018-2019, 2021 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -185,8 +185,8 @@
We require that x[k] >= k, then it follows that enb > x[k-1] >=
k-1, which implies k <= enb.
*/
- static const mp_bitcnt_t x[] = {0,POWM_SEC_TABLE,~(mp_bitcnt_t)0};
- for (k = 1; enb > x[k]; k++)
+ static const mp_bitcnt_t x[] = {POWM_SEC_TABLE,~(mp_bitcnt_t)0};
+ for (k = 0; enb > x[k++]; )
;
ASSERT (k <= enb);
return k;
@@ -205,6 +205,52 @@
MPN_COPY (rp, tp, n);
}
+static mp_limb_t
+sec_binvert_limb (mp_limb_t n)
+{
+ mp_limb_t inv, t;
+ ASSERT ((n & 1) == 1);
+ /* 3 + 2 -> 5 */
+ inv = n + (((n + 1) << 1) & 0x18);
+
+ t = n * inv;
+#if GMP_NUMB_BITS <= 10
+ /* 5 x 2 -> 10 */
+ inv = 2 * inv - inv * t;
+#else /* GMP_NUMB_BITS > 10 */
+ /* 5 x 2 + 2 -> 12 */
+ inv = 2 * inv - inv * t + ((inv<<10)&-(t&(1<<5)));
+#endif /* GMP_NUMB_BITS <= 10 */
+
+ if (GMP_NUMB_BITS > 12)
+ {
+ t = n * inv - 1;
+ if (GMP_NUMB_BITS <= 36)
+ {
+ /* 12 x 3 -> 36 */
+ inv += inv * t * (t - 1);
+ }
+ else /* GMP_NUMB_BITS > 36 */
+ {
+ mp_limb_t t2 = t * t;
+#if GMP_NUMB_BITS <= 60
+ /* 12 x 5 -> 60 */
+ inv += inv * (t2 + 1) * (t2 - t);
+#else /* GMP_NUMB_BITS > 60 */
+ /* 12 x 5 + 4 -> 64 */
+ inv *= (t2 + 1) * (t2 - t) + 1 - ((t<<48)&-(t&(1<<12)));
+
+ /* 64 -> 128 -> 256 -> ... */
+ for (int todo = (GMP_NUMB_BITS - 1) >> 6; todo != 0; todo >>= 1)
+ inv = 2 * inv - inv * inv * n;
+#endif /* GMP_NUMB_BITS <= 60 */
+ }
+ }
+
+ ASSERT ((inv * n & GMP_NUMB_MASK) == 1);
+ return inv & GMP_NUMB_MASK;
+}
+
/* {rp, n} <-- {bp, bn} ^ {ep, en} mod {mp, n},
where en = ceil (enb / GMP_NUMB_BITS)
Requires that {mp, n} is odd (and hence also mp[0] odd).
@@ -230,18 +276,19 @@
windowsize = win_size (enb);
- if (BELOW_THRESHOLD (n, REDC_1_TO_REDC_2_THRESHOLD))
+ mip = ip;
+ mip[0] = sec_binvert_limb (mp[0]);
+ if (ABOVE_THRESHOLD (n, REDC_1_TO_REDC_2_THRESHOLD))
{
- mip = ip;
- binvert_limb (mip[0], mp[0]);
- mip[0] = -mip[0];
+ mp_limb_t t, dummy, mip0 = mip[0];
+
+ umul_ppmm (t, dummy, mip0, mp[0]);
+ ASSERT (dummy == 1);
+ t += mip0 * mp[1]; /* t = (mp * mip0)[1] */
+
+ mip[1] = t * mip0 - 1; /* ~( - t * mip0) */
}
- else
- {
- mip = ip;
- mpn_binvert (mip, mp, 2, tp);
- mip[0] = -mip[0]; mip[1] = ~mip[1];
- }
+ mip[0] = -mip[0];
pp = tp;
tp += (n << windowsize); /* put tp after power table */
More information about the gmp-commit
mailing list