1 /*============================================================================== 2 | 3 | File Name: 4 | 5 | Primpoly.h 6 | 7 | Description: 8 | 9 | Global header file for primitive polynomial routines. 10 | Constants, data types and algorithm control parameters. 11 | 12 | For an exhaustive description of the algorithms used in this program, 13 | the theory which underlies them, and the software design, visit my 14 | web page at http://seanerikoconnor.freeservers.com 15 | 16 | LEGAL 17 | 18 | Primpoly Version 16.1 - A Program for Computing Primitive Polynomials. 19 | Copyright (C) 1999-2021 by Sean Erik O'Connor. All Rights Reserved. 20 | 21 | This program is free software: you can redistribute it and/or modify 22 | it under the terms of the GNU General Public License as published by 23 | the Free Software Foundation, either version 3 of the License, or 24 | (at your option) any later version. 25 | 26 | This program is distributed in the hope that it will be useful, 27 | but WITHOUT ANY WARRANTY; without even the implied warranty of 28 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 29 | GNU General Public License for more details. 30 | 31 | You should have received a copy of the GNU General Public License 32 | along with this program. If not, see <http://www.gnu.org/licenses/>. 33 | 34 | The author's address is artificer!AT!seanerikoconnor!DOT!freeservers!DOT!com 35 | with !DOT! replaced by . and the !AT! replaced by @ 36 | 37 ==============================================================================*/ 38 39 #ifndef PP_H /* Wrap this header file. */ 40 #define PP_H 41 42 43 /*============================================================================== 44 | DATA TYPES 45 ==============================================================================*/ 46 47 /* Extend the range of the program's calculations using a higher precision 48 integer type, in this case a 64-bit type. 49 */ 50 #if defined( _MSC_VER ) /* Microsoft/Pentium systems with Visual C++ 6.0 */ 51 typedef unsigned __int64 bigint ; /* Special type defined in the Microsoft 52 Visual C++ 6.0 SP3 compiler. */ 53 typedef __int64 sbigint ; /* Signed version. */ 54 #define bigintOutputFormat "%I64u" 55 #else /* Unix systems (e.g. PC/Cygwin or Mac OS X) */ 56 typedef unsigned long long bigint ; 57 typedef long long sbigint ; 58 #define bigintOutputFormat "%lld" 59 #endif 60 61 #define YES 1 /* Imitate boolean values. */ 62 #define NO 0 63 64 /* In case it's not defined, put something reasonable. */ 65 #ifndef _MAX_PATH 66 #define _MAX_PATH 100 67 #endif 68 69 70 /*============================================================================== 71 | CONSTANTS 72 ==============================================================================*/ 73 74 #define MAXPTON (bigint) \ 75 pow( (double) 2, \ 76 (double) (8 * sizeof( bigint ) - 1) ) - 1 77 78 /* Maximum value of p to the nth power. As high 79 as possible without causing integer overflow 80 or overflow into the sign bit (if a signed type) 81 for the bigint data type. This value will be 82 b 83 2 - 1 if bigint = b-bit unsigned integer type. 84 b-1 85 2 - 1 if bigint = b-bit signed integer type.*/ 86 87 #define NUMBITS 8 * \ 88 sizeof( bigint ) /* Number of bits in the high precision integer. */ 89 90 #define MAXDEGPOLY 62 /* Maximum possible degree n of f( x ) when p = 2: 91 | log ( MAXPTON ) |. 92 -- 2 -- */ 93 94 #define MAXNUMPRIMEFACTORS 31 /* Maxmimum number of distinct primes = 95 | log ( MAXPTON ) | + 1. 96 -- -- */ 97 98 #define NUM_PRIME_TEST_TRIALS 25 /* Number of trials to test if a number is 99 probably prime. */ 100 101 102 /*============================================================================== 103 | CONTROL PARAMETERS 104 ==============================================================================*/ 105 106 #define NUMOPTIONS 3 /* Number of command line arguments including 107 the program name "pp". */ 108 109 #define NUMTERMSPERLINE 7 /* How many terms of a polynomial to 110 write before starting a new line. */ 111 112 /*============================================================================== 113 | F U N C T I O N S 114 ==============================================================================*/ 115 116 /* ppIO.c */ 117 int parse_command_line( int argc, 118 char * argv[], 119 int * testPolynomialForPrimitivity, 120 int * listAllPrimitivePolynomials, 121 int * printStatistics, 122 int * printHelp, 123 int * selfCheck, 124 int * p, 125 int * n, 126 int * testPolynomial ) ; 127 void write_poly ( int * a, int n ) ; 128 129 130 /* ppArith.c */ 131 int mod ( int n, int p ) ; 132 bigint power ( int x, int y ) ; 133 int power_mod ( int a, int n, int p ) ; 134 int is_primitive_root( int a, int p ) ; 135 int inverse_mod_p ( int n, int p ) ; 136 137 138 /* ppPolyArith.c */ 139 int eval_poly ( int * f, int x, int n, int p ) ; 140 int linear_factor ( int * f, int n, int p ) ; 141 int is_integer ( int * t, int n ) ; 142 void construct_power_table( int power_table[][ MAXDEGPOLY ], int * f, 143 int n, int p ) ; 144 int auto_convolve ( int * t, int k, int lower, int upper, int p ) ; 145 int convolve ( int * s, int * t, int k, int lower, int upper, int p ) ; 146 int coeff_of_square ( int * t, int k, int n, int p ) ; 147 int coeff_of_product ( int * s, int * t, int k, int n, int p ) ; 148 void square ( int * t, int power_table[][ MAXDEGPOLY ], int n, int p ) ; 149 void product ( int * s, int * t, int power_table[][ MAXDEGPOLY ], int n, int p ) ; 150 void times_x ( int * t, int power_table[][ MAXDEGPOLY ], int n, int p ) ; 151 void x_to_power ( bigint m, int * g, int power_table[][ MAXDEGPOLY ], int n, int p ) ; 152 153 154 /* ppFactor.c */ 155 int factor ( bigint n, bigint * primes, int * count ) ; 156 int is_probably_prime ( int n, int x ) ; 157 int is_almost_surely_prime( int n ) ; 158 bigint EulerPhi ( bigint n ) ; 159 160 161 /* ppHelperFunc.c */ 162 void initial_trial_poly ( int * f, int n ) ; 163 void next_trial_poly ( int * f, int n, int p ) ; 164 int const_coeff_test ( int * f, int n, int p, int a ) ; 165 int const_coeff_is_primitive_root( int * f, int n, int p ) ; 166 int skip_test ( int i, bigint * primes, int p ) ; 167 void generate_Q_matrix ( int **q, int power_table[][ MAXDEGPOLY ], int n, int p ) ; 168 int find_nullity ( int ** Q, int n, int p ) ; 169 int has_multi_irred_factors ( int power_table[][ MAXDEGPOLY ], int n, int p ) ; 170 171 172 173 /* pporder.c */ 174 int order_m ( int power_table[][ MAXDEGPOLY ], int n, int p, bigint r, 175 bigint * primes, int prime_count ) ; 176 int order_r ( int power_table[][ MAXDEGPOLY ], int n, int p, bigint r, int * a ) ; 177 int maximal_order( int * f, int n, int p ) ; 178 179 #endif /* End of wrapper for header. */
