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.4 - A Program for Computing Primitive Polynomials.
19| Copyright (C) 1999-2025 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 seanerikoconnor!AT!gmail!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 */
117int 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 ) ;
127void write_poly ( int * a, int n ) ;
128
129
130/* ppArith.c */
131int mod ( int n, int p ) ;
132bigint power ( int x, int y ) ;
133int power_mod ( int a, int n, int p ) ;
134int is_primitive_root( int a, int p ) ;
135int inverse_mod_p ( int n, int p ) ;
136
137
138/* ppPolyArith.c */
139int eval_poly ( int * f, int x, int n, int p ) ;
140int linear_factor ( int * f, int n, int p ) ;
141int is_integer ( int * t, int n ) ;
142void construct_power_table( int power_table[][ MAXDEGPOLY ], int * f,
143 int n, int p ) ;
144int auto_convolve ( int * t, int k, int lower, int upper, int p ) ;
145int convolve ( int * s, int * t, int k, int lower, int upper, int p ) ;
146int coeff_of_square ( int * t, int k, int n, int p ) ;
147int coeff_of_product ( int * s, int * t, int k, int n, int p ) ;
148void square ( int * t, int power_table[][ MAXDEGPOLY ], int n, int p ) ;
149void product ( int * s, int * t, int power_table[][ MAXDEGPOLY ], int n, int p ) ;
150void times_x ( int * t, int power_table[][ MAXDEGPOLY ], int n, int p ) ;
151void x_to_power ( bigint m, int * g, int power_table[][ MAXDEGPOLY ], int n, int p ) ;
152
153
154/* ppFactor.c */
155int factor ( bigint n, bigint * primes, int * count ) ;
156int is_probably_prime ( int n, int x ) ;
157int is_almost_surely_prime( int n ) ;
158bigint EulerPhi ( bigint n ) ;
159
160
161/* ppHelperFunc.c */
162void initial_trial_poly ( int * f, int n ) ;
163void next_trial_poly ( int * f, int n, int p ) ;
164int const_coeff_test ( int * f, int n, int p, int a ) ;
165int const_coeff_is_primitive_root( int * f, int n, int p ) ;
166int skip_test ( int i, bigint * primes, int p ) ;
167void generate_Q_matrix ( int **q, int power_table[][ MAXDEGPOLY ], int n, int p ) ;
168int find_nullity ( int ** Q, int n, int p ) ;
169int has_multi_irred_factors ( int power_table[][ MAXDEGPOLY ], int n, int p ) ;
170
171
172
173/* pporder.c */
174int order_m ( int power_table[][ MAXDEGPOLY ], int n, int p, bigint r,
175 bigint * primes, int prime_count ) ;
176int order_r ( int power_table[][ MAXDEGPOLY ], int n, int p, bigint r, int * a ) ;
177int maximal_order( int * f, int n, int p ) ;
178
179#endif /* End of wrapper for header. */
