1/*==============================================================================
2|
3| File Name:
4|
5| ppOrder.c
6|
7| Description:
8|
9| Routines for testing the order of polynomials.
10|
11| Functions:
12|
13| order_m
14| order_r
15| maximal_order
16|
17| LEGAL
18|
19| Primpoly Version 16.4 - A Program for Computing Primitive Polynomials.
20| Copyright (C) 1999-2025 by Sean Erik O'Connor. All Rights Reserved.
21|
22| This program is free software: you can redistribute it and/or modify
23| it under the terms of the GNU General Public License as published by
24| the Free Software Foundation, either version 3 of the License, or
25| (at your option) any later version.
26|
27| This program is distributed in the hope that it will be useful,
28| but WITHOUT ANY WARRANTY; without even the implied warranty of
29| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30| GNU General Public License for more details.
31|
32| You should have received a copy of the GNU General Public License
33| along with this program. If not, see <http://www.gnu.org/licenses/>.
34|
35| The author's address is seanerikoconnor!AT!gmail!DOT!com
36| with !DOT! replaced by . and the !AT! replaced by @
37|
38==============================================================================*/
39
40/*------------------------------------------------------------------------------
41| Include Files |
42------------------------------------------------------------------------------*/
43
44#include <stdio.h>
45#include <stdlib.h> /* for rand() function */
46
47#include "Primpoly.h"
48
49
50/*==============================================================================
51| order_m |
52================================================================================
53
54DESCRIPTION
55 m
56 Check that x (mod f(x), p) is not an integer for m = r / p but skip
57 n i
58 p - 1
59 this test if p | (p-1). Recall r = -------.
60 i p - 1
61
62INPUT
63
64 power_table (int **) x ^ k (mod f(x), p) for n <= k <= 2n-2, f monic.
65 n (int, n >= 1) Degree of f(x).
66 p (int) Modulo p coefficient arithmetic.
67 r (int) See above.
68 primes (bigint *) Distinct prime factors of r.
69 prime_count Number of primes.
70
71RETURNS
72
73 YES if all tests are passed.
74 NO if any one test fails.
75
76EXAMPLE
77 2
78 Let n = 4 and p = 5. Then r = 156 = 2 * 3 * 13, and p = 2, p = 3,
79 1 2
80 and p = 13. m = { 156/2, 156/3, 156/13 } = { 78, 52, 12 }. We can
81 3
82 skip the test for m = 78 because p = 2 divides p-1 = 4. Exponentiation
83 1
84 52 3 2 12
85 gives x = 2 x + x + 4 x, which is not an integer and x =
86 3 2
87 4 x + 2 x + 4 x + 3 which is not an integer either, so we return
88
89 YES.
90
91METHOD
92
93 Exponentiate x with x_to_power and test the result with is_integer.
94 Return right away if the result is not an integer.
95
96BUGS
97
98 None.
99
100--------------------------------------------------------------------------------
101| Function Call |
102------------------------------------------------------------------------------*/
103
104int
105 order_m( int power_table[][ MAXDEGPOLY ], int n, int p, bigint r,
106 bigint * primes, int prime_count )
107{
108
109/*------------------------------------------------------------------------------
110| Local Variables |
111------------------------------------------------------------------------------*/
112
113int
114 i, /* Loop counter. */
115 g[ MAXDEGPOLY ] ; /* g(x) = x ^ m (mod f(x), p) */
116
117bigint
118 m ; /* Exponent of m. */
119
120/*------------------------------------------------------------------------------
121| Function Body |
122------------------------------------------------------------------------------*/
123
124for (i = 0 ; i <= prime_count ; ++i)
125
126 if (!skip_test( i, primes, p ))
127 {
128 m = r / primes[ i ] ;
129
130 x_to_power( m, g, power_table, n, p ) ;
131
132 #ifdef DEBUG_PP_PRIMPOLY
133 printf( " order m test for prime = %lld, x^ m = x ^ %lld = ", primes[i], m ) ;
134 write_poly( g, n-1 ) ;
135 printf( "\n\n" );
136 #endif
137
138 if (is_integer( g, n-1 ))
139
140 return( NO ) ;
141 }
142
143return( YES ) ;
144
145} /* ====================== end of function order_m ========================= */
146
147
148
149/*==============================================================================
150| order_r |
151================================================================================
152
153DESCRIPTION
154 r
155 Check if x (mod f(x), p) = a, where a is an integer.
156
157INPUT
158
159 power_table (int **) x ^ k (mod f(x), p) for n <= k <= 2n-2, f monic.
160 n (int, n >= 1) Degree of f(x).
161 p (int) Modulo p coefficient arithmetic.
162 r (int) See above.
163 a (int *) Pointer to value of a.
164
165RETURNS
166
167 YES if the formula above is true.
168 NO if it isn't.
169
170EXAMPLE
171 4 2
172 Let r = 156, f(x) = x + x + 2 x + 3, n = 4 and p = 5. It turns
173 156 4
174 out that x = 3 (mod f(x), 5) = (-1) * 3, so we return YES.
175
176METHOD
177 r
178 First compute g(x) = x (mod f(x), p).
179 Then test if g(x) is a constant polynomial,
180
181BUGS
182
183 None.
184
185--------------------------------------------------------------------------------
186| Function Call |
187------------------------------------------------------------------------------*/
188
189int
190 order_r( int power_table[][ MAXDEGPOLY ], int n, int p, bigint r, int * a )
191{
192
193/*------------------------------------------------------------------------------
194| Local Variables |
195------------------------------------------------------------------------------*/
196
197int
198 g[ MAXDEGPOLY ] ; /* g(x) = x ^ m (mod f(x), p) */
199
200/*------------------------------------------------------------------------------
201| Function Body |
202------------------------------------------------------------------------------*/
203
204x_to_power( r, g, power_table, n, p ) ;
205
206#ifdef DEBUG_PP_PRIMPOLY
207printf( " order r test for x^r = x ^ %lld = ", r ) ;
208write_poly( g, n-1 ) ;
209printf( "\n\n" );
210#endif
211
212/* Return the value a = constant term of g(x) */
213*a = g[ 0 ] ;
214
215return( is_integer( g, n-1 ) ? YES : NO ) ;
216
217} /* ====================== end of function order_r ========================= */
218
219
220
221/*==============================================================================
222| maximal_order |
223================================================================================
224
225DESCRIPTION
226 k n
227 Check if x = 1 (mod f(x), p) only when k = p - 1 and not for any smaller
228 power of k, i.e. that f(x) is a primitive polynomial.
229
230INPUT
231
232 f (int *) Monic polynomial f(x).
233 n (int, n >= 1) Degree of f(x).
234 p (int) Modulo p coefficient arithmetic.
235
236RETURNS
237
238 YES if f( x ) is primitive.
239 NO if it isn't.
240
241EXAMPLE
242
243 4
244 f( x ) = x + x + 1 is a primitive polynomial modulo p = 2,
245 4
246 because it generates the group GF( 2 ) with the exception of
247 2 15
248 zero. The powers {x, x , ... , x } modulo f(x), mod 2 are
249 16 4
250 distinct and not equal to 1 until x (mod x + x + 1, 2) = 1.
251
252METHOD
253
254 Confirm f(x) is primitive using the definition of primitive
255 polynomial as a generator of the Galois group
256 n n
257 GF( p ) by testing that p - 1 is the smallest power for which
258 k
259 x = 1 (mod f(x), p).
260
261BUGS
262
263 None.
264
265--------------------------------------------------------------------------------
266| Function Call |
267------------------------------------------------------------------------------*/
268
269int maximal_order( int * f, int n, int p )
270{
271 int g[ MAXDEGPOLY ] ; /* g(x) = x ^ m (mod f(x), p) */
272 bigint maxOrder ;
273 bigint k ;
274 int power_table[ MAXDEGPOLY - 1 ] [ MAXDEGPOLY ] ; /* x ^ n , ... , x ^ 2n-2 (mod f(x), p) */
275
276 /* n 2n-2
277 Precompute the powers x , ..., x (mod f(x), p)
278 for use in all later computations.
279 */
280 construct_power_table( power_table, f, n, p ) ;
281
282 /* Highest possible order for x. */
283 maxOrder = power( p, n ) - 1 ;
284
285 for (k = 1 ; k <= maxOrder ; ++k)
286 {
287 x_to_power( k, g, power_table, n, p ) ;
288
289 if (is_integer( g, n-1 ) &&
290 g[0] == 1 &&
291 k < maxOrder)
292 {
293 return 0 ;
294 }
295
296 } /* end for k */
297
298 return 1 ;
299
300} /* ================= end of function maximal_order ======================== */
