0
# Polynomial Operations
1

2
Univariate polynomial arithmetic over finite fields, including polynomial creation, arithmetic operations, factorization, and specialized polynomial generation functions for Conway, irreducible, and primitive polynomials.
3

4
## Capabilities
5

6
### Polynomial Class
7

8
Main polynomial class for univariate polynomials over finite fields with comprehensive arithmetic operations and utility methods.
9

10
```python { .api }
11
class Poly:
12
    """
13
    A univariate polynomial f(x) over GF(p^m).
14
    """
15
    
16
    def __init__(self, coeffs, field=None, order="desc"):
17
        """
18
        Create polynomial from coefficients.
19
        
20
        Parameters:
21
        - coeffs: Polynomial coefficients as array-like
22
        - field: Galois field class, defaults to GF(2) if None
23
        - order: Coefficient order - "desc" (default) for descending powers, "asc" for ascending
24
        """
25
    
26
    # Properties
27
    @property
28
    def field(self) -> type:
29
        """The Galois field the polynomial is defined over."""
30
    
31
    @property
32
    def degree(self) -> int:
33
        """The degree of the polynomial."""
34
    
35
    @property
36
    def coeffs(self) -> FieldArray:
37
        """The polynomial coefficients in descending order."""
38
    
39
    @property
40
    def nonzero_coeffs(self) -> FieldArray:
41
        """The non-zero coefficients."""
42
    
43
    @property
44
    def nonzero_degrees(self) -> np.ndarray:
45
        """The degrees with non-zero coefficients."""
46
    
47
    @property
48
    def integer(self) -> int:
49
        """Integer representation of the polynomial."""
50
    
51
    @property
52
    def string(self) -> str:
53
        """String representation of the polynomial."""
54
    
55
    # Arithmetic operations
56
    def __call__(self, at, field=None, elementwise=True):
57
        """
58
        Evaluate polynomial at given points.
59
        
60
        Parameters:
61
        - at: Points to evaluate at
62
        - field: Field for evaluation, uses polynomial's field if None
63
        - elementwise: Whether to evaluate elementwise
64
        
65
        Returns:
66
        Evaluation results
67
        """
68
    
69
    def derivative(self, k=1):
70
        """
71
        Compute k-th derivative of polynomial.
72
        
73
        Parameters:
74
        - k: Derivative order, default 1
75
        
76
        Returns:
77
        Poly: The k-th derivative
78
        """
79
    
80
    def reverse(self):
81
        """
82
        Reverse the coefficients of the polynomial.
83
        
84
        Returns:
85
        Poly: Polynomial with reversed coefficients
86
        """
87
    
88
    # Polynomial analysis
89
    def is_monic(self) -> bool:
90
        """Test if polynomial is monic (leading coefficient is 1)."""
91
    
92
    def is_primitive(self) -> bool:
93
        """Test if polynomial is primitive."""
94
    
95
    def is_irreducible(self) -> bool:
96
        """Test if polynomial is irreducible."""
97
    
98
    def is_square_free(self) -> bool:
99
        """Test if polynomial is square-free."""
100
    
101
    # Class methods for special polynomials
102
    @classmethod
103
    def Zero(cls, field=None):
104
        """
105
        Create zero polynomial.
106
        
107
        Parameters:
108
        - field: Galois field class
109
        
110
        Returns:
111
        Poly: Zero polynomial
112
        """
113
    
114
    @classmethod
115
    def One(cls, field=None):
116
        """
117
        Create constant polynomial f(x) = 1.
118
        
119
        Parameters:
120
        - field: Galois field class
121
        
122
        Returns:
123
        Poly: Unit polynomial
124
        """
125
    
126
    @classmethod
127
    def Identity(cls, field=None):
128
        """
129
        Create identity polynomial f(x) = x.
130
        
131
        Parameters:
132
        - field: Galois field class
133
        
134
        Returns:
135
        Poly: Identity polynomial
136
        """
137
    
138
    @classmethod
139
    def Random(cls, degree, field=None):
140
        """
141
        Create random polynomial of specified degree.
142
        
143
        Parameters:
144
        - degree: Polynomial degree
145
        - field: Galois field class
146
        
147
        Returns:
148
        Poly: Random polynomial
149
        """
150
    
151
    @classmethod
152
    def Int(cls, integer, field=None):
153
        """
154
        Create polynomial from integer representation.
155
        
156
        Parameters:
157
        - integer: Integer representation
158
        - field: Galois field class
159
        
160
        Returns:
161
        Poly: Polynomial from integer
162
        """
163
    
164
    @classmethod
165
    def Str(cls, string, field=None):
166
        """
167
        Create polynomial from string representation.
168
        
169
        Parameters:
170
        - string: String representation
171
        - field: Galois field class
172
        
173
        Returns:
174
        Poly: Polynomial from string
175
        """
176
```
177

