[Gmp-commit] /var/hg/gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue Feb 9 17:32:52 UTC 2021
details: /var/hg/gmp/rev/00de66c682c7
changeset: 18200:00de66c682c7
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 09 18:25:34 2021 +0100
description:
mpn/generic/binvert.c: Remove unneeded mpn_sub_1.
details: /var/hg/gmp/rev/73fadaf1570d
changeset: 18201:73fadaf1570d
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 09 18:30:27 2021 +0100
description:
mpz/millerrabin.c (millerrabin): Don't check unlikely 0 or 1.
(mpz_millerrabin): Update limit for numbers checked "surely prime".
details: /var/hg/gmp/rev/bc5ea129d0e8
changeset: 18202:bc5ea129d0e8
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 09 18:32:31 2021 +0100
description:
Copyright year
diffstat:
mini-gmp/mini-gmp.c | 2 +-
mpn/generic/binvert.c | 7 +++++--
mpz/millerrabin.c | 23 +++++++++--------------
3 files changed, 15 insertions(+), 17 deletions(-)
diffs (104 lines):
diff -r 989830e2b958 -r bc5ea129d0e8 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Mon Jan 18 23:03:10 2021 +0100
+++ b/mini-gmp/mini-gmp.c Tue Feb 09 18:32:31 2021 +0100
@@ -2,7 +2,7 @@
Contributed to the GNU project by Niels Möller
-Copyright 1991-1997, 1999-2020 Free Software Foundation, Inc.
+Copyright 1991-1997, 1999-2021 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
diff -r 989830e2b958 -r bc5ea129d0e8 mpn/generic/binvert.c
--- a/mpn/generic/binvert.c Mon Jan 18 23:03:10 2021 +0100
+++ b/mpn/generic/binvert.c Tue Feb 09 18:32:31 2021 +0100
@@ -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 GMP RELEASE.
-Copyright (C) 2004-2007, 2009, 2012, 2017 Free Software Foundation, Inc.
+Copyright (C) 2004-2007, 2009, 2012, 2017, 2021 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -94,7 +94,10 @@
/* X <- UR. */
m = mpn_mulmod_bnm1_next_size (newrn);
mpn_mulmod_bnm1 (xp, m, up, newrn, rp, rn, xp + m);
- mpn_sub_1 (xp + m, xp, rn - (m - newrn), 1);
+ /* Only the values in the range xp + rn .. xp + newrn - 1 are
+ used by the _mullo_n below.
+ Since m >= newrn, we do not need the following. */
+ /* mpn_sub_1 (xp + m, xp, rn - (m - newrn), 1); */
/* R = R(X/B^rn) */
mpn_mullo_n (rp + rn, rp, xp + rn, newrn - rn);
diff -r 989830e2b958 -r bc5ea129d0e8 mpz/millerrabin.c
--- a/mpz/millerrabin.c Mon Jan 18 23:03:10 2021 +0100
+++ b/mpz/millerrabin.c Tue Feb 09 18:32:31 2021 +0100
@@ -8,7 +8,7 @@
With the current implementation, the first 24 MR-tests are substituted by a
Baillie-PSW probable prime test.
- This implementation the Baillie-PSW test was checked up to 19*2^46,
+ This implementation the Baillie-PSW test was checked up to 23*10^14,
for smaller values no MR-test is performed, regardless of reps, and
2 ("surely prime") is returned if the number was not proved composite.
@@ -19,7 +19,7 @@
CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN
FUTURE GNU MP RELEASES.
-Copyright 1991, 1993, 1994, 1996-2002, 2005, 2014, 2018, 2019 Free
+Copyright 1991, 1993, 1994, 1996-2002, 2005, 2014, 2018-2021 Free
Software Foundation, Inc.
Contributed by John Amanatides.
@@ -65,7 +65,6 @@
{
mpz_t nm, x, y, q;
unsigned long int k;
- gmp_randstate_t rstate;
int is_prime;
TMP_DECL;
TMP_MARK;
@@ -101,12 +100,12 @@
|| SIZ (n) - 64 / GMP_NUMB_BITS == (PTR (n) [64 / GMP_NUMB_BITS] < CNST_LIMB(1) << 64 % GMP_NUMB_BITS)
#endif
#else
- /* Consider numbers up to 19*2^46 that pass the BPSW test as primes.
- This implementation was tested up to 19*2^46 = 2^50+2^47+2^46 */
- /* 2^4 < 19 = 0b10011 < 2^5 */
-#define GMP_BPSW_LIMB_CONST CNST_LIMB(19)
-#define GMP_BPSW_BITS_CONST (LOG2C(19) - 1)
-#define GMP_BPSW_BITS_LIMIT (46 + GMP_BPSW_BITS_CONST)
+ /* Consider numbers up to 65*2^45 that pass the BPSW test as primes.
+ This implementation was tested up to 23*10^14 > 2^51+2^45 */
+ /* 2^6 < 65 = 0b1000001 < 2^7 */
+#define GMP_BPSW_LIMB_CONST CNST_LIMB(65)
+#define GMP_BPSW_BITS_CONST (LOG2C(65) - 1)
+#define GMP_BPSW_BITS_LIMIT (45 + GMP_BPSW_BITS_CONST)
#define GMP_BPSW_LIMBS_LIMIT (GMP_BPSW_BITS_LIMIT / GMP_NUMB_BITS)
#define GMP_BPSW_BITS_MOD (GMP_BPSW_BITS_LIMIT % GMP_NUMB_BITS)
@@ -142,6 +141,7 @@
reps -= 24;
if (reps > 0)
{
+ gmp_randstate_t rstate;
/* (n-5)/2 */
mpz_sub_ui (nm, nm, 2L);
ASSERT (mpz_cmp_ui (nm, 1L) >= 0);
@@ -212,11 +212,6 @@
mpz_powm_ui (y, y, 2L, n);
if (mod_eq_m1 (y, n))
return 1;
- /* y == 1 means that the previous y was a non-trivial square root
- of 1 (mod n). y == 0 means that n is a power of the base.
- In either case, n is not prime. */
- if (mpz_cmp_ui (y, 1L) <= 0)
- return 0;
}
return 0;
}
More information about the gmp-commit
mailing list