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.1 - A Program for Computing Primitive Polynomials. 20 | Copyright (C) 1999-2021 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 artificer!AT!seanerikoconnor!DOT!freeservers!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 54 DESCRIPTION 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 62 INPUT 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 71 RETURNS 72 73 YES if all tests are passed. 74 NO if any one test fails. 75 76 EXAMPLE 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 91 METHOD 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 96 BUGS 97 98 None. 99 100 -------------------------------------------------------------------------------- 101 | Function Call | 102 ------------------------------------------------------------------------------*/ 103 104 int 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 113 int 114 i, /* Loop counter. */ 115 g[ MAXDEGPOLY ] ; /* g(x) = x ^ m (mod f(x), p) */ 116 117 bigint 118 m ; /* Exponent of m. */ 119 120 /*------------------------------------------------------------------------------ 121 | Function Body | 122 ------------------------------------------------------------------------------*/ 123 124 for (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 143 return( YES ) ; 144 145 } /* ====================== end of function order_m ========================= */ 146 147 148 149 /*============================================================================== 150 | order_r | 151 ================================================================================ 152 153 DESCRIPTION 154 r 155 Check if x (mod f(x), p) = a, where a is an integer. 156 157 INPUT 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 165 RETURNS 166 167 YES if the formula above is true. 168 NO if it isn't. 169 170 EXAMPLE 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 176 METHOD 177 r 178 First compute g(x) = x (mod f(x), p). 179 Then test if g(x) is a constant polynomial, 180 181 BUGS 182 183 None. 184 185 -------------------------------------------------------------------------------- 186 | Function Call | 187 ------------------------------------------------------------------------------*/ 188 189 int 190 order_r( int power_table[][ MAXDEGPOLY ], int n, int p, bigint r, int * a ) 191 { 192 193 /*------------------------------------------------------------------------------ 194 | Local Variables | 195 ------------------------------------------------------------------------------*/ 196 197 int 198 g[ MAXDEGPOLY ] ; /* g(x) = x ^ m (mod f(x), p) */ 199 200 /*------------------------------------------------------------------------------ 201 | Function Body | 202 ------------------------------------------------------------------------------*/ 203 204 x_to_power( r, g, power_table, n, p ) ; 205 206 #ifdef DEBUG_PP_PRIMPOLY 207 printf( " order r test for x^r = x ^ %lld = ", r ) ; 208 write_poly( g, n-1 ) ; 209 printf( "\n\n" ); 210 #endif 211 212 /* Return the value a = constant term of g(x) */ 213 *a = g[ 0 ] ; 214 215 return( is_integer( g, n-1 ) ? YES : NO ) ; 216 217 } /* ====================== end of function order_r ========================= */ 218 219 220 221 /*============================================================================== 222 | maximal_order | 223 ================================================================================ 224 225 DESCRIPTION 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 230 INPUT 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 236 RETURNS 237 238 YES if f( x ) is primitive. 239 NO if it isn't. 240 241 EXAMPLE 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 252 METHOD 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 261 BUGS 262 263 None. 264 265 -------------------------------------------------------------------------------- 266 | Function Call | 267 ------------------------------------------------------------------------------*/ 268 269 int 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 ======================== */
