From 11da511c784eca003deb90c23570f0873954e0de Mon Sep 17 00:00:00 2001 From: Duncan Wilkie Date: Sat, 18 Nov 2023 06:11:09 -0600 Subject: Initial commit. --- gmp-6.3.0/tests/mpz/t-pprime_p.c | 243 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 243 insertions(+) create mode 100644 gmp-6.3.0/tests/mpz/t-pprime_p.c (limited to 'gmp-6.3.0/tests/mpz/t-pprime_p.c') diff --git a/gmp-6.3.0/tests/mpz/t-pprime_p.c b/gmp-6.3.0/tests/mpz/t-pprime_p.c new file mode 100644 index 0000000..dffe6ea --- /dev/null +++ b/gmp-6.3.0/tests/mpz/t-pprime_p.c @@ -0,0 +1,243 @@ +/* Exercise mpz_probab_prime_p. + +Copyright 2002, 2018-2019, 2022 Free Software Foundation, Inc. + +This file is part of the GNU MP Library test suite. + +The GNU MP Library test suite is free software; you can redistribute it +and/or modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 3 of the License, +or (at your option) any later version. + +The GNU MP Library test suite is distributed in the hope that it will be +useful, but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General +Public License for more details. + +You should have received a copy of the GNU General Public License along with +the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ + +#include +#include +#include "gmp-impl.h" +#include "tests.h" + + +/* Enhancements: + + - Test some big primes don't come back claimed to be composite. + - Test some big composites don't come back claimed to be certainly prime. + - Test some big composites with small factors are identified as certainly + composite. */ + + +/* return 2 if prime, 0 if composite */ +int +isprime (unsigned long n) +{ + if (n < 4) + return (n & 2); + if ((n & 1) == 0) + return 0; + + for (unsigned long i = 3; i*i <= n; i+=2) + if ((n % i) == 0) + return 0; + + return 2; +} + +void +check_one (mpz_srcptr n, int want) +{ + int got; + + got = mpz_probab_prime_p (n, 25); + + /* "definitely prime" (2) is fine if we only wanted "probably prime" (1) */ + if ((got != want) && (got != want * 2)) + { + printf ("mpz_probab_prime_p\n"); + mpz_trace (" n ", n); + printf (" got =%d", got); + printf (" want=%d", want); + abort (); + } +} + +void +check_pn (mpz_ptr n, int want) +{ + check_one (n, want); + mpz_neg (n, n); + check_one (n, want); +} + +/* expect certainty for small n */ +void +check_small (void) +{ + mpz_t n; + long i; + + mpz_init (n); + + for (i = 0; i < 300; i++) + { + mpz_set_si (n, i); + check_pn (n, isprime (i)); + } + + mpz_clear (n); +} + +void +check_composites (int count) +{ + int i; + mpz_t a, b, n, bs; + unsigned long size_range, size; + gmp_randstate_ptr rands = RANDS; + + mpz_init (a); + mpz_init (b); + mpz_init (n); + mpz_init (bs); + + static const char * const composites[] = { + "225670644213750121", /* n=61*C16, if D < 61, (n/D) = 1. */ + "2386342059899637841", /* n=61*C17, if D < 61, (n/D) = 1. */ + "1194649", /* A square, but strong base-2 pseudoprime, */ + "12327121", /* another base-2 pseudoprime square. */ + "18446744066047760377", /* Should trigger Fibonacci's test; */ + "10323769", /* &3==1, Lucas' test with D=37; */ + "1397419", /* &3==3, Lucas' test with D=43; */ + "11708069165918597341", /* &3==1, Lucas' test with large D=107; */ + "395009109077493751", /* &3==3, Lucas' test with large D=113. */ + NULL + }; + + for (i = 0; composites[i]; i++) + { + mpz_set_str_or_abort (n, composites[i], 0); + check_one (n, 0); + } + + for (i = 0; i < count; i++) + { + mpz_urandomb (bs, rands, 32); + size_range = mpz_get_ui (bs) % 13 + 1; /* 0..8192 bit operands */ + + mpz_urandomb (bs, rands, size_range); + size = mpz_get_ui (bs); + mpz_rrandomb (a, rands, size); + + mpz_urandomb (bs, rands, 32); + size_range = mpz_get_ui (bs) % 13 + 1; /* 0..8192 bit operands */ + mpz_rrandomb (b, rands, size); + + /* Exclude trivial factors */ + if (mpz_cmp_ui (a, 1) == 0) + mpz_set_ui (a, 2); + if (mpz_cmp_ui (b, 1) == 0) + mpz_set_ui (b, 2); + + mpz_mul (n, a, b); + + check_pn (n, 0); + } + mpz_clear (a); + mpz_clear (b); + mpz_clear (n); + mpz_clear (bs); +} + +static void +check_primes (void) +{ + static const char * const primes[] = { + "2", "53", "1234567891", + "2055693949", "1125899906842597", "16412292043871650369", + "18446744075358702679", /* Lucas' test with large D=107. */ + /* diffie-hellman-group1-sha1, also "Well known group 2" in RFC + 2412, 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 } */ + "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1" + "29024E088A67CC74020BBEA63B139B22514A08798E3404DD" + "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245" + "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED" + "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381" + "FFFFFFFFFFFFFFFF", + NULL + }; + + mpz_t n; + int i; + + mpz_init (n); + + for (i = 0; primes[i]; i++) + { + mpz_set_str_or_abort (n, primes[i], 0); + check_one (n, 1); + } + mpz_clear (n); +} + +static void +check_fermat_mersenne (int count) +{ + int fermat_exponents [] = {1, 2, 4, 8, 16}; + int mersenne_exponents [] = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, + 107, 127, 521, 607, 1279, 2203, 2281, + 3217, 4253, 4423, 9689, 9941, 11213, + 19937, 21701, 23209, 44497, 86243}; + mpz_t pp; + int i, j, want; + + mpz_init (pp); + count = MIN (110000, count); + + for (i=1; i> 3); + check_composites (count); + check_primes (); + + tests_end (); + exit (0); +} -- cgit v1.2.3