178
### Conway Polynomials
179

180
Generate Conway polynomials for consistent field extensions and compatibility with mathematical software.
181

182
```python { .api }
183
def conway_poly(characteristic, degree):
184
    """
185
    Return Conway polynomial C_{p,n}(x) over GF(p).
186
    
187
    Conway polynomials provide a standard choice of irreducible polynomial
188
    for each extension field, ensuring compatibility between different
189
    implementations and mathematical software packages.
190
    
191
    Parameters:
192
    - characteristic (int): The characteristic p of the base field
193
    - degree (int): The degree n of the polynomial
194
    
195
    Returns:
196
    Poly: The Conway polynomial C_{p,n}(x)
197
    
198
    Raises:
199
    LookupError: If Conway polynomial is not available in database
200
    """
201
```
202

203
### Irreducible Polynomials
204

205
Generate irreducible polynomials over finite fields for creating field extensions.
206

207
```python { .api }
208
def irreducible_poly(field, degree, terms=None, method="min"):
209
    """
210
    Find irreducible polynomial of specified degree over finite field.
211
    
212
    Parameters:
213
    - field: The finite field class GF(p^m)
214
    - degree (int): Degree of desired irreducible polynomial
215
    - terms (int, optional): Number of terms in polynomial. If None, finds any irreducible.
216
    - method (str): Search method - "min" for minimal, "max" for maximal, "random" for random
217
    
218
    Returns:
219
    Poly: An irreducible polynomial of specified degree
220
    """
221

222
def irreducible_polys(field, degree, terms=None, reverse=False):
223
    """
224
    Iterate through all irreducible polynomials over finite field.
225
    
226
    Parameters:
227
    - field: The finite field class GF(p^m)  
228
    - degree (int): Degree of irreducible polynomials
229
    - terms (int, optional): Number of terms in polynomial. If None, finds all.
230
    - reverse (bool): Whether to iterate in reverse order
231
    
232
    Yields:
233
    Poly: Irreducible polynomials of specified degree
234
    """
235
```
236

237
### Primitive Polynomials
238

239
Generate primitive polynomials that produce primitive elements when used as irreducible polynomials.
240

241
```python { .api }
242
def primitive_poly(field, degree, terms=None, method="min"):
243
    """
244
    Find primitive polynomial of specified degree over finite field.
245
    
246
    A primitive polynomial generates the full multiplicative group
247
    when used as the irreducible polynomial for field extension.
248
    
249
    Parameters:
250
    - field: The finite field class GF(p^m)
251
    - degree (int): Degree of desired primitive polynomial
252
    - terms (int, optional): Number of terms in polynomial. If None, finds any primitive.
253
    - method (str): Search method - "min" for minimal, "max" for maximal, "random" for random
254
    
255
    Returns:
256
    Poly: A primitive polynomial of specified degree
257
    """
258

259
def primitive_polys(field, degree, terms=None, reverse=False):
260
    """
261
    Iterate through all primitive polynomials over finite field.
262
    
263
    Parameters:
264
    - field: The finite field class GF(p^m)
265
    - degree (int): Degree of primitive polynomials  
266
    - terms (int, optional): Number of terms in polynomial. If None, finds all.
267
    - reverse (bool): Whether to iterate in reverse order
268
    
269
    Yields:
270
    Poly: Primitive polynomials of specified degree
271
    """
272

273
def matlab_primitive_poly(characteristic, degree):
274
    """
275
    Return MATLAB-compatible primitive polynomial.
276
    
277
    Returns the same primitive polynomial that MATLAB's gfprimpolyy() function
278
    would return for the same parameters, ensuring compatibility.
279
    
280
    Parameters:
281
    - characteristic (int): The characteristic of the field
282
    - degree (int): The degree of the polynomial
283
    
284
    Returns:
285
    Poly: MATLAB-compatible primitive polynomial
286
    """
287
```
288

289
### Lagrange Interpolation
290

291
Construct interpolating polynomials through given points using Lagrange interpolation.
292

293
```python { .api }
294
def lagrange_poly(x, y):
295
    """
296
    Construct Lagrange interpolating polynomial.
297
    
298
    Find polynomial of minimal degree that passes through all given points.
299
    
300
    Parameters:
301
    - x: X-coordinates of interpolation points (field array)
302
    - y: Y-coordinates of interpolation points (field array)
303
    
304
    Returns:
305
    Poly: Lagrange interpolating polynomial
306
    
307
    Note: x and y must have same length and x values must be distinct
308
    """
309
```
310

311
## Usage Examples
312

313
### Basic Polynomial Operations
314

