1/*==============================================================================
2|
3| NAME
4|
5| ppPolynomial.hpp
6|
7| DESCRIPTION
8|
9| Header file for all the polynomial classes.
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 !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 __POLYNOMIAL_H__
40#define __POLYNOMIAL_H__
41
42/*=============================================================================
43|
44| NAME
45|
46| PolynomialError
47| PolynomialRangeError
48|
49| DESCRIPTION
50|
51| Exception classes for classes Polynomial and PolyMod
52| derived from the STL exception class runtime_error.
53|
54+============================================================================*/
55
56// General purpose exception for a polynomial.
57class PolynomialError : public runtime_error
58{
59 public:
60 // Throw with error message, file name and line number.
61 PolynomialError( const string & description, const string & file, const int & line )
62 : runtime_error( description + " in file " + file + " at line " + to_string(line) )
63 {
64 } ;
65
66 // Throw with an error message.
67 PolynomialError( const string & description )
68 : runtime_error( description )
69 {
70 } ;
71
72 // Throw with default error message.
73 PolynomialError()
74 : runtime_error( "Polynomial error: " )
75 {
76 } ;
77
78} ; // end class PolynomialError
79
80// Typically thrown when we parse a bad string which is not a proper polynomial.
81class PolynomialRangeError : public PolynomialError
82{
83 public:
84 // Throw with error message, file name and line number.
85 PolynomialRangeError( const string & description, const string & file, const int & line )
86 : PolynomialError( description + " in file " + file + " at line " + to_string(line) )
87 {
88 } ;
89
90 // Throw with an error message.
91 PolynomialRangeError( const string & description )
92 : PolynomialError( description )
93 {
94 } ;
95
96 // Throw with default error message.
97 PolynomialRangeError()
98 : PolynomialError( "Polynomial range error: " )
99 {
100 } ;
101
102} ; // end class PolynomialRangeError
103
104
105/*=============================================================================
106|
107| NAME
108|
109| Polynomial
110|
111| DESCRIPTION
112|
113| Represents the monic polynomial f( x ) of degree n, with
114| coefficients in GF( p ). Precisely,
115|
116| n n-1
117| f( x ) = x + a x + ... a x + a 0 <= a < p
118| n-1 1 0 i
119|
120| The constant polynomial is of degree 0.
121|
122| We support these basic operations:
123|
124| Polynomial f ; Construct f(x) = 0 mod 2.
125| <destructor>
126| Polynomial f( f2 ) ; Copy, f(x) = f2(x)
127| Polynomial f = f2 ; Overwrite, f(x) = f2(x)
128| Polynomial f( "x^2+1, 3" ) ; Polynomial from string.
129| String s = f ; Poly to string.
130| stream << p Read the poly.
131| p >> stream Print the poly.
132| p1 == p2, p1 != p2 Test for equality.
133| f[ i ] = coeff Set poly coefficient.
134| f.deg() Return the degree of f(x).
135| f.modulus() Return the modulus p of f(x).
136| int coeff = f[ i ] Get poly coefficient.
137| f(x) + g(x) Add poly mod p.
138| f(x) Evaluate f(x) for integer x
139| f.hasLinearFactor() Check if f(x) has any linear factors.
140| f.isInteger() Is f(x) = constant?
141| f.firstTrialPoly() Set f(x) = x^n - 1
142| f.nextTrialPoly() Set f(x) = next poly in sequence.
143|
144| Exceptions: throw PolynomialError or one of its subclasses such as
145| PolynomialRangeError.
146|
147| NOTES
148|
149| The member functions and friends are documented in ppPolynomial.cpp
150|
151+============================================================================*/
152
153class Polynomial
154{
155 public:
156 // Default constructor which sets f(x) = 0 modulo 2.
157 Polynomial() ;
158
159 // Constructor for a polynomial from a vector of integers.
160 explicit Polynomial( const vector<ppuint> ) ;
161
162 // Destructor.
163 virtual ~Polynomial() ;
164
165 // Copy constructor.
166 Polynomial( const Polynomial & g ) ;
167
168 // Assignment.
169 virtual Polynomial & operator=( const Polynomial & g ) ;
170
171 // String to polynomial assignment.
172 virtual Polynomial & operator=( string s ) ;
173
174 // Construct from string:
175 // Polynomial p( "x^2 + 2 x + 1, 3" ) ;
176 // If modulus isn't specified, use the one in specified in the
177 // polynomial string.
178 Polynomial( string s, ppuint p = 0 ) ;
179
180 // Operator casting to string type.
181 operator string() const ;
182
183 // Equality tests.
184 friend bool operator==( const Polynomial & p1, const Polynomial & p2 ) ;
185 friend bool operator!=( const Polynomial & p1, const Polynomial & p2 ) ;
186
187 // cout << p and cin >> p
188 friend ostream & operator<<( ostream & out, const Polynomial & p ) ;
189 friend istream & operator>>( istream & in, Polynomial & p ) ;
190
191 // Bounds checked indexing operator which allows an lvalue:
192 // p[ i ] = coeff ;
193 ppuint & operator[]( int i ) ;
194
195 // Bounds checked indexing operator for read only access:
196 // coeff = p[ i ] ;
197 const ppuint operator[]( int i ) const ;
198
199 // Return the degree n of f(x).
200 int deg() const ;
201
202 // Return the modulus p of f(x).
203 ppuint modulus() const ;
204
205 // Set the modulus p of f(x).
206 void setModulus( const ppuint p ) ;
207
208 // Addition modulo p: f(x) + g(x) mod p
209 friend const Polynomial operator+( const Polynomial & f, const Polynomial & g ) ;
210
211 // Addition.
212 Polynomial & operator+=( const Polynomial & g ) ;
213
214 // Scalar multiple.
215 friend const Polynomial
216 operator*( const Polynomial & f, const ppuint k ) ;
217
218 Polynomial & operator*=( const ppuint k ) ;
219
220 // Evaluation: f( x ) mod p
221 ppuint operator()( int x ) ;
222
223 // Does f(x) have any linear factor?
224 bool hasLinearFactor() ;
225
226 // Is f(x) an integer?
227 bool isInteger() const ;
228
229 // Only to show how we override a virtual function in C++. We actually don't need to define this function here in the base class.
230 virtual void initialTrialPoly( const ppuint n, const ppuint p )
231 { throw PolynomialError( "Trying to call initialTrialPoly() from Polynomial class instead of its child class TrialPolynomial", __FILE__, __LINE__ ) ;
232} ;
233
234 // Private data accessible by member functions only, and
235 // derived classes for convenience.
236 protected:
237 vector<ppuint> f_ ; // Polynomial coefficients:
238 // f_[0] = const coeff ... f_[n] = nth degree coeff.
239 // then f_.size() = n+1
240 int n_ ; // Degree of the polynomial.
241 ppuint p_ ; // Coefficients are in GF( p ).
242 ModP<ppuint,ppsint> mod ; // modulo p functionoid.
243} ;
244
245/*=============================================================================
246|
247| NAME
248|
249| TrialPolynomial
250|
251| DESCRIPTION
252|
253| Trial polynomial used in primitivity testing. Just a Polynomial with
254| a couple of functions to initialize and iterate over a sequence of
255| polynomials.
256|
257| NOTES
258|
259+============================================================================*/
260
261// final means a derived class won't be able to override any of the virtual
262// functions.
263class TrialPolynomial final : public Polynomial
264{
265 using Polynomial::Polynomial ; // Inherit all the base class constructors.
266
267 public:
268 // First trial polynomial. Set
269 // n
270 // f( x ) = x - 1
271 // override makes the compiler check the args AND the return type also
272 // to make sure there's an exact match to the base class function.
273 virtual void initialTrialPoly( const ppuint n, const ppuint p ) override ;
274
275 // Update f( x ) := next polynomial in sequence.
276 void nextTrialPoly() ;
277} ;
278
279/*=============================================================================
280|
281| NAME
282|
283| PolyMod
284|
285| DESCRIPTION
286|
287| Represents the monic polynomial g( x ) of degree m with coefficients in GF( p ),
288|
289| m m-1
290| g( x ) = x + a x + ... + a 0 <= a < p
291| m-1 0 i
292|
293| modulo f( x ) for monic polynomial f( x ) of degree n over GF( p ),
294|
295| n n-1
296| f( x ) = x + a x + ... + a 0 <= a < p
297| n-1 0 i
298|
299| We support these basic operations:
300|
301| PolyMod p() ; Set g(x)=0 and f(x) = 0 mod 2
302| Destructor.
303| PolyMod p( g, f ) Constructor from polynomials g(x) and f(x)
304| PolyMod p( p2 ) Copy p(x) = p2(x).
305| PolyMod p = p2 Assign p(x) = p2(x).
306| p.timesX() ; p(x) := x p( x ) (mod f( x ), p)
307| 2
308| p.square() ; p(x) := p( x ) (mod f( x ), p)
309| p *= p2 Do p(x) = p(x) * p2(x) (mod f( x ), p)
310| p1 * p2 Do p1(x) * p2(x) (mod f( x ), p)
311| m
312| p.power( m ) p(x) = x (mod f(x), p)
313|
314| Exceptions: throw PolynomialError or one of its subclasses such as
315| PolynomialRangeError.
316|
317| NOTES
318|
319| The member functions and friends are documented in ppPolynomial.hpp
320|
321+============================================================================*/
322
323// Friends of PolyMod
324ppuint autoConvolve( const Polynomial & t, const int k, const int lower, const int upper ) ;
325
326ppuint coeffOfSquare( const Polynomial & g, const int k, const int n ) ;
327
328ppuint coeffOfProduct( const Polynomial & s, const Polynomial & t, const int k, const int n ) ;
329
330ppuint convolve( const Polynomial & s, const Polynomial & t, const int k, const int lower, const int upper ) ;
331
332class PolyMod
333{
334 public:
335 // Set g( x ) = 0 modulo f(x) = 0 and p = 2
336 PolyMod() ;
337
338 // Destructor.
339 virtual ~PolyMod() ;
340
341 // Construct from polynomials g(x) and f(x).
342 PolyMod( const Polynomial & g, const Polynomial & f ) ;
343
344 // Construct from string g and polynomial f(x).
345 PolyMod( const string & g, const Polynomial & f ) ;
346
347 // Operator casting g(x) to string type.
348 operator string() const ;
349
350 // cout << p prints g(x) to output stream
351 friend ostream & operator<<( ostream & out, const PolyMod & p ) ;
352
353 // Copy g( x ) = g2( x ).
354 PolyMod( const PolyMod & g2 ) ;
355
356 // Assign g( x ) = g2( x )
357 virtual PolyMod & operator=( const PolyMod & g2 ) ;
358
359 // Bounds checked indexing operator for read only access:
360 // coeff = p[ i ] ;
361 const ppuint operator[]( int i ) const ;
362
363 // Multiply by x: g(x) := g(x) x (mod f( x ), p)
364 void timesX() ;
365
366 // Squaring: 2
367 // g(x) := g(x) (mod f( x ), p)
368 void square() ;
369
370 // Multiplication: g(x) := g(x) g2(x) (mod f( x ), p)
371 PolyMod & operator*=( const PolyMod & g2 ) ;
372
373 // Multiplication: g(x) := s(x) t(x) (mod f( x ), p)
374 friend const PolyMod operator*( const PolyMod & s, const PolyMod & t ) ;
375
376 // Special exponentiation: g(x) ^ m (mod f(x), p)
377 // for g(x) = x only for now!
378 friend const PolyMod power( const PolyMod & g, const BigInt & m ) ;
379
380 bool isInteger() const ;
381
382 //-----------------< Helper functions >-------------------------------
383 const Polynomial getf() const ;
384
385 const ppuint getModulus() const ;
386
387
388 private:
389 // Polynomial g(x).
390 Polynomial g_ ;
391
392 // Modulus polynomial f(x) and modulus p.
393 Polynomial f_ ;
394
395 // Two dimensional precomputed power table.
396 //
397 // Precompute the n-1 polynomials
398 //
399 // n 2n-2
400 // x ... x (mod f(x), p)
401 //
402 // n+i
403 // powerTable_[ i ] = x (mod f(x), p)
404 //
405 vector<Polynomial> powerTable_ ;
406
407 ModP<ppuint,ppsint> mod ; // modulo p functionoid.
408
409 // Helper functions. Note the friend functions are really public due to C++ rules.
410 protected:
411 // Offset into powerTable.
412 int inline offset( const int i ) const { return i - f_.deg() ; }
413
414 // Power table of the polynomial.
415 void constructPowerTable() ;
416
417 // Reduce g( x ) mod f( x ) and p
418 void modf() ;
419
420 // Autoconvolution product.
421 friend ppuint autoConvolve( const Polynomial & t, const int k, const int lower, const int upper ) ;
422
423 // Convolution product.
424 friend ppuint convolve( const Polynomial & s, const Polynomial & t,
425 const int k, const int lower, const int upper ) ;
426
427 // 2
428 // kth coeff of g (x) for degree n.
429 friend ppuint coeffOfSquare( const Polynomial & g, const int k, const int n ) ;
430
431 // Coeff of s(x) t(x) for degree n.
432 friend ppuint coeffOfProduct( const Polynomial & s, const Polynomial & t, const int k, const int n ) ;
433} ;
434
435
436
437/*=============================================================================
438|
439| NAME
440|
441| PolyOrder
442|
443| DESCRIPTION
444|
445| Order tests on the monic polynomial f( x ) of degree n,
446| with coefficients in GF( p ).
447|
448| n n-1
449| f( x ) = x + a x + ... + a 0 <= a < p
450| n-1 0 i
451|
452| Exceptions: throw PolynomialError or one of its subclasses such as
453| PolynomialRangeError.
454|
455| NOTES
456|
457| The member functions and friends are documented in ppPolynomial.hpp
458|
459+============================================================================*/
460
461class PolyOrder
462{
463 public:
464 // Do tests on the nth degree polynomial f(x) modulo p.
465 explicit PolyOrder( const Polynomial & f ) ;
466
467 // n
468 // p - 1
469 // Compute r = -------- and factor r into the product of primes
470 // p - 1
471 void factorR() ;
472
473 void computeMaxNumPoly() ;
474
475 void computeNumPrimPoly() ;
476
477 void resetPolynomial( const Polynomial &f ) ;
478
479 // m r
480 // Check that x (mod f(x), p) is not an integer for m = ---
481 // p
482 // i
483 // but skip this test if p | (p-1).
484 // i
485 bool orderM() ;
486
487 // r
488 // Check if x (mod f(x), p) = a, for integer a.
489 // If a is not an integer, return 0.
490 ppuint orderR() ;
491
492 // k n
493 // Check if x = 1 (mod f(x), p) only for k = p - 1
494 // Note this is O( p^n ); very expensive.
495 bool maximal_order() ;
496
497 // Check if the monic polynomial f( x ) has 2 or more distinct factors.
498 // Uses x_to_power().
499 bool hasMultipleDistinctFactors( bool earlyOut = true ) ;
500
501 inline BigInt getR() const { return r_ ; } ;
502
503 inline BigInt getNumPrimPoly() const { return num_prim_poly_ ; } ;
504
505 inline BigInt getMaxNumPoly() const { return max_num_poly_ ; } ;
506
507 // Test if a given polynomial f(x) is primitive.
508 bool isPrimitive() ;
509
510 // Test function.
511 string printQMatrix() const ;
512
513 inline int getNullity() const { return nullity_ ; } ;
514
515 inline Factorization<BigInt> getFactorsOfR() const { return factors_of_R_ ; }
516
517 // Allow direct access to this simple data type for convenience.
518 public:
519 OperationCount statistics_ ;
520
521 protected:
522 // Polynomial f(x) modulo p of degree n which is to be tested.
523 Polynomial f_ ;
524 ppuint n_ ;
525 ppuint p_ ;
526 ModP<ppuint,ppsint> mod ;
527
528 // n
529 // p - 1
530 BigInt p_to_n_minus_1_ ;
531
532 // n
533 // p - 1
534 // r = -------
535 // p - 1
536 BigInt r_ ;
537
538 // Constant factor a (see notes).
539 ppuint a_ ;
540
541 // n
542 // Factorization of p - 1
543 Factorization<BigInt> factors_of_p_to_n_minus_1_ ;
544
545 // Factorization of r.
546 Factorization<BigInt> factors_of_R_ ;
547
548 // Number of possible primitive polynomials.
549 BigInt num_prim_poly_ ;
550
551 // Total number of possible polynomials.
552 BigInt max_num_poly_ ;
553
554 // Two dimensional Q matrix for irreducibility testing.
555 vector< vector<ppsint> > Q_ ;
556
557 int nullity_ ;
558
559 // Helper functions.
560 protected:
561 void generateQMatrix() ;
562
563 void findNullity( bool earlyOut = true ) ;
564
565} ;
566
567#endif // __POLYNOMIAL_H__ --- End of wrapper for header file.
