1 /*==============================================================================
  2 |
  3 |  NAME
  4 |
  5 |     ppArith.h
  6 |
  7 |  DESCRIPTION
  8 |
  9 |     Header file for miscellaneous integer multiple precision math routines.
 10 |
 11 |     User manual and technical documentation are described in detail in my web page at
 12 |     http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html
 13 |
 14 |  LEGAL
 15 |
 16 |     Primpoly Version 16.1 - A Program for Computing Primitive Polynomials.
 17 |     Copyright (C) 1999-2021 by Sean Erik O'Connor.  All Rights Reserved.
 18 |
 19 |     This program is free software: you can redistribute it and/or modify
 20 |     it under the terms of the GNU General Public License as published by
 21 |     the Free Software Foundation, either version 3 of the License, or
 22 |     (at your option) any later version.
 23 |
 24 |     This program is distributed in the hope that it will be useful,
 25 |     but WITHOUT ANY WARRANTY; without even the implied warranty of
 26 |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 27 |     GNU General Public License for more details.
 28 |
 29 |     You should have received a copy of the GNU General Public License
 30 |     along with this program.  If not, see http://www.gnu.org/licenses/.
 31 |     
 32 |     The author's address is seanerikoconnor!AT!gmail!DOT!com
 33 |     with the !DOT! replaced by . and the !AT! replaced by @
 34 |
 35 ==============================================================================*/
 36 
 37 // Wrap this header file to prevent duplication if it is included
 38 // accidentally more than once.
 39 #ifndef __PPARITH_H__
 40 #define __PPARITH_H__
 41 
 42 /*=============================================================================
 43 |
 44 | NAME
 45 |
 46 |     ArithModPException
 47 |
 48 | DESCRIPTION
 49 |
 50 |     Helper class for exceptions thrown by ArithModP.
 51 |
 52 +============================================================================*/
 53 
 54 class ArithModPError : public runtime_error
 55 {
 56     public:
 57         // Throw with error message, file name and line number.
 58         ArithModPError( const string & description, const string & file, const int & line )
 59         : runtime_error( description + " in file " + file + " at line " + to_string(line) )
 60         {
 61         } ;
 62 
 63         // Throw with error message.
 64         ArithModPError( const string & description )
 65             : runtime_error( description )
 66         {
 67         } ;
 68 
 69         // Throw with no error message.
 70         ArithModPError()
 71             : runtime_error( "ArithModP exception:  " )
 72         {
 73         } ;
 74 
 75 } ; // end class ArithModPError
 76 
 77 
 78 /*=============================================================================
 79 |
 80 | NAME
 81 |
 82 |     ArithModP
 83 |
 84 | DESCRIPTION
 85 |
 86 |     Abstract classes for modulo p arithmetic operations on integers.
 87 |
 88 |     ppuint p{ 2 ;
 89 |     ppuint n{ 4 } ;
 90 |     ppuint a0{ 14 } ;
 91 |     ArithModP modp( p ) ;
 92 |     modp.constCoeffIsPrimitiveRoot( a0, n ) ;
 93 |
 94 | NOTES
 95 |
 96 |     Use the functionoid approach so we can (1) save state and (2) have
 97 |     a function interface.
 98 |     The member functions and friends are documented in detail ppArith.cpp
 99 |     Prevent implicity integer type conversion with "explicit".
100 |
101 +============================================================================*/
102 
103 class ArithModP
104 {
105     public:
106         ArithModP() : p_( 2 ) {} ;
107         explicit ArithModP( ppuint p ) : p_( p ) {} ;
108 
109         bool constCoeffTest( ppsint a, ppsint a0, int n ) ;
110         bool constCoeffIsPrimitiveRoot( ppuint a0, int n ) ;
111 
112     protected:
113         ppuint p_ ;    // Modulus for all arithmetic operations.
114 
115     private:
116         // Don't let anyone define the default constructor,
117         // copy constructor or assignment
118         // operator for this class.
119         ArithModP( const ArithModP & ) ;
120         ArithModP & operator=( const ArithModP & ) ;
121 } ;
122 
123 
124 
125 /*=============================================================================
126 |
127 | NAME
128 |
129 |     ModP
130 |
131 | DESCRIPTION
132 |
133 |     Abstract classes for modulo p arithmetic operations on integers.
134 |
135 |     ppuint p{ 7 } ;
136 |     ModP modp( p ) ;                   // Set p = 7 for all subsequent operations.
137 |     ppuint rem_33_mod_7 = modp( 33 ) ; // Use as a functionoid.
138 |
139 | NOTES
140 |
141 |     Use the functionoid approach so we can (1) save state and (2) have
142 |     a function interface.
143 |     The member functions and friends are documented in detail ppArith.cpp
144 |
145 +============================================================================*/
146 
147 template <typename UIntType, typename SIntType>
148 class ModP
149 {
150     public:
151         explicit ModP( UIntType p )
152         {
153             p_ = p ;
154         } ;
155 
156         ModP( const ModP & mod )
157               : p_( mod.p_ )
158         {
159         }
160 
161         void set( UIntType p )
162         {
163             p_ = p ;
164         }
165 
166         UIntType operator()( SIntType n ) ;
167 
168     protected:
169         UIntType p_ ;    // Modulus for all arithmetic operations.
170 } ;
171 
172 
173 /*=============================================================================
174 |
175 | NAME
176 |
177 |     PowerMod
178 |
179 | DESCRIPTION
180 |
181 |     Abstract classes for modulo p arithmetic operations on integers.
182 |
183 |     ppuint p{ 7 } ;
184 |     PowerMod power_mod( p ) ;
185 |     ppuint threeToTheTenthmodp = power_mod( 3, 10 ) ;   // Use as a functionoid.
186 |
187 | NOTES
188 |
189 |     Use the functionoid approach so we can (1) save state and (2) have
190 |     a function interface.
191 |     The member functions and friends are documented in detail ppArith.cpp
192 |
193 +============================================================================*/
194 
195 // Generic class.
196 template <typename IntType>
197 class PowerMod
198 {
199     public:
200         explicit PowerMod( const IntType & p ) : p_( p ) {} ;
201 
202         IntType operator()( const IntType & a, const IntType & n ) ;
203 
204     protected:
205         IntType p_ ;    // Modulus for all arithmetic operations.
206 } ;
207 
208 
209 /*=============================================================================
210 |
211 | NAME
212 |
213 |     InverseModP
214 |
215 | DESCRIPTION
216 |
217 |     Abstract classes for modulo p arithmetic operations on integers.
218 |
219 |     InverseModP modp( p ) ;           // Set p = 7 for all subsequent operations.
220 |     ppuint sevenmodp = modp( 33 ) ;   // Use as a functionoid.
221 |
222 |
223 | NOTES
224 |
225 |     Use the functionoid approach so we can (1) save state and (2) have
226 |     a function interface.
227 |     The member functions and friends are documented in detail ppArith.cpp
228 |
229 +============================================================================*/
230 
231 class InverseModP
232 {
233       public:
234          explicit InverseModP( ppuint p ) { p_ = p ; } ;
235          ppsint operator()( ppsint a ) ;
236 
237     protected:
238         ppuint p_ ;    // Modulus for all arithmetic operations.
239 } ;
240 
241 
242 /*=============================================================================
243  | 
244  | NAME
245  | 
246  | 
247  | 
248  | DESCRIPTION
249  | 
250  | 
251  +============================================================================*/
252 
253 class IsPrimitiveRoot
254 {
255     public:
256         explicit IsPrimitiveRoot( ppuint p )
257         {
258             p_ = p ;
259         } ;
260 
261         bool operator()( ppuint a ) ;
262 
263     protected:
264         ppuint p_ ;    // Modulus for all arithmetic operations.
265 } ;
266 
267 
268 
269 /*=============================================================================
270 |
271 | NAME
272 |
273 |     Stand alone generic IntType functions:
274 |         gcd
275 |         addMod
276 |         timesTwoMod
277 |         multiplyMod
278 |
279 | DESCRIPTION
280 |
281 |     GCD of nonnegative integer types.
282 |
283 +============================================================================*/
284 
285 template <typename IntType> IntType gcd( const IntType & u, const IntType & v ) ;
286 template <typename IntType> IntType addMod(      IntType a,             IntType b,       IntType n ) ;
287 template <typename IntType> IntType timesTwoMod( IntType a,                              IntType n ) ;
288 template <typename IntType> IntType multiplyMod( const IntType a, const IntType b, const IntType n ) ;
289 
290 #endif // __PPARITH_H__