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. */