diff options
| author | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2014-05-21 09:48:26 +0200 |
|---|---|---|
| committer | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2014-05-21 09:48:26 +0200 |
| commit | 5752fe767561f6a7e68246010a0ba1d3c9e7e547 (patch) | |
| tree | f0427ac27d537db75dbdf6c975c0e9a535bb2de4 /mpz/millerrabin.c | |
| parent | 6e665beb3d70e78c2b91dcafb3c854fc80c5cc0c (diff) | |
| download | gmp-5752fe767561f6a7e68246010a0ba1d3c9e7e547.tar.gz | |
mpz/millerrabin.c (millerrabin): Consider the rare case n is a power
Diffstat (limited to 'mpz/millerrabin.c')
| -rw-r--r-- | mpz/millerrabin.c | 8 |
1 files changed, 6 insertions, 2 deletions
diff --git a/mpz/millerrabin.c b/mpz/millerrabin.c index e1ce32c89..1dab971c1 100644 --- a/mpz/millerrabin.c +++ b/mpz/millerrabin.c @@ -9,7 +9,8 @@ CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN FUTURE GNU MP RELEASES. -Copyright 1991, 1993, 1994, 1996-2002, 2005 Free Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996-2002, 2005, 2014 Free Software +Foundation, Inc. Contributed by John Amanatides. @@ -117,7 +118,10 @@ millerrabin (mpz_srcptr n, mpz_srcptr nm1, mpz_ptr x, mpz_ptr y, mpz_powm_ui (y, y, 2L, n); if (mpz_cmp (y, nm1) == 0) return 1; - if (mpz_cmp_ui (y, 1L) == 0) + /* 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; |