From 6c13e72c797771b4a37ffbea3e03f60b57f33a68 Mon Sep 17 00:00:00 2001 From: Torbjörn Granlund Date: Tue, 4 Sep 2012 18:38:29 +0200 Subject: 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. --- THANKS.in | 1 - 1 file changed, 1 deletion(-) (limited to 'THANKS.in') diff --git a/THANKS.in b/THANKS.in index 158015187..2c3f83cdc 100644 --- a/THANKS.in +++ b/THANKS.in @@ -608,7 +608,6 @@ Tony Leneis tony@plaza.ds.adp.com Tony Robinson ajr@eng.cam.ac.uk Toomas Soome Toomas.Soome@Elion.ee Toralf Förster toralf.foerster@gmx.de -Torbjorn Granlund tege@nada.kth.se Torbjorn Lindgren tl@funcom.no Torsten Landschoff torsten@pclab.ifg.uni-kiel.de Travis Gummels tgummels@redhat.com -- cgit v1.2.3-54-g00ecf