diff options
author | Torbjörn Granlund <tg@gmplib.org> | 2012-09-04 18:38:29 +0200 |
---|---|---|
committer | Jim Meyering <meyering@redhat.com> | 2012-09-07 11:04:41 +0200 |
commit | 6c13e72c797771b4a37ffbea3e03f60b57f33a68 (patch) | |
tree | 5be762374d1688efadc3eef7e53693f465a01cc6 /gl/modules | |
parent | 51a4b04954ad5ad12de1d1b82a3603fc350a3bfa (diff) | |
download | coreutils-6c13e72c797771b4a37ffbea3e03f60b57f33a68.tar.xz |
factor: don't ever declare composites to be prime
The multiple-precision factoring code (with HAVE_GMP) was copied from
a now-obsolete version of GMP that did not pass proper arguments to
the mpz_probab_prime_p function. It makes that code perform no more
than 3 Miller-Rabin tests only, which is not sufficient.
A Miller-Rabin test will detect composites with at least a probability
of 3/4. For a uniform random composite, the probability will actually
be much higher.
Or put another way, of the N-3 possible Miller-Rabin tests for checking
the composite N, there is no number N for which more than (N-3)/4 of the
tests will fail to detect the number as a composite. For most numbers N
the number of "false witnesses" will be much, much lower.
Problem numbers are of the form N=pq, p,q prime and (p-1)/(q-1) = s,
where s is a small integer. (There are other problem forms too,
involving 3 or more prime factors.) When s = 2, we get the 3/4 factor.
It is easy to find numbers of that form that cause coreutils' factor to
fail:
465658903
2242724851
6635692801
17709149503
17754345703
20889169003
42743470771
54890944111
72047131003
85862644003
98275842811
114654168091
117225546301
...
There are 9008992 composites of the form with s=2 below 2^64. With 3
Miller-Rabin tests, one would expect about 9008992/64 = 140766 to be
invalidly recognized as primes in that range.
* src/factor.c (MR_REPS): Define to 25.
(factor_using_pollard_rho): Use MR_REPS, not 3.
(print_factors_multi): Likewise.
* THANKS.in: Remove my name, now that it will be automatically
included in the generated THANKS file.
Diffstat (limited to 'gl/modules')
0 files changed, 0 insertions, 0 deletions