|
Packit |
5c3484 |
/* Test mpz_perfect_power_p.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Contributed to the GNU project by Torbjorn Granlund and Martin Boij.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 2008-2010, 2014 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library test suite.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library test suite is free software; you can redistribute it
|
|
Packit |
5c3484 |
and/or modify it under the terms of the GNU General Public License as
|
|
Packit |
5c3484 |
published by the Free Software Foundation; either version 3 of the License,
|
|
Packit |
5c3484 |
or (at your option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library test suite is distributed in the hope that it will be
|
|
Packit |
5c3484 |
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
5c3484 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
|
|
Packit |
5c3484 |
Public License for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received a copy of the GNU General Public License along with
|
|
Packit |
5c3484 |
the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include <stdio.h>
|
|
Packit |
5c3484 |
#include <stdlib.h>
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
#include "tests.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
struct
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
const char *num_as_str;
|
|
Packit |
5c3484 |
char want;
|
|
Packit |
5c3484 |
} static tests[] =
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
{ "0", 1},
|
|
Packit |
5c3484 |
{ "1", 1},
|
|
Packit |
5c3484 |
{"-1", 1},
|
|
Packit |
5c3484 |
{ "2", 0},
|
|
Packit |
5c3484 |
{"-2", 0},
|
|
Packit |
5c3484 |
{ "3", 0},
|
|
Packit |
5c3484 |
{"-3", 0},
|
|
Packit |
5c3484 |
{ "4", 1},
|
|
Packit |
5c3484 |
{"-4", 0},
|
|
Packit |
5c3484 |
{ "64", 1},
|
|
Packit |
5c3484 |
{"-64", 1},
|
|
Packit |
5c3484 |
{ "128", 1},
|
|
Packit |
5c3484 |
{"-128", 1},
|
|
Packit |
5c3484 |
{ "256", 1},
|
|
Packit |
5c3484 |
{"-256", 0},
|
|
Packit |
5c3484 |
{ "512", 1},
|
|
Packit |
5c3484 |
{"-512", 1},
|
|
Packit |
5c3484 |
{ "0x4000000", 1},
|
|
Packit |
5c3484 |
{"-0x4000000", 1},
|
|
Packit |
5c3484 |
{ "0x3cab640", 1},
|
|
Packit |
5c3484 |
{"-0x3cab640", 0},
|
|
Packit |
5c3484 |
{ "0x3e23840", 1},
|
|
Packit |
5c3484 |
{"-0x3e23840", 0},
|
|
Packit |
5c3484 |
{ "0x3d3a7ed1", 1},
|
|
Packit |
5c3484 |
{"-0x3d3a7ed1", 1},
|
|
Packit |
5c3484 |
{ "0x30a7a6000", 1},
|
|
Packit |
5c3484 |
{"-0x30a7a6000", 1},
|
|
Packit |
5c3484 |
{ "0xf33e5a5a59", 1},
|
|
Packit |
5c3484 |
{"-0xf33e5a5a59", 0},
|
|
Packit |
5c3484 |
{ "0xed1b1182118135d", 1},
|
|
Packit |
5c3484 |
{"-0xed1b1182118135d", 1},
|
|
Packit |
5c3484 |
{ "0xe71f6eb7689cc276b2f1", 1},
|
|
Packit |
5c3484 |
{"-0xe71f6eb7689cc276b2f1", 0},
|
|
Packit |
5c3484 |
{ "0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 1},
|
|
Packit |
5c3484 |
{"-0x12644507fe78cf563a4b342c92e7da9fe5e99cb75a01", 0},
|
|
Packit |
5c3484 |
{ "0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1},
|
|
Packit |
5c3484 |
{"-0x1ff2e7c581bb0951df644885bd33f50e472b0b73a204e13cbe98fdb424d66561e4000000", 1},
|
|
Packit |
5c3484 |
{ "0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1},
|
|
Packit |
5c3484 |
{"-0x2b9b44db2d91a6f8165c8c7339ef73633228ea29e388592e80354e4380004aad84000000", 1},
|
|
Packit |
5c3484 |
{ "0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1},
|
|
Packit |
5c3484 |
{"-0x28d5a2b8f330910a9d3cda06036ae0546442e5b1a83b26a436efea5b727bf1bcbe7e12b47d81", 1},
|
|
Packit |
5c3484 |
{NULL, 0}
|
|
Packit |
5c3484 |
};
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
check_tests ()
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t x;
|
|
Packit |
5c3484 |
int i;
|
|
Packit |
5c3484 |
int got, want;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_init (x);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (i = 0; tests[i].num_as_str != NULL; i++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_set_str (x, tests[i].num_as_str, 0);
|
|
Packit |
5c3484 |
got = mpz_perfect_power_p (x);
|
|
Packit |
5c3484 |
want = tests[i].want;
|
|
Packit |
5c3484 |
if (got != want)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
fprintf (stderr, "mpz_perfect_power_p returns %d when %d was expected\n", got, want);
|
|
Packit |
5c3484 |
fprintf (stderr, "fault operand: %s\n", tests[i].num_as_str);
|
|
Packit |
5c3484 |
abort ();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_clear (x);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define NRP 15
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
check_random (int reps)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t n, np, temp, primes[NRP];
|
|
Packit |
5c3484 |
int i, j, k, unique, destroy, res;
|
|
Packit |
5c3484 |
unsigned long int nrprimes, primebits;
|
|
Packit |
5c3484 |
mp_limb_t g, exp[NRP], e;
|
|
Packit |
5c3484 |
gmp_randstate_ptr rands;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
rands = RANDS;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_init (n);
|
|
Packit |
5c3484 |
mpz_init (np);
|
|
Packit |
5c3484 |
mpz_init (temp);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (i = 0; i < NRP; i++)
|
|
Packit |
5c3484 |
mpz_init (primes[i]);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (i = 0; i < reps; i++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_urandomb (np, rands, 32);
|
|
Packit |
5c3484 |
nrprimes = mpz_get_ui (np) % NRP + 1; /* 1-NRP unique primes */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_urandomb (np, rands, 32);
|
|
Packit |
5c3484 |
g = mpz_get_ui (np) % 32 + 2; /* gcd 2-33 */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (j = 0; j < nrprimes;)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_urandomb (np, rands, 32);
|
|
Packit |
5c3484 |
primebits = mpz_get_ui (np) % 100 + 3; /* 3-102 bit primes */
|
|
Packit |
5c3484 |
mpz_urandomb (primes[j], rands, primebits);
|
|
Packit |
5c3484 |
mpz_nextprime (primes[j], primes[j]);
|
|
Packit |
5c3484 |
unique = 1;
|
|
Packit |
5c3484 |
for (k = 0; k < j; k++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
if (mpz_cmp (primes[j], primes[k]) == 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
unique = 0;
|
|
Packit |
5c3484 |
break;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
if (unique)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_urandomb (np, rands, 32);
|
|
Packit |
5c3484 |
e = 371 / (10 * primebits) + mpz_get_ui (np) % 11 + 1; /* Magic constants */
|
|
Packit |
5c3484 |
exp[j++] = g * e;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (nrprimes > 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* Destroy d exponents, d in [1, nrprimes - 1] */
|
|
Packit |
5c3484 |
if (nrprimes == 2)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
destroy = 1;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_urandomb (np, rands, 32);
|
|
Packit |
5c3484 |
destroy = mpz_get_ui (np) % (nrprimes - 2);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
g = exp[destroy];
|
|
Packit |
5c3484 |
for (k = destroy + 1; k < nrprimes; k++)
|
|
Packit |
5c3484 |
g = mpn_gcd_1 (&g, 1, exp[k]);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (j = 0; j < destroy; j++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_urandomb (np, rands, 32);
|
|
Packit |
5c3484 |
e = mpz_get_ui (np) % 50 + 1;
|
|
Packit |
5c3484 |
while (mpn_gcd_1 (&g, 1, e) > 1)
|
|
Packit |
5c3484 |
e++;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
exp[j] = e;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Compute n */
|
|
Packit |
5c3484 |
mpz_pow_ui (n, primes[0], exp[0]);
|
|
Packit |
5c3484 |
for (j = 1; j < nrprimes; j++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_pow_ui (temp, primes[j], exp[j]);
|
|
Packit |
5c3484 |
mpz_mul (n, n, temp);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
res = mpz_perfect_power_p (n);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (nrprimes == 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
if (res == 0 && exp[0] > 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf("n is a perfect power, perfpow_p disagrees\n");
|
|
Packit |
5c3484 |
gmp_printf("n = %Zu\nprimes[0] = %Zu\nexp[0] = %lu\n", n, primes[0], exp[0]);
|
|
Packit |
5c3484 |
abort ();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else if (res == 1 && exp[0] == 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
gmp_printf("n = %Zu\n", n);
|
|
Packit |
5c3484 |
printf("n is now a prime number, but perfpow_p still believes n is a perfect power\n");
|
|
Packit |
5c3484 |
abort ();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
if (res == 1 && destroy != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
gmp_printf("n = %Zu\nn was destroyed, but perfpow_p still believes n is a perfect power\n", n);
|
|
Packit |
5c3484 |
abort ();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else if (res == 0 && destroy == 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
gmp_printf("n = %Zu\nn is a perfect power, perfpow_p disagrees\n", n);
|
|
Packit |
5c3484 |
abort ();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpz_clear (n);
|
|
Packit |
5c3484 |
mpz_clear (np);
|
|
Packit |
5c3484 |
mpz_clear (temp);
|
|
Packit |
5c3484 |
for (i = 0; i < NRP; i++)
|
|
Packit |
5c3484 |
mpz_clear (primes[i]);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
int
|
|
Packit |
5c3484 |
main (int argc, char **argv)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
int n_tests;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
tests_start ();
|
|
Packit |
5c3484 |
mp_trace_base = -16;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
check_tests ();
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
n_tests = 500;
|
|
Packit |
5c3484 |
if (argc == 2)
|
|
Packit |
5c3484 |
n_tests = atoi (argv[1]);
|
|
Packit |
5c3484 |
check_random (n_tests);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
tests_end ();
|
|
Packit |
5c3484 |
exit (0);
|
|
Packit |
5c3484 |
}
|