Note on primality testing

This library includes a Java port of Colin Plumb's implementation of Euler's Criterion for primality testing, from his bnlib (version 1.1) package. This test is consistently used, throughout this package, in preference to the Miller-Rabin probabilistic primality test—which is also implemented and included.

During the development, and tests, of the primality testing code, certain large numbers where found to be possible primes, even though the invocation of the isProbablePrime() method, provided by the java.math.BigInteger class claimed otherwise; i.e. returned false. I then ran those numbers through a primality proving application: PRIMO. Consistently, PRIMO proved those numbers to be indeed primes. I'm including the certificates PRIMO emits for review and to help debug the code in BigInteger since I cannot myself look at its source.

N (hexadecimal representation)	Primality Certificate
`888f a43a 2162 ca5c cdcf 7692 bcf5 f7a5 8f74 ff17`	Primo-B26DD022D8AB3
`9637 bddd 6b61 7916 4abe 971f 5051 6e4c 21de d7fb`	Primo-B26DD022A073E
`9f78 298f 3a49 3f5a 12fa 74b7 8881 61d6 5f01 9943`	Primo-B26F102996AB4
`a2e0 44da ff1c f529 f536 66ab 1861 d9c8 4d20 f4af`	Primo-B26DD022BF582
`a862 42e7 489d 79f3 153c 561b 5e53 00ab 736b 383f`	Primo-B26DD022F8215
`de09 f190 2cf4 84f2 32fe e5d2 7262 372d 1c60 72d7`	Primo-B26DC04CD92D1
`e844 990a 2f38 a72e 6301 97ca 3846 d75d e56e 2e53`	Primo-B26DD0228AF78
`964f cbaa 6a75 797d c797 ef47 6939 9c9d da13 b382 4fe9 c38c 15c8 2e48 64ff 8cf6 ef83 1924 90b0 c881 3f57 caa8 c4d9 7bb7 0ec5 56bf 7e86 9a59 4715 a1c6 507a d04f`	Primo-B26E900ADFBBA
`b966 49d9 7158 2f37 d3f8 3ee1 ddee dc10 63cb 74ed 6411 6bcc 62c1 52b5 9ec2 04f3 3c22 bf11 2f05 3669 cdde ebc1 68d3 54f3 eb6d 3130 52b7 2b05 3ad2 a6ee 9ee8 9847`	Primo-B26F102965B00
`bf29 1985 1a94 9a52 02d9 c734 f109 2140 2d19 1cf1 ef6f 84d0 5d44 8f3d 0566 99e9 1bdf 0e72 cea7 3922 af25 3cb0 a6db de6f a1ce 2d89 425b 2161 c757 8ebe d952 8c8b`	Primo-B26DD023184EC
`c59b ca6d fd38 0e00 1a4a 9e71 c98e f306 7b94 366f feda 6232 3e3a 6994 aad8 7a7d 810f 175f bc6b 9cce 645d 2ee0 cce5 b772 5968 b371 ad7b a997 f8b2 b25f 332b e307`	Primo-B26DD02335DF2
`c95d 51d8 e607 7fae 49b9 a08b 844d 25d0 2c91 b830 15ca ea6f 70d7 14a4 5f8f 144e addf b15c c330 8cdc fdc0 42ad f922 8ac2 14bc bed1 d33c 4731 fc92 32c0 d775 099f`	Primo-B26DD02344176
`e9ed cdbe a826 4c1a e2ff 4c3b e0c9 3980 05bf b699 3c50 18f9 0b10 f72c 0da9 7e0c d161 269b 8693 c988 1d07 9997 5f96 fbb8 8e61 98f9 90c1 fff6 add4 8817 e2ef d03f`	Primo-B26F1028E6A9F
`f2a4 85e4 2143 bc7a 59a8 4cf3 4ad6 a21c c297 05b4 418a 1a9b c1ef 29d5 133b e476 4f88 c79a 87d0 8a4f 2234 8e84 3fa3 ee33 636f 97e7 5265 da69 dad6 9563 74ef 534b`	Primo-B26F10293C5EE
`f424 25be 8d04 1b16 5929 d2b5 eeab 27f1 3e03 15e0 542c dc33 9a95 eba6 abcd e3ab c165 6b6f f873 bde6 d7de 4856 2c7c 6a18 aba7 e222 a853 69a6 72de 52ea ea71 34f3`	Primo-B26E900B6F8B1
`f58e 966a 4a81 d899 8518 dfc5 5407 7723 8d57 f1d1 5717 d69d 0f01 526b e88d db79 b9dc 4bd2 23f4 6585 cbe0 25b4 87a3 1416 3f75 5c39 27f8 5592 8819 d03c df76 5643`	Primo-B26DD023281FB
`f986 370b 2bb2 4bdd feeb 53ff 1678 59bf 7b00 aed6 b3d6 52fa c3f0 6131 25f3 101c 625e 8003 1aef e6c8 7aef d3d6 3f92 3e6c 4d37 54dd a810 587d 0d71 fe5d 18fb baa7`	Primo-B26DD02306259
`f995 c828 4492 6e6c 423e c13c 8fa2 63d9 19b0 4811 eddf 414b 5fe8 354d 4d2a 4ed0 2964 7ef0 57e0 93e6 64ca 0fef 0d91 5f3b 6815 ee8f 77d7 0ef4 dab9 ddc0 b795 ff0b`	Primo-B26DD02359EFD

Retrun to the [ GNU Crypto's home page | GNU's home page ].

Please send FSF & GNU inquiries & questions to gnu@gnu.org. There are also other ways to contact the FSF.

Please send comments on these web pages to webmasters@gnu.org, send other questions to gnu@gnu.org.

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Last Modified: $Date: 2006/11/25 10:32:10 $ $Author: ramprasadb $