315
```python
316
import galois
317

318
# Create polynomials over GF(2)
319
p1 = galois.Poly([1, 0, 1])      # x^2 + 1
320
p2 = galois.Poly([1, 1])         # x + 1
321

322
# Arithmetic operations
323
p3 = p1 + p2  # Addition
324
p4 = p1 * p2  # Multiplication
325
p5 = p1 ** 3  # Exponentiation
326
q, r = divmod(p1, p2)  # Division with remainder
327

328
print(f"({p1}) * ({p2}) = {p4}")
329
print(f"({p1}) / ({p2}) = {q} remainder {r}")
330

331
# Polynomial evaluation
332
GF = galois.GF(2**4)
333
x_vals = GF([0, 1, 2, 3])
334
y_vals = p1(x_vals)
335
print(f"p1 evaluated at {x_vals} = {y_vals}")
336
```
337

338
### Working with Different Fields
339

340
```python
341
import galois
342

343
# Polynomials over GF(3^2)
344
GF9 = galois.GF(3**2)  
345
p = galois.Poly([1, 2, 0, 1], field=GF9)  # x^3 + 2x^2 + 1
346
print(f"Polynomial: {p}")
347
print(f"Degree: {p.degree}")
348
print(f"Field: {p.field.name}")
349

350
# Properties and analysis
351
print(f"Is monic: {p.is_monic()}")
352
print(f"Coefficients: {p.coeffs}")
353
print(f"Non-zero degrees: {p.nonzero_degrees}")
354
print(f"Non-zero coefficients: {p.nonzero_coeffs}")
355

356
# Derivatives
357
p_deriv = p.derivative()
358
p_deriv2 = p.derivative(2)
359
print(f"First derivative: {p_deriv}")
360
print(f"Second derivative: {p_deriv2}")
361
```
362

363
### Special Polynomial Generation
364

365
```python
366
import galois
367

368
# Conway polynomials for standard field extensions
369
conway = galois.conway_poly(2, 8)  # Conway polynomial for GF(2^8)
370
print(f"Conway polynomial C_{{2,8}}: {conway}")
371

372
# Irreducible polynomials
373
GF2 = galois.GF(2)
374
irreducible = galois.irreducible_poly(GF2, 4)
375
print(f"Irreducible polynomial: {irreducible}")
376

377
# All irreducible polynomials of degree 3
378
for poly in galois.irreducible_polys(GF2, 3):
379
    print(f"Irreducible: {poly}")
380

381
# Primitive polynomials
382
primitive = galois.primitive_poly(GF2, 4)  
383
print(f"Primitive polynomial: {primitive}")
384

385
# MATLAB-compatible primitive polynomial
386
matlab_prim = galois.matlab_primitive_poly(2, 4)
387
print(f"MATLAB primitive: {matlab_prim}")
388
```
389

390
### Lagrange Interpolation
391

392
```python
393
import galois
394

395
GF = galois.GF(7)
396

397
# Interpolation points
398
x = GF([1, 2, 3, 4])
399
y = GF([2, 5, 1, 6])
400

401
# Construct interpolating polynomial
402
interp_poly = galois.lagrange_poly(x, y)
403
print(f"Interpolating polynomial: {interp_poly}")
404

405
# Verify interpolation
406
for i in range(len(x)):
407
    result = interp_poly(x[i])
408
    print(f"f({x[i]}) = {result} (expected {y[i]})")
409
```
410

411
### Advanced Polynomial Analysis
412

413
```python
414
import galois
415

416
GF = galois.GF(2)
417

418
# Create polynomials for analysis
419
polys = [
420
    galois.Poly([1, 0, 1, 1], field=GF),     # x^3 + x + 1
421
    galois.Poly([1, 1, 0, 1], field=GF),     # x^3 + x^2 + 1  
422
    galois.Poly([1, 0, 0, 1], field=GF),     # x^3 + 1
423
]
424

425
for i, p in enumerate(polys):
426
    print(f"Polynomial {i+1}: {p}")
427
    print(f"  Is irreducible: {p.is_irreducible()}")
428
    print(f"  Is primitive: {p.is_primitive()}")
429
    print(f"  Is square-free: {p.is_square_free()}")
430
    print(f"  Integer form: {p.integer}")
431
    print()
432
```
433

434
## Performance Notes
435

436
- **Storage Optimization**: Uses sparse representation for polynomials with few non-zero terms
437
- **Field Integration**: Seamlessly works with all finite field classes created by GF()
438
- **Efficient Arithmetic**: Optimized polynomial multiplication and division algorithms
439
- **Database Lookup**: Conway polynomials use precomputed database for fast retrieval
440
- **Search Algorithms**: Efficient irreducible and primitive polynomial search methods