1/*==============================================================================
2|
3| NAME
4|
5| ppArith.hpp
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.3 - A Program for Computing Primitive Polynomials.
17| Copyright (C) 1999-2024 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
54class 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
103class 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
147template <typename UIntType, typename SIntType>
148class 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.
196template <typename IntType>
197class 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
231class 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
253class 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
285template <typename IntType> IntType gcd( const IntType & u, const IntType & v ) ;
286template <typename IntType> IntType addMod( IntType a, IntType b, IntType n ) ;
287template <typename IntType> IntType timesTwoMod( IntType a, IntType n ) ;
288template <typename IntType> IntType multiplyMod( const IntType a, const IntType b, const IntType n ) ;
289
290#endif // __PPARITH_H__
