1 /* Copyright 2011-2015 David Cleaver 2 * 3 * This program is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU Lesser General Public License as published by 5 * the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU Lesser General Public License for more details. 12 * 13 * You should have received a copy of the GNU Lesser General Public License 14 * along with this program. If not, see <http://www.gnu.org/licenses/>. 15 */ 16 17 #ifndef __MPZ_APRCL__ 18 #define __MPZ_APRCL__ 19 20 #ifndef HAVE_U64_T 21 #define HAVE_U64_T 22 typedef long long s64_t; 23 typedef unsigned long long u64_t; 24 #endif 25 26 #include "jacobi_sum.h" 27 28 /*******************************************************/ 29 /*******************************************************/ 30 /* These are the definitions for the APRT-CLE routines */ 31 /*******************************************************/ 32 /*******************************************************/ 33 /* verbose = 0 means to only return the status */ 34 /* it will not print out progress info */ 35 /* verbose = 1 means to print out progress info */ 36 /* verbose = 2 means to print out progress/failure/failover info */ 37 #define APRTCLE_VERBOSE0 0 38 #define APRTCLE_VERBOSE1 1 39 #define APRTCLE_VERBOSE2 2 40 41 #define APRTCLE_ERROR -1 42 #define APRTCLE_COMPOSITE 0 43 #define APRTCLE_PRP 1 44 #define APRTCLE_PRIME 2 45 46 /* ********************************************************************************** 47 * APR-CL (also known as APRT-CLE) is a prime proving algorithm developed by: 48 * L. Adleman, C. Pomerance, R. Rumely, H. Cohen, and H. W. Lenstra 49 * APRT-CLE = Adleman-Pomerance-Rumely Test Cohen-Lenstra Extended version 50 * You can find all the details of this implementation in the Cohen & Lenstra paper: 51 * H. Cohen and A. K. Lenstra, "Implementation of a new primality test", 52 * Math. Comp., 48 (1987) 103--121 53 * 54 * ---------------------------------------------------------------------------------- 55 * 56 * This C/GMP version is a conversion of Dario Alpern's Java based APRT-CLE code 57 * His code was based on Yuji Kida's UBASIC code 58 * 59 * Based on APRT-CLE Written by Dario Alejandro Alpern (Buenos Aires - Argentina) 60 * From: Last updated September 10th, 2011. See http://www.alpertron.com.ar/ECM.HTM 61 * 62 * On 2012/11/12 Dario Alpern has approved the conversion, from Java to C/GMP, of 63 * his implementation of the APR-CL algorithm, and that it be licensed under the LGPL. 64 * 65 * ---------------------------------------------------------------------------------- 66 * 67 * With improvements based on Jason Moxham's APRCL v1.15 code, from 2003/01/01 68 * 69 * On 2013/04/14 Toby Moxham has approved the APR-CL code and data tables, 70 * originally written by his brother Jason Moxham on 2003/01/01, to be released 71 * under the LGPL. 72 * 73 * ---------------------------------------------------------------------------------- 74 * 75 * v1.0 to v1.1 improvements: 76 * 77 * [The following fix was recommended by Dana Jacobsen and verified by Jon Grantham] 78 * - Bug fix: Removed unnecessary vl==0 check in mpz_extrastronglucas_prp 79 * [The following improvements/fixes were recommended by Laurent Desnogues in 2013/08] 80 * - Speed improvement 1: Removed extraneous NormalizeJS calls in ARPCL 81 * - Speed improvement 2: Removed/consolidated calls to mpz_mod in APRCL 82 * (these improvements make the APRCL code about 1.5-2.2x faster) 83 * - Bug fix: Final test in APRCL routine is now correct 84 * 85 * 86 * *********************************************************************************/ 87 88 int mpz_aprcl(mpz_t N); /* Just return the status of the input, no progress is printed out */ 89 int mpz_aprtcle(mpz_t N, int verbose); 90 91 #endif 92