Annotation of OpenXM_contrib2/asir2018/engine/gfs.c, Revision 1.1
1.1 ! noro 1: /*
! 2: * Copyright (c) 1994-2000 FUJITSU LABORATORIES LIMITED
! 3: * All rights reserved.
! 4: *
! 5: * FUJITSU LABORATORIES LIMITED ("FLL") hereby grants you a ligfsted,
! 6: * non-exclusive and royalty-free license to use, copy, modify and
! 7: * redistribute, solely for non-commercial and non-profit purposes, the
! 8: * computer program, "Risa/Asir" ("SOFTWARE"), subject to the terms and
! 9: * conditions of this Agreement. For the avoidance of doubt, you acquire
! 10: * only a ligfsted right to use the SOFTWARE hereunder, and FLL or any
! 11: * third party developer retains all rights, including but not ligfsted to
! 12: * copyrights, in and to the SOFTWARE.
! 13: *
! 14: * (1) FLL does not grant you a license in any way for commercial
! 15: * purposes. You may use the SOFTWARE only for non-commercial and
! 16: * non-profit purposes only, such as acadegfsc, research and internal
! 17: * business use.
! 18: * (2) The SOFTWARE is protected by the Copyright Law of Japan and
! 19: * international copyright treaties. If you make copies of the SOFTWARE,
! 20: * with or without modification, as pergfstted hereunder, you shall affix
! 21: * to all such copies of the SOFTWARE the above copyright notice.
! 22: * (3) An explicit reference to this SOFTWARE and its copyright owner
! 23: * shall be made on your publication or presentation in any form of the
! 24: * results obtained by use of the SOFTWARE.
! 25: * (4) In the event that you modify the SOFTWARE, you shall notify FLL by
! 26: * e-mail at risa-adgfsn@sec.flab.fujitsu.co.jp of the detailed specification
! 27: * for such modification or the source code of the modified part of the
! 28: * SOFTWARE.
! 29: *
! 30: * THE SOFTWARE IS PROVIDED AS IS WITHOUT ANY WARRANTY OF ANY KIND. FLL
! 31: * MAKES ABSOLUTELY NO WARRANTIES, EXPRESSED, IMPLIED OR STATUTORY, AND
! 32: * EXPRESSLY DISCLAIMS ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS
! 33: * FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT OF THIRD PARTIES'
! 34: * RIGHTS. NO FLL DEALER, AGENT, EMPLOYEES IS AUTHORIZED TO MAKE ANY
! 35: * MODIFICATIONS, EXTENSIONS, OR ADDITIONS TO THIS WARRANTY.
! 36: * UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, TORT, CONTRACT,
! 37: * OR OTHERWISE, SHALL FLL BE LIABLE TO YOU OR ANY OTHER PERSON FOR ANY
! 38: * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, PUNITIVE OR CONSEQUENTIAL
! 39: * DAMAGES OF ANY CHARACTER, INCLUDING, WITHOUT LIMITATION, DAMAGES
! 40: * ARISING OUT OF OR RELATING TO THE SOFTWARE OR THIS AGREEMENT, DAMAGES
! 41: * FOR LOSS OF GOODWILL, WORK STOPPAGE, OR LOSS OF DATA, OR FOR ANY
! 42: * DAMAGES, EVEN IF FLL SHALL HAVE BEEN INFORMED OF THE POSSIBILITY OF
! 43: * SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. EVEN IF A PART
! 44: * OF THE SOFTWARE HAS BEEN DEVELOPED BY A THIRD PARTY, THE THIRD PARTY
! 45: * DEVELOPER SHALL HAVE NO LIABILITY IN CONNECTION WITH THE USE,
! 46: * PERFORMANCE OR NON-PERFORMANCE OF THE SOFTWARE.
! 47: *
! 48: * $OpenXM$
! 49: */
! 50: #include "ca.h"
! 51: #include "inline.h"
! 52:
! 53: /* q = p^n */
! 54:
! 55: P current_gfs_ext;
! 56: int current_gfs_p;
! 57: int current_gfs_q;
! 58: int current_gfs_q1;
! 59: int *current_gfs_plus1;
! 60: int *current_gfs_ntoi;
! 61: int *current_gfs_iton;
! 62:
! 63: struct prim_root_info {
! 64: int p;
! 65: int extdeg;
! 66: int defpoly;
! 67: int prim_root;
! 68: };
! 69:
! 70: /* if p >= SF_THRESHOLD, usual representation is used */
! 71:
! 72: #define SF_THRESHOLD 16384
! 73:
! 74: struct prim_root_info prim_root_info_tab[] = {
! 75: {2,1,0,0}, {2,2,7,2}, {2,3,11,2}, {2,4,19,2}, {2,5,37,2}, {2,6,67,2},
! 76: {2,7,131,2}, {2,8,283,3}, {2,9,515,7}, {2,10,1033,2}, {2,11,2053,2},
! 77: {2,12,4105,3}, {2,13,8219,2}, {2,14,16417,7}, {2,15,32771,2}, {3,1,0,2},
! 78: {3,2,10,4}, {3,3,34,3}, {3,4,86,3}, {3,5,250,3}, {3,6,734,3}, {3,7,2198,5},
! 79: {3,8,6572,38}, {3,9,19747,3}, {3,10,59068,34}, {5,1,0,2}, {5,2,27,6},
! 80: {5,3,131,9}, {5,4,627,6}, {5,5,3146,10}, {5,6,15632,5}, {7,1,0,3},
! 81: {7,2,50,9}, {7,3,345,22}, {7,4,2409,12}, {7,5,16817,9}, {11,1,0,2},
! 82: {11,2,122,15}, {11,3,1346,11}, {11,4,14654,11}, {13,1,0,2}, {13,2,171,15},
! 83: {13,3,2199,15}, {13,4,28563,17}, {17,1,0,3}, {17,2,292,19}, {17,3,4933,17},
! 84: {19,1,0,2}, {19,2,362,22}, {19,3,6861,29}, {23,1,0,5}, {23,2,530,25},
! 85: {23,3,12193,23}, {29,1,0,2}, {29,2,843,30}, {29,3,24422,30}, {31,1,0,3},
! 86: {31,2,962,35}, {31,3,29794,34}, {37,1,0,2}, {37,2,1371,41}, {37,3,50655,75},
! 87: {41,1,0,6}, {41,2,1684,43}, {43,1,0,3}, {43,2,1850,45}, {47,1,0,5},
! 88: {47,2,2210,49}, {53,1,0,2}, {53,2,2811,54}, {59,1,0,2}, {59,2,3482,62},
! 89: {61,1,0,2}, {61,2,3723,63}, {67,1,0,2}, {67,2,4490,74}, {71,1,0,7},
! 90: {71,2,5042,79}, {73,1,0,5}, {73,2,5334,76}, {79,1,0,3}, {79,2,6242,85},
! 91: {83,1,0,2}, {83,2,6890,93}, {89,1,0,3}, {89,2,7924,91}, {97,1,0,5},
! 92: {97,2,9414,101}, {101,1,0,2}, {101,2,10203,102},
! 93: {103,1,0,5}, {103,2,10610,105}, {107,1,0,2}, {107,2,11450,109},
! 94: {109,1,0,6}, {109,2,11883,111}, {113,1,0,3}, {113,2,12772,117},
! 95: {127,1,0,3}, {127,2,16130,135}, {131,1,0,2}, {131,2,17162,134},
! 96: {137,1,0,3}, {137,2,18772,145}, {139,1,0,2}, {139,2,19322,143},
! 97: {149,1,0,2}, {149,2,22203,152}, {151,1,0,6}, {151,2,22802,160},
! 98: {157,1,0,5}, {157,2,24651,159}, {163,1,0,2}, {163,2,26570,170},
! 99: {167,1,0,5}, {167,2,27890,169}, {173,1,0,2}, {173,2,29931,174},
! 100: {179,1,0,2}, {179,2,32042,182}, {181,1,0,2}, {181,2,32763,185},
! 101: {191,1,0,19}, {191,2,36482,201}, {193,1,0,5}, {193,2,37254,198},
! 102: {197,1,0,2}, {197,2,38811,200}, {199,1,0,3}, {199,2,39602,212},
! 103: {211,1,0,2}, {211,2,44522,215}, {223,1,0,3}, {223,2,49730,225},
! 104: {227,1,0,2}, {227,2,51530,229}, {229,1,0,6}, {229,2,52443,231},
! 105: {233,1,0,3}, {233,2,54292,241}, {239,1,0,7}, {239,2,57122,247},
! 106: {241,1,0,7}, {241,2,58088,248}, {251,1,0,6}, {251,2,63002,256},
! 107: {257,1,0,3}, {263,1,0,5}, {269,1,0,2}, {271,1,0,6}, {277,1,0,5}, {281,1,0,3},
! 108: {283,1,0,3}, {293,1,0,2}, {307,1,0,5}, {311,1,0,17}, {313,1,0,10},
! 109: {317,1,0,2}, {331,1,0,3}, {337,1,0,10}, {347,1,0,2}, {349,1,0,2},
! 110: {353,1,0,3}, {359,1,0,7}, {367,1,0,6}, {373,1,0,2}, {379,1,0,2},
! 111: {383,1,0,5}, {389,1,0,2}, {397,1,0,5}, {401,1,0,3}, {409,1,0,21},
! 112: {419,1,0,2}, {421,1,0,2}, {431,1,0,7}, {433,1,0,5}, {439,1,0,15},
! 113: {443,1,0,2}, {449,1,0,3}, {457,1,0,13}, {461,1,0,2}, {463,1,0,3},
! 114: {467,1,0,2}, {479,1,0,13}, {487,1,0,3}, {491,1,0,2}, {499,1,0,7},
! 115: {503,1,0,5}, {509,1,0,2}, {521,1,0,3}, {523,1,0,2}, {541,1,0,2},
! 116: {547,1,0,2}, {557,1,0,2}, {563,1,0,2}, {569,1,0,3}, {571,1,0,3},
! 117: {577,1,0,5}, {587,1,0,2}, {593,1,0,3}, {599,1,0,7}, {601,1,0,7},
! 118: {607,1,0,3}, {613,1,0,2}, {617,1,0,3}, {619,1,0,2}, {631,1,0,3},
! 119: {641,1,0,3}, {643,1,0,11}, {647,1,0,5}, {653,1,0,2}, {659,1,0,2},
! 120: {661,1,0,2}, {673,1,0,5}, {677,1,0,2}, {683,1,0,5}, {691,1,0,3},
! 121: {701,1,0,2}, {709,1,0,2}, {719,1,0,11}, {727,1,0,5}, {733,1,0,6},
! 122: {739,1,0,3}, {743,1,0,5}, {751,1,0,3}, {757,1,0,2}, {761,1,0,6},
! 123: {769,1,0,11}, {773,1,0,2}, {787,1,0,2}, {797,1,0,2}, {809,1,0,3},
! 124: {811,1,0,3}, {821,1,0,2}, {823,1,0,3}, {827,1,0,2}, {829,1,0,2},
! 125: {839,1,0,11}, {853,1,0,2}, {857,1,0,3}, {859,1,0,2}, {863,1,0,5},
! 126: {877,1,0,2}, {881,1,0,3}, {883,1,0,2}, {887,1,0,5}, {907,1,0,2},
! 127: {911,1,0,17}, {919,1,0,7}, {929,1,0,3}, {937,1,0,5}, {941,1,0,2},
! 128: {947,1,0,2}, {953,1,0,3}, {967,1,0,5}, {971,1,0,6}, {977,1,0,3},
! 129: {983,1,0,5}, {991,1,0,6}, {997,1,0,7}, {1009,1,0,11}, {1013,1,0,3},
! 130: {1019,1,0,2}, {1021,1,0,10}, {1031,1,0,14}, {1033,1,0,5}, {1039,1,0,3},
! 131: {1049,1,0,3}, {1051,1,0,7}, {1061,1,0,2}, {1063,1,0,3}, {1069,1,0,6},
! 132: {1087,1,0,3}, {1091,1,0,2}, {1093,1,0,5}, {1097,1,0,3}, {1103,1,0,5},
! 133: {1109,1,0,2}, {1117,1,0,2}, {1123,1,0,2}, {1129,1,0,11}, {1151,1,0,17},
! 134: {1153,1,0,5}, {1163,1,0,5}, {1171,1,0,2}, {1181,1,0,7}, {1187,1,0,2},
! 135: {1193,1,0,3}, {1201,1,0,11}, {1213,1,0,2}, {1217,1,0,3}, {1223,1,0,5},
! 136: {1229,1,0,2}, {1231,1,0,3}, {1237,1,0,2}, {1249,1,0,7}, {1259,1,0,2},
! 137: {1277,1,0,2}, {1279,1,0,3}, {1283,1,0,2}, {1289,1,0,6}, {1291,1,0,2},
! 138: {1297,1,0,10}, {1301,1,0,2}, {1303,1,0,6}, {1307,1,0,2}, {1319,1,0,13},
! 139: {1321,1,0,13}, {1327,1,0,3}, {1361,1,0,3}, {1367,1,0,5}, {1373,1,0,2},
! 140: {1381,1,0,2}, {1399,1,0,13}, {1409,1,0,3}, {1423,1,0,3}, {1427,1,0,2},
! 141: {1429,1,0,6}, {1433,1,0,3}, {1439,1,0,7}, {1447,1,0,3}, {1451,1,0,2},
! 142: {1453,1,0,2}, {1459,1,0,3}, {1471,1,0,6}, {1481,1,0,3}, {1483,1,0,2},
! 143: {1487,1,0,5}, {1489,1,0,14}, {1493,1,0,2}, {1499,1,0,2}, {1511,1,0,11},
! 144: {1523,1,0,2}, {1531,1,0,2}, {1543,1,0,5}, {1549,1,0,2}, {1553,1,0,3},
! 145: {1559,1,0,19}, {1567,1,0,3}, {1571,1,0,2}, {1579,1,0,3}, {1583,1,0,5},
! 146: {1597,1,0,11}, {1601,1,0,3}, {1607,1,0,5}, {1609,1,0,7}, {1613,1,0,3},
! 147: {1619,1,0,2}, {1621,1,0,2}, {1627,1,0,3}, {1637,1,0,2}, {1657,1,0,11},
! 148: {1663,1,0,3}, {1667,1,0,2}, {1669,1,0,2}, {1693,1,0,2}, {1697,1,0,3},
! 149: {1699,1,0,3}, {1709,1,0,3}, {1721,1,0,3}, {1723,1,0,3}, {1733,1,0,2},
! 150: {1741,1,0,2}, {1747,1,0,2}, {1753,1,0,7}, {1759,1,0,6}, {1777,1,0,5},
! 151: {1783,1,0,10}, {1787,1,0,2}, {1789,1,0,6}, {1801,1,0,11}, {1811,1,0,6},
! 152: {1823,1,0,5}, {1831,1,0,3}, {1847,1,0,5}, {1861,1,0,2}, {1867,1,0,2},
! 153: {1871,1,0,14}, {1873,1,0,10}, {1877,1,0,2}, {1879,1,0,6}, {1889,1,0,3},
! 154: {1901,1,0,2}, {1907,1,0,2}, {1913,1,0,3}, {1931,1,0,2}, {1933,1,0,5},
! 155: {1949,1,0,2}, {1951,1,0,3}, {1973,1,0,2}, {1979,1,0,2}, {1987,1,0,2},
! 156: {1993,1,0,5}, {1997,1,0,2}, {1999,1,0,3}, {2003,1,0,5}, {2011,1,0,3},
! 157: {2017,1,0,5}, {2027,1,0,2}, {2029,1,0,2}, {2039,1,0,7}, {2053,1,0,2},
! 158: {2063,1,0,5}, {2069,1,0,2}, {2081,1,0,3}, {2083,1,0,2}, {2087,1,0,5},
! 159: {2089,1,0,7}, {2099,1,0,2}, {2111,1,0,7}, {2113,1,0,5}, {2129,1,0,3},
! 160: {2131,1,0,2}, {2137,1,0,10}, {2141,1,0,2}, {2143,1,0,3}, {2153,1,0,3},
! 161: {2161,1,0,23}, {2179,1,0,7}, {2203,1,0,5}, {2207,1,0,5}, {2213,1,0,2},
! 162: {2221,1,0,2}, {2237,1,0,2}, {2239,1,0,3}, {2243,1,0,2}, {2251,1,0,7},
! 163: {2267,1,0,2}, {2269,1,0,2}, {2273,1,0,3}, {2281,1,0,7}, {2287,1,0,19},
! 164: {2293,1,0,2}, {2297,1,0,5}, {2309,1,0,2}, {2311,1,0,3}, {2333,1,0,2},
! 165: {2339,1,0,2}, {2341,1,0,7}, {2347,1,0,3}, {2351,1,0,13}, {2357,1,0,2},
! 166: {2371,1,0,2}, {2377,1,0,5}, {2381,1,0,3}, {2383,1,0,5}, {2389,1,0,2},
! 167: {2393,1,0,3}, {2399,1,0,11}, {2411,1,0,6}, {2417,1,0,3}, {2423,1,0,5},
! 168: {2437,1,0,2}, {2441,1,0,6}, {2447,1,0,5}, {2459,1,0,2}, {2467,1,0,2},
! 169: {2473,1,0,5}, {2477,1,0,2}, {2503,1,0,3}, {2521,1,0,17}, {2531,1,0,2},
! 170: {2539,1,0,2}, {2543,1,0,5}, {2549,1,0,2}, {2551,1,0,6}, {2557,1,0,2},
! 171: {2579,1,0,2}, {2591,1,0,7}, {2593,1,0,7}, {2609,1,0,3}, {2617,1,0,5},
! 172: {2621,1,0,2}, {2633,1,0,3}, {2647,1,0,3}, {2657,1,0,3}, {2659,1,0,2},
! 173: {2663,1,0,5}, {2671,1,0,7}, {2677,1,0,2}, {2683,1,0,2}, {2687,1,0,5},
! 174: {2689,1,0,19}, {2693,1,0,2}, {2699,1,0,2}, {2707,1,0,2}, {2711,1,0,7},
! 175: {2713,1,0,5}, {2719,1,0,3}, {2729,1,0,3}, {2731,1,0,3}, {2741,1,0,2},
! 176: {2749,1,0,6}, {2753,1,0,3}, {2767,1,0,3}, {2777,1,0,3}, {2789,1,0,2},
! 177: {2791,1,0,6}, {2797,1,0,2}, {2801,1,0,3}, {2803,1,0,2}, {2819,1,0,2},
! 178: {2833,1,0,5}, {2837,1,0,2}, {2843,1,0,2}, {2851,1,0,2}, {2857,1,0,11},
! 179: {2861,1,0,2}, {2879,1,0,7}, {2887,1,0,5}, {2897,1,0,3}, {2903,1,0,5},
! 180: {2909,1,0,2}, {2917,1,0,5}, {2927,1,0,5}, {2939,1,0,2}, {2953,1,0,13},
! 181: {2957,1,0,2}, {2963,1,0,2}, {2969,1,0,3}, {2971,1,0,10}, {2999,1,0,17},
! 182: {3001,1,0,14}, {3011,1,0,2}, {3019,1,0,2}, {3023,1,0,5}, {3037,1,0,2},
! 183: {3041,1,0,3}, {3049,1,0,11}, {3061,1,0,6}, {3067,1,0,2}, {3079,1,0,6},
! 184: {3083,1,0,2}, {3089,1,0,3}, {3109,1,0,6}, {3119,1,0,7}, {3121,1,0,7},
! 185: {3137,1,0,3}, {3163,1,0,3}, {3167,1,0,5}, {3169,1,0,7}, {3181,1,0,7},
! 186: {3187,1,0,2}, {3191,1,0,11}, {3203,1,0,2}, {3209,1,0,3}, {3217,1,0,5},
! 187: {3221,1,0,10}, {3229,1,0,6}, {3251,1,0,6}, {3253,1,0,2}, {3257,1,0,3},
! 188: {3259,1,0,3}, {3271,1,0,3}, {3299,1,0,2}, {3301,1,0,6}, {3307,1,0,2},
! 189: {3313,1,0,10}, {3319,1,0,6}, {3323,1,0,2}, {3329,1,0,3}, {3331,1,0,3},
! 190: {3343,1,0,5}, {3347,1,0,2}, {3359,1,0,11}, {3361,1,0,22}, {3371,1,0,2},
! 191: {3373,1,0,5}, {3389,1,0,3}, {3391,1,0,3}, {3407,1,0,5}, {3413,1,0,2},
! 192: {3433,1,0,5}, {3449,1,0,3}, {3457,1,0,7}, {3461,1,0,2}, {3463,1,0,3},
! 193: {3467,1,0,2}, {3469,1,0,2}, {3491,1,0,2}, {3499,1,0,2}, {3511,1,0,7},
! 194: {3517,1,0,2}, {3527,1,0,5}, {3529,1,0,17}, {3533,1,0,2}, {3539,1,0,2},
! 195: {3541,1,0,7}, {3547,1,0,2}, {3557,1,0,2}, {3559,1,0,3}, {3571,1,0,2},
! 196: {3581,1,0,2}, {3583,1,0,3}, {3593,1,0,3}, {3607,1,0,5}, {3613,1,0,2},
! 197: {3617,1,0,3}, {3623,1,0,5}, {3631,1,0,15}, {3637,1,0,2}, {3643,1,0,2},
! 198: {3659,1,0,2}, {3671,1,0,13}, {3673,1,0,5}, {3677,1,0,2}, {3691,1,0,2},
! 199: {3697,1,0,5}, {3701,1,0,2}, {3709,1,0,2}, {3719,1,0,7}, {3727,1,0,3},
! 200: {3733,1,0,2}, {3739,1,0,7}, {3761,1,0,3}, {3767,1,0,5}, {3769,1,0,7},
! 201: {3779,1,0,2}, {3793,1,0,5}, {3797,1,0,2}, {3803,1,0,2}, {3821,1,0,3},
! 202: {3823,1,0,3}, {3833,1,0,3}, {3847,1,0,5}, {3851,1,0,2}, {3853,1,0,2},
! 203: {3863,1,0,5}, {3877,1,0,2}, {3881,1,0,13}, {3889,1,0,11}, {3907,1,0,2},
! 204: {3911,1,0,13}, {3917,1,0,2}, {3919,1,0,3}, {3923,1,0,2}, {3929,1,0,3},
! 205: {3931,1,0,2}, {3943,1,0,3}, {3947,1,0,2}, {3967,1,0,6}, {3989,1,0,2},
! 206: {4001,1,0,3}, {4003,1,0,2}, {4007,1,0,5}, {4013,1,0,2}, {4019,1,0,2},
! 207: {4021,1,0,2}, {4027,1,0,3}, {4049,1,0,3}, {4051,1,0,10}, {4057,1,0,5},
! 208: {4073,1,0,3}, {4079,1,0,11}, {4091,1,0,2}, {4093,1,0,2}, {4099,1,0,2},
! 209: {4111,1,0,12}, {4127,1,0,5}, {4129,1,0,13}, {4133,1,0,2}, {4139,1,0,2},
! 210: {4153,1,0,5}, {4157,1,0,2}, {4159,1,0,3}, {4177,1,0,5}, {4201,1,0,11},
! 211: {4211,1,0,6}, {4217,1,0,3}, {4219,1,0,2}, {4229,1,0,2}, {4231,1,0,3},
! 212: {4241,1,0,3}, {4243,1,0,2}, {4253,1,0,2}, {4259,1,0,2}, {4261,1,0,2},
! 213: {4271,1,0,7}, {4273,1,0,5}, {4283,1,0,2}, {4289,1,0,3}, {4297,1,0,5},
! 214: {4327,1,0,3}, {4337,1,0,3}, {4339,1,0,10}, {4349,1,0,2}, {4357,1,0,2},
! 215: {4363,1,0,2}, {4373,1,0,2}, {4391,1,0,14}, {4397,1,0,2}, {4409,1,0,3},
! 216: {4421,1,0,3}, {4423,1,0,3}, {4441,1,0,21}, {4447,1,0,3}, {4451,1,0,2},
! 217: {4457,1,0,3}, {4463,1,0,5}, {4481,1,0,3}, {4483,1,0,2}, {4493,1,0,2},
! 218: {4507,1,0,2}, {4513,1,0,7}, {4517,1,0,2}, {4519,1,0,3}, {4523,1,0,5},
! 219: {4547,1,0,2}, {4549,1,0,6}, {4561,1,0,11}, {4567,1,0,3}, {4583,1,0,5},
! 220: {4591,1,0,11}, {4597,1,0,5}, {4603,1,0,2}, {4621,1,0,2}, {4637,1,0,2},
! 221: {4639,1,0,3}, {4643,1,0,5}, {4649,1,0,3}, {4651,1,0,3}, {4657,1,0,15},
! 222: {4663,1,0,3}, {4673,1,0,3}, {4679,1,0,11}, {4691,1,0,2}, {4703,1,0,5},
! 223: {4721,1,0,6}, {4723,1,0,2}, {4729,1,0,17}, {4733,1,0,5}, {4751,1,0,19},
! 224: {4759,1,0,3}, {4783,1,0,6}, {4787,1,0,2}, {4789,1,0,2}, {4793,1,0,3},
! 225: {4799,1,0,7}, {4801,1,0,7}, {4813,1,0,2}, {4817,1,0,3}, {4831,1,0,3},
! 226: {4861,1,0,11}, {4871,1,0,11}, {4877,1,0,2}, {4889,1,0,3}, {4903,1,0,3},
! 227: {4909,1,0,6}, {4919,1,0,13}, {4931,1,0,6}, {4933,1,0,2}, {4937,1,0,3},
! 228: {4943,1,0,7}, {4951,1,0,6}, {4957,1,0,2}, {4967,1,0,5}, {4969,1,0,11},
! 229: {4973,1,0,2}, {4987,1,0,2}, {4993,1,0,5}, {4999,1,0,3}, {5003,1,0,2},
! 230: {5009,1,0,3}, {5011,1,0,2}, {5021,1,0,3}, {5023,1,0,3}, {5039,1,0,11},
! 231: {5051,1,0,2}, {5059,1,0,2}, {5077,1,0,2}, {5081,1,0,3}, {5087,1,0,5},
! 232: {5099,1,0,2}, {5101,1,0,6}, {5107,1,0,2}, {5113,1,0,19}, {5119,1,0,3},
! 233: {5147,1,0,2}, {5153,1,0,5}, {5167,1,0,6}, {5171,1,0,2}, {5179,1,0,2},
! 234: {5189,1,0,2}, {5197,1,0,7}, {5209,1,0,17}, {5227,1,0,2}, {5231,1,0,7},
! 235: {5233,1,0,10}, {5237,1,0,3}, {5261,1,0,2}, {5273,1,0,3}, {5279,1,0,7},
! 236: {5281,1,0,7}, {5297,1,0,3}, {5303,1,0,5}, {5309,1,0,2}, {5323,1,0,5},
! 237: {5333,1,0,2}, {5347,1,0,3}, {5351,1,0,11}, {5381,1,0,3}, {5387,1,0,2},
! 238: {5393,1,0,3}, {5399,1,0,7}, {5407,1,0,3}, {5413,1,0,5}, {5417,1,0,3},
! 239: {5419,1,0,3}, {5431,1,0,3}, {5437,1,0,5}, {5441,1,0,3}, {5443,1,0,2},
! 240: {5449,1,0,7}, {5471,1,0,7}, {5477,1,0,2}, {5479,1,0,3}, {5483,1,0,2},
! 241: {5501,1,0,2}, {5503,1,0,3}, {5507,1,0,2}, {5519,1,0,13}, {5521,1,0,11},
! 242: {5527,1,0,5}, {5531,1,0,10}, {5557,1,0,2}, {5563,1,0,2}, {5569,1,0,13},
! 243: {5573,1,0,2}, {5581,1,0,6}, {5591,1,0,11}, {5623,1,0,5}, {5639,1,0,7},
! 244: {5641,1,0,14}, {5647,1,0,3}, {5651,1,0,2}, {5653,1,0,5}, {5657,1,0,3},
! 245: {5659,1,0,2}, {5669,1,0,3}, {5683,1,0,2}, {5689,1,0,11}, {5693,1,0,2},
! 246: {5701,1,0,2}, {5711,1,0,19}, {5717,1,0,2}, {5737,1,0,5}, {5741,1,0,2},
! 247: {5743,1,0,10}, {5749,1,0,2}, {5779,1,0,2}, {5783,1,0,7}, {5791,1,0,6},
! 248: {5801,1,0,3}, {5807,1,0,5}, {5813,1,0,2}, {5821,1,0,6}, {5827,1,0,2},
! 249: {5839,1,0,6}, {5843,1,0,2}, {5849,1,0,3}, {5851,1,0,2}, {5857,1,0,7},
! 250: {5861,1,0,3}, {5867,1,0,5}, {5869,1,0,2}, {5879,1,0,11}, {5881,1,0,31},
! 251: {5897,1,0,3}, {5903,1,0,5}, {5923,1,0,2}, {5927,1,0,5}, {5939,1,0,2},
! 252: {5953,1,0,7}, {5981,1,0,3}, {5987,1,0,2}, {6007,1,0,3}, {6011,1,0,2},
! 253: {6029,1,0,2}, {6037,1,0,5}, {6043,1,0,5}, {6047,1,0,5}, {6053,1,0,2},
! 254: {6067,1,0,2}, {6073,1,0,10}, {6079,1,0,17}, {6089,1,0,3}, {6091,1,0,7},
! 255: {6101,1,0,2}, {6113,1,0,3}, {6121,1,0,7}, {6131,1,0,2}, {6133,1,0,5},
! 256: {6143,1,0,5}, {6151,1,0,3}, {6163,1,0,3}, {6173,1,0,2}, {6197,1,0,2},
! 257: {6199,1,0,3}, {6203,1,0,2}, {6211,1,0,2}, {6217,1,0,5}, {6221,1,0,3},
! 258: {6229,1,0,2}, {6247,1,0,5}, {6257,1,0,3}, {6263,1,0,5}, {6269,1,0,2},
! 259: {6271,1,0,11}, {6277,1,0,2}, {6287,1,0,7}, {6299,1,0,2}, {6301,1,0,10},
! 260: {6311,1,0,7}, {6317,1,0,2}, {6323,1,0,2}, {6329,1,0,3}, {6337,1,0,10},
! 261: {6343,1,0,3}, {6353,1,0,3}, {6359,1,0,13}, {6361,1,0,19}, {6367,1,0,3},
! 262: {6373,1,0,2}, {6379,1,0,2}, {6389,1,0,2}, {6397,1,0,2}, {6421,1,0,6},
! 263: {6427,1,0,3}, {6449,1,0,3}, {6451,1,0,3}, {6469,1,0,2}, {6473,1,0,3},
! 264: {6481,1,0,7}, {6491,1,0,2}, {6521,1,0,6}, {6529,1,0,7}, {6547,1,0,2},
! 265: {6551,1,0,17}, {6553,1,0,10}, {6563,1,0,5}, {6569,1,0,3}, {6571,1,0,3},
! 266: {6577,1,0,5}, {6581,1,0,14}, {6599,1,0,13}, {6607,1,0,3}, {6619,1,0,2},
! 267: {6637,1,0,2}, {6653,1,0,2}, {6659,1,0,2}, {6661,1,0,6}, {6673,1,0,5},
! 268: {6679,1,0,7}, {6689,1,0,3}, {6691,1,0,2}, {6701,1,0,2}, {6703,1,0,5},
! 269: {6709,1,0,2}, {6719,1,0,11}, {6733,1,0,2}, {6737,1,0,3}, {6761,1,0,3},
! 270: {6763,1,0,2}, {6779,1,0,2}, {6781,1,0,2}, {6791,1,0,7}, {6793,1,0,10},
! 271: {6803,1,0,2}, {6823,1,0,3}, {6827,1,0,2}, {6829,1,0,2}, {6833,1,0,3},
! 272: {6841,1,0,22}, {6857,1,0,3}, {6863,1,0,5}, {6869,1,0,2}, {6871,1,0,3},
! 273: {6883,1,0,2}, {6899,1,0,2}, {6907,1,0,2}, {6911,1,0,7}, {6917,1,0,2},
! 274: {6947,1,0,2}, {6949,1,0,2}, {6959,1,0,7}, {6961,1,0,13}, {6967,1,0,5},
! 275: {6971,1,0,2}, {6977,1,0,3}, {6983,1,0,5}, {6991,1,0,6}, {6997,1,0,5},
! 276: {7001,1,0,3}, {7013,1,0,2}, {7019,1,0,2}, {7027,1,0,2}, {7039,1,0,3},
! 277: {7043,1,0,2}, {7057,1,0,5}, {7069,1,0,2}, {7079,1,0,7}, {7103,1,0,5},
! 278: {7109,1,0,2}, {7121,1,0,3}, {7127,1,0,5}, {7129,1,0,7}, {7151,1,0,7},
! 279: {7159,1,0,3}, {7177,1,0,10}, {7187,1,0,2}, {7193,1,0,3}, {7207,1,0,3},
! 280: {7211,1,0,2}, {7213,1,0,5}, {7219,1,0,2}, {7229,1,0,2}, {7237,1,0,2},
! 281: {7243,1,0,2}, {7247,1,0,5}, {7253,1,0,2}, {7283,1,0,2}, {7297,1,0,5},
! 282: {7307,1,0,2}, {7309,1,0,6}, {7321,1,0,7}, {7331,1,0,2}, {7333,1,0,6},
! 283: {7349,1,0,2}, {7351,1,0,6}, {7369,1,0,7}, {7393,1,0,5}, {7411,1,0,2},
! 284: {7417,1,0,5}, {7433,1,0,3}, {7451,1,0,2}, {7457,1,0,3}, {7459,1,0,2},
! 285: {7477,1,0,2}, {7481,1,0,6}, {7487,1,0,5}, {7489,1,0,7}, {7499,1,0,2},
! 286: {7507,1,0,2}, {7517,1,0,2}, {7523,1,0,2}, {7529,1,0,3}, {7537,1,0,7},
! 287: {7541,1,0,2}, {7547,1,0,2}, {7549,1,0,2}, {7559,1,0,13}, {7561,1,0,13},
! 288: {7573,1,0,2}, {7577,1,0,3}, {7583,1,0,5}, {7589,1,0,2}, {7591,1,0,6},
! 289: {7603,1,0,2}, {7607,1,0,5}, {7621,1,0,2}, {7639,1,0,7}, {7643,1,0,2},
! 290: {7649,1,0,3}, {7669,1,0,2}, {7673,1,0,3}, {7681,1,0,17}, {7687,1,0,6},
! 291: {7691,1,0,2}, {7699,1,0,3}, {7703,1,0,5}, {7717,1,0,2}, {7723,1,0,3},
! 292: {7727,1,0,5}, {7741,1,0,7}, {7753,1,0,10}, {7757,1,0,2}, {7759,1,0,3},
! 293: {7789,1,0,2}, {7793,1,0,3}, {7817,1,0,3}, {7823,1,0,5}, {7829,1,0,2},
! 294: {7841,1,0,12}, {7853,1,0,2}, {7867,1,0,3}, {7873,1,0,5}, {7877,1,0,2},
! 295: {7879,1,0,3}, {7883,1,0,2}, {7901,1,0,2}, {7907,1,0,2}, {7919,1,0,7},
! 296: {7927,1,0,3}, {7933,1,0,2}, {7937,1,0,3}, {7949,1,0,2}, {7951,1,0,6},
! 297: {7963,1,0,5}, {7993,1,0,5}, {8009,1,0,3}, {8011,1,0,14}, {8017,1,0,5},
! 298: {8039,1,0,11}, {8053,1,0,2}, {8059,1,0,3}, {8069,1,0,2}, {8081,1,0,3},
! 299: {8087,1,0,5}, {8089,1,0,17}, {8093,1,0,2}, {8101,1,0,6}, {8111,1,0,11},
! 300: {8117,1,0,2}, {8123,1,0,2}, {8147,1,0,2}, {8161,1,0,7}, {8167,1,0,3},
! 301: {8171,1,0,2}, {8179,1,0,2}, {8191,1,0,17}, {8209,1,0,7}, {8219,1,0,2},
! 302: {8221,1,0,2}, {8231,1,0,11}, {8233,1,0,10}, {8237,1,0,2}, {8243,1,0,2},
! 303: {8263,1,0,3}, {8269,1,0,2}, {8273,1,0,3}, {8287,1,0,3}, {8291,1,0,2},
! 304: {8293,1,0,2}, {8297,1,0,3}, {8311,1,0,3}, {8317,1,0,6}, {8329,1,0,7},
! 305: {8353,1,0,5}, {8363,1,0,2}, {8369,1,0,3}, {8377,1,0,5}, {8387,1,0,2},
! 306: {8389,1,0,6}, {8419,1,0,3}, {8423,1,0,5}, {8429,1,0,2}, {8431,1,0,3},
! 307: {8443,1,0,2}, {8447,1,0,5}, {8461,1,0,6}, {8467,1,0,2}, {8501,1,0,7},
! 308: {8513,1,0,5}, {8521,1,0,13}, {8527,1,0,5}, {8537,1,0,3}, {8539,1,0,2},
! 309: {8543,1,0,5}, {8563,1,0,2}, {8573,1,0,2}, {8581,1,0,6}, {8597,1,0,2},
! 310: {8599,1,0,3}, {8609,1,0,3}, {8623,1,0,3}, {8627,1,0,2}, {8629,1,0,6},
! 311: {8641,1,0,17}, {8647,1,0,3}, {8663,1,0,5}, {8669,1,0,2}, {8677,1,0,2},
! 312: {8681,1,0,15}, {8689,1,0,13}, {8693,1,0,2}, {8699,1,0,2}, {8707,1,0,5},
! 313: {8713,1,0,5}, {8719,1,0,3}, {8731,1,0,2}, {8737,1,0,5}, {8741,1,0,2},
! 314: {8747,1,0,2}, {8753,1,0,3}, {8761,1,0,23}, {8779,1,0,11}, {8783,1,0,5},
! 315: {8803,1,0,2}, {8807,1,0,5}, {8819,1,0,2}, {8821,1,0,2}, {8831,1,0,7},
! 316: {8837,1,0,2}, {8839,1,0,3}, {8849,1,0,3}, {8861,1,0,2}, {8863,1,0,3},
! 317: {8867,1,0,2}, {8887,1,0,3}, {8893,1,0,5}, {8923,1,0,2}, {8929,1,0,11},
! 318: {8933,1,0,2}, {8941,1,0,6}, {8951,1,0,13}, {8963,1,0,2}, {8969,1,0,3},
! 319: {8971,1,0,2}, {8999,1,0,7}, {9001,1,0,7}, {9007,1,0,3}, {9011,1,0,2},
! 320: {9013,1,0,5}, {9029,1,0,2}, {9041,1,0,3}, {9043,1,0,3}, {9049,1,0,7},
! 321: {9059,1,0,2}, {9067,1,0,3}, {9091,1,0,3}, {9103,1,0,6}, {9109,1,0,10},
! 322: {9127,1,0,3}, {9133,1,0,6}, {9137,1,0,3}, {9151,1,0,3}, {9157,1,0,6},
! 323: {9161,1,0,3}, {9173,1,0,2}, {9181,1,0,2}, {9187,1,0,3}, {9199,1,0,3},
! 324: {9203,1,0,2}, {9209,1,0,3}, {9221,1,0,2}, {9227,1,0,2}, {9239,1,0,19},
! 325: {9241,1,0,13}, {9257,1,0,3}, {9277,1,0,5}, {9281,1,0,3}, {9283,1,0,2},
! 326: {9293,1,0,2}, {9311,1,0,7}, {9319,1,0,3}, {9323,1,0,2}, {9337,1,0,5},
! 327: {9341,1,0,2}, {9343,1,0,5}, {9349,1,0,2}, {9371,1,0,2}, {9377,1,0,3},
! 328: {9391,1,0,3}, {9397,1,0,2}, {9403,1,0,3}, {9413,1,0,3}, {9419,1,0,2},
! 329: {9421,1,0,2}, {9431,1,0,7}, {9433,1,0,5}, {9437,1,0,2}, {9439,1,0,22},
! 330: {9461,1,0,3}, {9463,1,0,3}, {9467,1,0,2}, {9473,1,0,3}, {9479,1,0,7},
! 331: {9491,1,0,2}, {9497,1,0,3}, {9511,1,0,3}, {9521,1,0,3}, {9533,1,0,2},
! 332: {9539,1,0,2}, {9547,1,0,2}, {9551,1,0,11}, {9587,1,0,2}, {9601,1,0,13},
! 333: {9613,1,0,2}, {9619,1,0,2}, {9623,1,0,5}, {9629,1,0,2}, {9631,1,0,3},
! 334: {9643,1,0,2}, {9649,1,0,7}, {9661,1,0,2}, {9677,1,0,2}, {9679,1,0,3},
! 335: {9689,1,0,3}, {9697,1,0,10}, {9719,1,0,17}, {9721,1,0,7}, {9733,1,0,2},
! 336: {9739,1,0,3}, {9743,1,0,5}, {9749,1,0,2}, {9767,1,0,5}, {9769,1,0,13},
! 337: {9781,1,0,6}, {9787,1,0,3}, {9791,1,0,11}, {9803,1,0,2}, {9811,1,0,3},
! 338: {9817,1,0,5}, {9829,1,0,10}, {9833,1,0,3}, {9839,1,0,7}, {9851,1,0,2},
! 339: {9857,1,0,5}, {9859,1,0,2}, {9871,1,0,3}, {9883,1,0,2}, {9887,1,0,5},
! 340: {9901,1,0,2}, {9907,1,0,2}, {9923,1,0,2}, {9929,1,0,3}, {9931,1,0,10},
! 341: {9941,1,0,2}, {9949,1,0,2}, {9967,1,0,3}, {9973,1,0,11}, {10007,1,0,5},
! 342: {10009,1,0,11}, {10037,1,0,2}, {10039,1,0,3}, {10061,1,0,3}, {10067,1,0,2},
! 343: {10069,1,0,2}, {10079,1,0,11}, {10091,1,0,2}, {10093,1,0,2}, {10099,1,0,2},
! 344: {10103,1,0,5}, {10111,1,0,12}, {10133,1,0,2}, {10139,1,0,2}, {10141,1,0,2},
! 345: {10151,1,0,7}, {10159,1,0,3}, {10163,1,0,2}, {10169,1,0,3}, {10177,1,0,7},
! 346: {10181,1,0,2}, {10193,1,0,3}, {10211,1,0,6}, {10223,1,0,5}, {10243,1,0,7},
! 347: {10247,1,0,5}, {10253,1,0,2}, {10259,1,0,2}, {10267,1,0,2}, {10271,1,0,7},
! 348: {10273,1,0,10}, {10289,1,0,3}, {10301,1,0,2}, {10303,1,0,3}, {10313,1,0,3},
! 349: {10321,1,0,7}, {10331,1,0,2}, {10333,1,0,5}, {10337,1,0,3}, {10343,1,0,5},
! 350: {10357,1,0,2}, {10369,1,0,13}, {10391,1,0,19}, {10399,1,0,6}, {10427,1,0,2},
! 351: {10429,1,0,7}, {10433,1,0,3}, {10453,1,0,5}, {10457,1,0,3}, {10459,1,0,2},
! 352: {10463,1,0,5}, {10477,1,0,2}, {10487,1,0,5}, {10499,1,0,2}, {10501,1,0,2},
! 353: {10513,1,0,7}, {10529,1,0,3}, {10531,1,0,3}, {10559,1,0,23}, {10567,1,0,6},
! 354: {10589,1,0,2}, {10597,1,0,5}, {10601,1,0,3}, {10607,1,0,5}, {10613,1,0,2},
! 355: {10627,1,0,5}, {10631,1,0,11}, {10639,1,0,6}, {10651,1,0,7}, {10657,1,0,7},
! 356: {10663,1,0,3}, {10667,1,0,2}, {10687,1,0,5}, {10691,1,0,2}, {10709,1,0,2},
! 357: {10711,1,0,3}, {10723,1,0,2}, {10729,1,0,7}, {10733,1,0,2}, {10739,1,0,6},
! 358: {10753,1,0,11}, {10771,1,0,3}, {10781,1,0,10}, {10789,1,0,2}, {10799,1,0,19},
! 359: {10831,1,0,7}, {10837,1,0,2}, {10847,1,0,5}, {10853,1,0,2}, {10859,1,0,2},
! 360: {10861,1,0,2}, {10867,1,0,2}, {10883,1,0,2}, {10889,1,0,3}, {10891,1,0,2},
! 361: {10903,1,0,3}, {10909,1,0,2}, {10937,1,0,3}, {10939,1,0,3}, {10949,1,0,2},
! 362: {10957,1,0,5}, {10973,1,0,2}, {10979,1,0,2}, {10987,1,0,2}, {10993,1,0,7},
! 363: {11003,1,0,2}, {11027,1,0,2}, {11047,1,0,3}, {11057,1,0,3}, {11059,1,0,10},
! 364: {11069,1,0,2}, {11071,1,0,3}, {11083,1,0,2}, {11087,1,0,5}, {11093,1,0,2},
! 365: {11113,1,0,13}, {11117,1,0,3}, {11119,1,0,3}, {11131,1,0,2}, {11149,1,0,10},
! 366: {11159,1,0,7}, {11161,1,0,7}, {11171,1,0,2}, {11173,1,0,5}, {11177,1,0,3},
! 367: {11197,1,0,2}, {11213,1,0,2}, {11239,1,0,3}, {11243,1,0,5}, {11251,1,0,13},
! 368: {11257,1,0,10}, {11261,1,0,2}, {11273,1,0,3}, {11279,1,0,7}, {11287,1,0,3},
! 369: {11299,1,0,3}, {11311,1,0,3}, {11317,1,0,2}, {11321,1,0,3}, {11329,1,0,7},
! 370: {11351,1,0,7}, {11353,1,0,7}, {11369,1,0,3}, {11383,1,0,5}, {11393,1,0,3},
! 371: {11399,1,0,11}, {11411,1,0,7}, {11423,1,0,5}, {11437,1,0,2}, {11443,1,0,2},
! 372: {11447,1,0,5}, {11467,1,0,5}, {11471,1,0,11}, {11483,1,0,2}, {11489,1,0,3},
! 373: {11491,1,0,3}, {11497,1,0,7}, {11503,1,0,3}, {11519,1,0,7}, {11527,1,0,5},
! 374: {11549,1,0,2}, {11551,1,0,7}, {11579,1,0,2}, {11587,1,0,2}, {11593,1,0,5},
! 375: {11597,1,0,3}, {11617,1,0,10}, {11621,1,0,2}, {11633,1,0,3}, {11657,1,0,3},
! 376: {11677,1,0,2}, {11681,1,0,3}, {11689,1,0,7}, {11699,1,0,2}, {11701,1,0,6},
! 377: {11717,1,0,2}, {11719,1,0,6}, {11731,1,0,3}, {11743,1,0,3}, {11777,1,0,3},
! 378: {11779,1,0,2}, {11783,1,0,5}, {11789,1,0,2}, {11801,1,0,3}, {11807,1,0,5},
! 379: {11813,1,0,2}, {11821,1,0,2}, {11827,1,0,2}, {11831,1,0,7}, {11833,1,0,5},
! 380: {11839,1,0,3}, {11863,1,0,3}, {11867,1,0,2}, {11887,1,0,3}, {11897,1,0,3},
! 381: {11903,1,0,5}, {11909,1,0,2}, {11923,1,0,5}, {11927,1,0,5}, {11933,1,0,2},
! 382: {11939,1,0,2}, {11941,1,0,10}, {11953,1,0,5}, {11959,1,0,3}, {11969,1,0,3},
! 383: {11971,1,0,10}, {11981,1,0,2}, {11987,1,0,2}, {12007,1,0,13}, {12011,1,0,2},
! 384: {12037,1,0,5}, {12041,1,0,3}, {12043,1,0,2}, {12049,1,0,13}, {12071,1,0,11},
! 385: {12073,1,0,7}, {12097,1,0,5}, {12101,1,0,3}, {12107,1,0,2}, {12109,1,0,6},
! 386: {12113,1,0,3}, {12119,1,0,7}, {12143,1,0,10}, {12149,1,0,2}, {12157,1,0,2},
! 387: {12161,1,0,3}, {12163,1,0,5}, {12197,1,0,2}, {12203,1,0,2}, {12211,1,0,2},
! 388: {12227,1,0,2}, {12239,1,0,13}, {12241,1,0,7}, {12251,1,0,2}, {12253,1,0,2},
! 389: {12263,1,0,5}, {12269,1,0,2}, {12277,1,0,2}, {12281,1,0,3}, {12289,1,0,11},
! 390: {12301,1,0,2}, {12323,1,0,2}, {12329,1,0,3}, {12343,1,0,7}, {12347,1,0,2},
! 391: {12373,1,0,2}, {12377,1,0,6}, {12379,1,0,2}, {12391,1,0,26}, {12401,1,0,3},
! 392: {12409,1,0,7}, {12413,1,0,2}, {12421,1,0,7}, {12433,1,0,13}, {12437,1,0,2},
! 393: {12451,1,0,3}, {12457,1,0,10}, {12473,1,0,3}, {12479,1,0,23}, {12487,1,0,3},
! 394: {12491,1,0,2}, {12497,1,0,3}, {12503,1,0,5}, {12511,1,0,3}, {12517,1,0,6},
! 395: {12527,1,0,5}, {12539,1,0,2}, {12541,1,0,14}, {12547,1,0,2}, {12553,1,0,5},
! 396: {12569,1,0,3}, {12577,1,0,10}, {12583,1,0,5}, {12589,1,0,2}, {12601,1,0,11},
! 397: {12611,1,0,2}, {12613,1,0,2}, {12619,1,0,2}, {12637,1,0,2}, {12641,1,0,3},
! 398: {12647,1,0,5}, {12653,1,0,2}, {12659,1,0,2}, {12671,1,0,14}, {12689,1,0,3},
! 399: {12697,1,0,7}, {12703,1,0,3}, {12713,1,0,3}, {12721,1,0,13}, {12739,1,0,2},
! 400: {12743,1,0,5}, {12757,1,0,2}, {12763,1,0,2}, {12781,1,0,2}, {12791,1,0,7},
! 401: {12799,1,0,13}, {12809,1,0,3}, {12821,1,0,2}, {12823,1,0,3}, {12829,1,0,2},
! 402: {12841,1,0,21}, {12853,1,0,5}, {12889,1,0,13}, {12893,1,0,3}, {12899,1,0,2},
! 403: {12907,1,0,2}, {12911,1,0,23}, {12917,1,0,2}, {12919,1,0,6}, {12923,1,0,2},
! 404: {12941,1,0,2}, {12953,1,0,3}, {12959,1,0,7}, {12967,1,0,3}, {12973,1,0,14},
! 405: {12979,1,0,2}, {12983,1,0,5}, {13001,1,0,3}, {13003,1,0,5}, {13007,1,0,5},
! 406: {13009,1,0,7}, {13033,1,0,5}, {13037,1,0,2}, {13043,1,0,2}, {13049,1,0,3},
! 407: {13063,1,0,5}, {13093,1,0,6}, {13099,1,0,3}, {13103,1,0,5}, {13109,1,0,2},
! 408: {13121,1,0,7}, {13127,1,0,5}, {13147,1,0,2}, {13151,1,0,13}, {13159,1,0,3},
! 409: {13163,1,0,2}, {13171,1,0,11}, {13177,1,0,5}, {13183,1,0,3}, {13187,1,0,2},
! 410: {13217,1,0,3}, {13219,1,0,3}, {13229,1,0,2}, {13241,1,0,3}, {13249,1,0,7},
! 411: {13259,1,0,6}, {13267,1,0,3}, {13291,1,0,2}, {13297,1,0,5}, {13309,1,0,6},
! 412: {13313,1,0,3}, {13327,1,0,3}, {13331,1,0,2}, {13337,1,0,3}, {13339,1,0,2},
! 413: {13367,1,0,5}, {13381,1,0,10}, {13397,1,0,2}, {13399,1,0,3}, {13411,1,0,2},
! 414: {13417,1,0,5}, {13421,1,0,10}, {13441,1,0,11}, {13451,1,0,2}, {13457,1,0,3},
! 415: {13463,1,0,5}, {13469,1,0,2}, {13477,1,0,2}, {13487,1,0,5}, {13499,1,0,6},
! 416: {13513,1,0,5}, {13523,1,0,2}, {13537,1,0,7}, {13553,1,0,3}, {13567,1,0,3},
! 417: {13577,1,0,3}, {13591,1,0,3}, {13597,1,0,5}, {13613,1,0,2}, {13619,1,0,2},
! 418: {13627,1,0,2}, {13633,1,0,5}, {13649,1,0,3}, {13669,1,0,6}, {13679,1,0,7},
! 419: {13681,1,0,22}, {13687,1,0,3}, {13691,1,0,2}, {13693,1,0,6}, {13697,1,0,3},
! 420: {13709,1,0,2}, {13711,1,0,6}, {13721,1,0,3}, {13723,1,0,2}, {13729,1,0,23},
! 421: {13751,1,0,11}, {13757,1,0,2}, {13759,1,0,6}, {13763,1,0,2}, {13781,1,0,7},
! 422: {13789,1,0,7}, {13799,1,0,7}, {13807,1,0,5}, {13829,1,0,2}, {13831,1,0,6},
! 423: {13841,1,0,6}, {13859,1,0,2}, {13873,1,0,5}, {13877,1,0,2}, {13879,1,0,6},
! 424: {13883,1,0,2}, {13901,1,0,2}, {13903,1,0,3}, {13907,1,0,2}, {13913,1,0,3},
! 425: {13921,1,0,7}, {13931,1,0,2}, {13933,1,0,2}, {13963,1,0,3}, {13967,1,0,5},
! 426: {13997,1,0,2}, {13999,1,0,3}, {14009,1,0,3}, {14011,1,0,2}, {14029,1,0,6},
! 427: {14033,1,0,3}, {14051,1,0,2}, {14057,1,0,3}, {14071,1,0,7}, {14081,1,0,3},
! 428: {14083,1,0,3}, {14087,1,0,5}, {14107,1,0,2}, {14143,1,0,3}, {14149,1,0,6},
! 429: {14153,1,0,3}, {14159,1,0,13}, {14173,1,0,2}, {14177,1,0,3}, {14197,1,0,11},
! 430: {14207,1,0,5}, {14221,1,0,2}, {14243,1,0,2}, {14249,1,0,3}, {14251,1,0,3},
! 431: {14281,1,0,19}, {14293,1,0,6}, {14303,1,0,5}, {14321,1,0,3}, {14323,1,0,5},
! 432: {14327,1,0,5}, {14341,1,0,2}, {14347,1,0,3}, {14369,1,0,3}, {14387,1,0,2},
! 433: {14389,1,0,2}, {14401,1,0,11}, {14407,1,0,19}, {14411,1,0,2}, {14419,1,0,2},
! 434: {14423,1,0,5}, {14431,1,0,3}, {14437,1,0,5}, {14447,1,0,5}, {14449,1,0,22},
! 435: {14461,1,0,2}, {14479,1,0,3}, {14489,1,0,3}, {14503,1,0,3}, {14519,1,0,13},
! 436: {14533,1,0,2}, {14537,1,0,3}, {14543,1,0,5}, {14549,1,0,2}, {14551,1,0,3},
! 437: {14557,1,0,2}, {14561,1,0,6}, {14563,1,0,3}, {14591,1,0,11}, {14593,1,0,5},
! 438: {14621,1,0,2}, {14627,1,0,2}, {14629,1,0,2}, {14633,1,0,3}, {14639,1,0,11},
! 439: {14653,1,0,2}, {14657,1,0,3}, {14669,1,0,2}, {14683,1,0,3}, {14699,1,0,2},
! 440: {14713,1,0,5}, {14717,1,0,2}, {14723,1,0,2}, {14731,1,0,10}, {14737,1,0,10},
! 441: {14741,1,0,2}, {14747,1,0,2}, {14753,1,0,3}, {14759,1,0,17}, {14767,1,0,3},
! 442: {14771,1,0,2}, {14779,1,0,3}, {14783,1,0,5}, {14797,1,0,2}, {14813,1,0,2},
! 443: {14821,1,0,2}, {14827,1,0,2}, {14831,1,0,11}, {14843,1,0,2}, {14851,1,0,2},
! 444: {14867,1,0,2}, {14869,1,0,2}, {14879,1,0,7}, {14887,1,0,3}, {14891,1,0,2},
! 445: {14897,1,0,3}, {14923,1,0,2}, {14929,1,0,7}, {14939,1,0,2}, {14947,1,0,2},
! 446: {14951,1,0,19}, {14957,1,0,2}, {14969,1,0,3}, {14983,1,0,3}, {15013,1,0,2},
! 447: {15017,1,0,3}, {15031,1,0,3}, {15053,1,0,2}, {15061,1,0,2}, {15073,1,0,5},
! 448: {15077,1,0,2}, {15083,1,0,2}, {15091,1,0,2}, {15101,1,0,2}, {15107,1,0,2},
! 449: {15121,1,0,11}, {15131,1,0,2}, {15137,1,0,3}, {15139,1,0,2}, {15149,1,0,2},
! 450: {15161,1,0,3}, {15173,1,0,2}, {15187,1,0,2}, {15193,1,0,5}, {15199,1,0,6},
! 451: {15217,1,0,10}, {15227,1,0,2}, {15233,1,0,3}, {15241,1,0,11}, {15259,1,0,2},
! 452: {15263,1,0,5}, {15269,1,0,2}, {15271,1,0,11}, {15277,1,0,6}, {15287,1,0,5},
! 453: {15289,1,0,11}, {15299,1,0,2}, {15307,1,0,3}, {15313,1,0,5}, {15319,1,0,3},
! 454: {15329,1,0,3}, {15331,1,0,2}, {15349,1,0,2}, {15359,1,0,11}, {15361,1,0,7},
! 455: {15373,1,0,2}, {15377,1,0,3}, {15383,1,0,5}, {15391,1,0,12}, {15401,1,0,6},
! 456: {15413,1,0,2}, {15427,1,0,2}, {15439,1,0,3}, {15443,1,0,2}, {15451,1,0,3},
! 457: {15461,1,0,2}, {15467,1,0,5}, {15473,1,0,3}, {15493,1,0,5}, {15497,1,0,3},
! 458: {15511,1,0,3}, {15527,1,0,5}, {15541,1,0,6}, {15551,1,0,7}, {15559,1,0,3},
! 459: {15569,1,0,3}, {15581,1,0,2}, {15583,1,0,5}, {15601,1,0,23}, {15607,1,0,3},
! 460: {15619,1,0,7}, {15629,1,0,2}, {15641,1,0,3}, {15643,1,0,5}, {15647,1,0,5},
! 461: {15649,1,0,11}, {15661,1,0,2}, {15667,1,0,2}, {15671,1,0,13}, {15679,1,0,11},
! 462: {15683,1,0,2}, {15727,1,0,3}, {15731,1,0,2}, {15733,1,0,6}, {15737,1,0,3},
! 463: {15739,1,0,2}, {15749,1,0,2}, {15761,1,0,3}, {15767,1,0,5}, {15773,1,0,2},
! 464: {15787,1,0,2}, {15791,1,0,29}, {15797,1,0,2}, {15803,1,0,2}, {15809,1,0,3},
! 465: {15817,1,0,5}, {15823,1,0,3}, {15859,1,0,2}, {15877,1,0,5}, {15881,1,0,3},
! 466: {15887,1,0,5}, {15889,1,0,21}, {15901,1,0,10}, {15907,1,0,2}, {15913,1,0,5},
! 467: {15919,1,0,6}, {15923,1,0,2}, {15937,1,0,7}, {15959,1,0,11}, {15971,1,0,2},
! 468: {15973,1,0,7}, {15991,1,0,12}, {16001,1,0,3}, {16007,1,0,5}, {16033,1,0,5},
! 469: {16057,1,0,7}, {16061,1,0,12}, {16063,1,0,5}, {16067,1,0,2}, {16069,1,0,2},
! 470: {16073,1,0,3}, {16087,1,0,5}, {16091,1,0,6}, {16097,1,0,3}, {16103,1,0,5},
! 471: {16111,1,0,7}, {16127,1,0,5}, {16139,1,0,2}, {16141,1,0,6}, {16183,1,0,3},
! 472: {16187,1,0,2}, {16189,1,0,2}, {16193,1,0,5}, {16217,1,0,3}, {16223,1,0,5},
! 473: {16229,1,0,2}, {16231,1,0,3}, {16249,1,0,17}, {16253,1,0,2}, {16267,1,0,3},
! 474: {16273,1,0,7}, {16301,1,0,2}, {16319,1,0,7}, {16333,1,0,2}, {16339,1,0,2},
! 475: {16349,1,0,2}, {16361,1,0,3}, {16363,1,0,2}, {16369,1,0,7}, {16381,1,0,2},
! 476: };
! 477:
! 478: void dec_um(int p,int a,UM u)
! 479: {
! 480: int i;
! 481:
! 482: for ( i = 0; a; i++, a /= p )
! 483: COEF(u)[i] = a%p;
! 484: DEG(u) = i-1;
! 485: }
! 486:
! 487: /*
! 488: * an element of GF(p^n) f(x)=a(n-1)*x^(n-1)+...+a(0)
! 489: * is encodeded to f(p).
! 490: * current_gfs_iton[i] = r^i mod p (i=0,...,p-2)
! 491: * current_gfs_iton[p-1] = 0
! 492: */
! 493:
! 494: void setmod_sf(int p,int n)
! 495: {
! 496: int r,i,q1,q,t,t1;
! 497: UM dp;
! 498:
! 499: if ( p >= SF_THRESHOLD ) {
! 500: if ( n > 1 )
! 501: error("setmod_ff : p^n is too large");
! 502: current_gfs_p = p;
! 503: current_gfs_q = p;
! 504: current_gfs_q1 = p-1;
! 505: current_gfs_ext = 0;
! 506: current_gfs_ntoi = 0;
! 507: current_gfs_iton = 0;
! 508: current_gfs_plus1 = 0;
! 509: return;
! 510: }
! 511:
! 512: for ( i = 0, q = 1; i < n; i++ )
! 513: q *= p;
! 514: if ( p == current_gfs_p && q == current_gfs_q ) return;
! 515: dp = UMALLOC(n);
! 516: r = search_defpoly_and_primitive_root(p,n,dp);
! 517: if ( !r ) {
! 518: generate_defpoly_um(p,n,dp);
! 519: r = generate_primitive_root_enc(p,n,dp);
! 520: if ( !r )
! 521: error("setmod_sf : primitive root not found");
! 522: }
! 523: current_gfs_p = p;
! 524: current_gfs_q = q;
! 525: current_gfs_q1 = q1 = q-1;
! 526: if ( n > 1 )
! 527: umtop(CO->v,dp,¤t_gfs_ext);
! 528: else
! 529: current_gfs_ext = 0;
! 530: current_gfs_iton = (int *)MALLOC(q1*sizeof(int));
! 531: current_gfs_iton[0] = 1;
! 532: for ( i = 1; i < q1; i++ )
! 533: current_gfs_iton[i] = mulremum_enc(p,n,dp,current_gfs_iton[i-1],r);
! 534:
! 535: current_gfs_ntoi = (int *)MALLOC(q*sizeof(int));
! 536: current_gfs_ntoi[0] = -1;
! 537: for ( i = 0; i < q1; i++ )
! 538: current_gfs_ntoi[current_gfs_iton[i]] = i;
! 539:
! 540: current_gfs_plus1 = (int *)MALLOC(q*sizeof(int));
! 541: for ( i = 0; i < q1; i++ ) {
! 542: t = current_gfs_iton[i];
! 543: /* add 1 to the constant part */
! 544: t1 = (t/p)*p+((t+1)%p);
! 545: current_gfs_plus1[i] = current_gfs_ntoi[t1];
! 546: }
! 547: }
! 548:
! 549: int search_defpoly_and_primitive_root(int p,int n,UM dp)
! 550: {
! 551: int l,min,max,mid,p1,i,ind,t;
! 552:
! 553: l = sizeof(prim_root_info_tab)/sizeof(struct prim_root_info);
! 554: min = 0; max = l-1;
! 555: ind = -1;
! 556: while ( max - min > 1 ) {
! 557: mid = (max+min)/2;
! 558: p1 = prim_root_info_tab[mid].p;
! 559: if ( p1 == p ) {
! 560: ind = mid; break;
! 561: } else if ( p1 > p )
! 562: max = mid;
! 563: else
! 564: min = mid;
! 565: }
! 566: if ( ind < 0 ) {
! 567: if ( prim_root_info_tab[min].p == p )
! 568: ind = min;
! 569: else if ( prim_root_info_tab[max].p == p )
! 570: ind = max;
! 571: else
! 572: return 0; /* XXX */
! 573: }
! 574: /* now prim_root_info_tab[ind].p = p */
! 575: t = ind - (prim_root_info_tab[ind].extdeg-1);
! 576: /* now prim_root_info_tab[t].extdeg = 1 */
! 577: for ( i = t; prim_root_info_tab[i].p == p; i++ )
! 578: if ( prim_root_info_tab[i].extdeg == n )
! 579: break;
! 580: if ( prim_root_info_tab[i].p != p )
! 581: return 0;
! 582: dec_um(p,prim_root_info_tab[i].defpoly,dp);
! 583: return prim_root_info_tab[i].prim_root;
! 584: }
! 585:
! 586: void generate_defpoly_um(int p,int n,UM dp)
! 587: {
! 588: int i,j,a,q;
! 589: UM wf,wdf,wgcd;
! 590:
! 591: wf = W_UMALLOC(n);
! 592: wdf = W_UMALLOC(n);
! 593: wgcd = W_UMALLOC(n);
! 594: COEF(dp)[n] = 1;
! 595: DEG(dp) = n;
! 596: for ( i = 0, q = 1; i < n; i++ )
! 597: q *= p;
! 598: for ( i = 0; i < q; i++ ) {
! 599: for ( j = 0, a = i; a; j++, a /= p )
! 600: COEF(dp)[j] = a%p;
! 601: for ( ; j < n; j++ )
! 602: COEF(dp)[j] = 0;
! 603: cpyum(dp,wf);
! 604: diffum(p,dp,wdf);
! 605: gcdum(p,wf,wdf,wgcd);
! 606: if ( DEG(wgcd) >= 1 )
! 607: continue;
! 608: mini(p,dp,wf);
! 609: if ( DEG(wf) <= 0 )
! 610: return;
! 611: }
! 612: }
! 613:
! 614: int generate_primitive_root_enc(int p,int n,UM dp)
! 615: {
! 616: int i,r,rj,j,q;
! 617:
! 618: if ( p == 2 && n == 1 )
! 619: return 1;
! 620:
! 621: for ( i = 0, q = 1; i < n; i++ )
! 622: q *= p;
! 623: for ( r = n==1?2:p; r < q; r++ ) {
! 624: rj = r;
! 625: for ( j = 1; j < q-1 && rj != 1; j++ )
! 626: rj = mulremum_enc(p,n,dp,rj,r);
! 627: if ( j == q-1 )
! 628: return r;
! 629: }
! 630: /* not found */
! 631: return 0;
! 632: }
! 633:
! 634: /* [a(p)]*[b(p)] in GF(p^n) -> [a(x)*b(x) mod dp(x)]_{x->p} */
! 635:
! 636: int mulremum_enc(int p,int n,UM dp,int a,int b)
! 637: {
! 638: int i,dr,r;
! 639: UM wa,wb,wc,wq;
! 640:
! 641: if ( n == 1 )
! 642: return (a*b)%p;
! 643: if ( !a || !b )
! 644: return 0;
! 645:
! 646: wa = W_UMALLOC(n);
! 647: dec_um(p,a,wa);
! 648:
! 649: wb = W_UMALLOC(n);
! 650: dec_um(p,b,wb);
! 651:
! 652: wc = W_UMALLOC(2*n);
! 653: wq = W_UMALLOC(2*n);
! 654: mulum(p,wa,wb,wc);
! 655: dr = divum(p,wc,dp,wq);
! 656: for ( i = dr, r = 0; i >= 0; i-- )
! 657: r = r*p+COEF(wc)[i];
! 658: return r;
! 659: }
! 660:
! 661: /* sigma : alpha -> alpha^q */
! 662:
! 663: void gfs_galois_action(GFS a,Q e,GFS *c)
! 664: {
! 665: Z p;
! 666: int i,k;
! 667: GFS t,s;
! 668:
! 669: t = a;
! 670: k = QTOS(e);
! 671: STOQ(current_gfs_p,p);
! 672: for ( i = 0; i < k; i++ ) {
! 673: pwrgfs(t,p,&s); t = s;
! 674: }
! 675: *c = t;
! 676: }
! 677:
! 678: /* GF(pn)={0,1,a,a^2,...} -> GF(pm)={0,1,b,b^2,...}; a->b^k */
! 679:
! 680: void gfs_embed(GFS z,int k,int pm,GFS *c)
! 681: {
! 682: int t;
! 683:
! 684: if ( !z )
! 685: *c = 0;
! 686: else {
! 687: t = dmar(k,CONT(z),0,pm-1);
! 688: MKGFS(t,*c);
! 689: }
! 690: }
! 691:
! 692: /* 0 <= index <= q-1 */
! 693:
! 694: void indextogfs(int index, GFS *c)
! 695: {
! 696: if ( index == 0 )
! 697: *c = 0;
! 698: else if ( index >= current_gfs_q )
! 699: error("indextogfs : exhausted");
! 700: else if ( !current_gfs_ntoi ) {
! 701: MKGFS(index,*c);
! 702: } else {
! 703: MKGFS(index-1,*c);
! 704: }
! 705: }
! 706:
! 707: void itogfs(int n, GFS *c)
! 708: {
! 709: n = _itosf(n);
! 710: if ( !n )
! 711: *c = 0;
! 712: else {
! 713: n = IFTOF(n);
! 714: MKGFS(n,*c);
! 715: }
! 716: }
! 717:
! 718: void iftogfs(int n, GFS *c)
! 719: {
! 720: if ( !n )
! 721: *c = 0;
! 722: else {
! 723: MKGFS(IFTOF(n),*c);
! 724: }
! 725: }
! 726:
! 727: void qtogfs(Q a,GFS *c)
! 728: {
! 729: int s;
! 730:
! 731: if ( a && (sgnq(a) < 1) )
! 732: error("qtogfs : invalid argument");
! 733: s = QTOS(a)%current_gfs_q;
! 734: itogfs(s,c);
! 735: }
! 736:
! 737: void mqtogfs(MQ a,GFS *c)
! 738: {
! 739: if ( !a )
! 740: *c = 0;
! 741: else
! 742: itogfs(CONT(a),c);
! 743: }
! 744:
! 745: void gfstomq(GFS a,MQ *c)
! 746: {
! 747: if ( !a )
! 748: *c = 0;
! 749: else if ( !current_gfs_ntoi ) {
! 750: UTOMQ(CONT(a),*c);
! 751: } else {
! 752: UTOMQ(current_gfs_iton[CONT(a)],*c);
! 753: }
! 754: }
! 755:
! 756: void gfstopgfs(GFS a,V v,P *c)
! 757: {
! 758: MQ t;
! 759: Z q;
! 760:
! 761: if ( !a )
! 762: *c = 0;
! 763: else if ( !current_gfs_ntoi ) {
! 764: UTOMQ(CONT(a),t);
! 765: STOQ(CONT(t),q);
! 766: *c = (P)q;
! 767: } else
! 768: enc_to_p(current_gfs_p,current_gfs_iton[CONT(a)],v,c);
! 769: }
! 770:
! 771: void ntogfs(Obj a,GFS *b)
! 772: {
! 773: P t;
! 774:
! 775: if ( !current_gfs_q1 )
! 776: error("addgfs : current_gfs_q is not set");
! 777: if ( !a || (OID(a)==O_N && NID(a) == N_GFS) )
! 778: *b = (GFS)a;
! 779: else if ( OID(a) == O_N && NID(a) == N_M )
! 780: mqtogfs((MQ)a,b);
! 781: else if ( OID(a) == O_N && NID(a) == N_Q ) {
! 782: ptomp(current_gfs_p,(P)a,&t); mqtogfs((MQ)t,b);
! 783: } else
! 784: error("ntogfs : invalid argument");
! 785: }
! 786:
! 787: void addgfs(GFS a,GFS b,GFS *c)
! 788: {
! 789: int ai,bi,ci;
! 790: GFS z;
! 791:
! 792: ntogfs((Obj)a,&z); a = z;
! 793: ntogfs((Obj)b,&z); b = z;
! 794: if ( !a )
! 795: *c = b;
! 796: else if ( !b )
! 797: *c = a;
! 798: else if ( !current_gfs_ntoi ) {
! 799: ai = CONT(a); bi = CONT(b);
! 800: ci = ai+bi-current_gfs_q;
! 801: if ( ci == 0 )
! 802: *c = 0;
! 803: else {
! 804: if ( ci < 0 )
! 805: ci += current_gfs_q;
! 806: MKGFS(ci,*c);
! 807: }
! 808: } else {
! 809: ai = CONT(a); bi = CONT(b);
! 810: if ( ai > bi ) {
! 811: /* tab[ai]+tab[bi] = tab[bi](tab[ai-bi]+1) */
! 812: ci = current_gfs_plus1[ai-bi];
! 813: if ( ci < 0 )
! 814: *c = 0;
! 815: else {
! 816: ci += bi;
! 817: if ( ci >= current_gfs_q1 )
! 818: ci -= current_gfs_q1;
! 819: MKGFS(ci,*c);
! 820: }
! 821: } else {
! 822: /* tab[ai]+tab[bi] = tab[ai](tab[bi-ai]+1) */
! 823: ci = current_gfs_plus1[bi-ai];
! 824: if ( ci < 0 )
! 825: *c = 0;
! 826: else {
! 827: ci += ai;
! 828: if ( ci >= current_gfs_q1 )
! 829: ci -= current_gfs_q1;
! 830: MKGFS(ci,*c);
! 831: }
! 832: }
! 833: }
! 834: }
! 835:
! 836: void subgfs(GFS a,GFS b,GFS *c)
! 837: {
! 838: GFS t,z;
! 839:
! 840: ntogfs((Obj)a,&z); a = z;
! 841: ntogfs((Obj)b,&z); b = z;
! 842: if ( !b )
! 843: *c = a;
! 844: else {
! 845: chsgngfs(b,&t);
! 846: addgfs(a,t,c);
! 847: }
! 848: }
! 849:
! 850: void mulgfs(GFS a,GFS b,GFS *c)
! 851: {
! 852: int ai,bi,ci;
! 853: GFS z;
! 854:
! 855: ntogfs((Obj)a,&z); a = z;
! 856: ntogfs((Obj)b,&z); b = z;
! 857: if ( !a || !b )
! 858: *c = 0;
! 859: else if ( !current_gfs_ntoi ) {
! 860: ai = CONT(a); bi = CONT(b);
! 861: DMAR(ai,bi,0,current_gfs_q,ci);
! 862: MKGFS(ci,*c);
! 863: } else {
! 864: ai = CONT(a) + CONT(b);
! 865: if ( ai >= current_gfs_q1 )
! 866: ai -= current_gfs_q1;
! 867: MKGFS(ai,*c);
! 868: }
! 869: }
! 870:
! 871: void divgfs(GFS a,GFS b,GFS *c)
! 872: {
! 873: int ai,bi,ci;
! 874: GFS z;
! 875:
! 876: ntogfs((Obj)a,&z); a = z;
! 877: ntogfs((Obj)b,&z); b = z;
! 878: if ( !b )
! 879: error("divgfs : division by 0");
! 880: else if ( !a )
! 881: *c = 0;
! 882: else if ( !current_gfs_ntoi ) {
! 883: ai = CONT(a); bi = invm(CONT(b),current_gfs_q);
! 884: DMAR(ai,bi,0,current_gfs_q,ci);
! 885: MKGFS(ci,*c);
! 886: } else {
! 887: ai = CONT(a) - CONT(b);
! 888: if ( ai < 0 )
! 889: ai += current_gfs_q1;
! 890: MKGFS(ai,*c);
! 891: }
! 892: }
! 893:
! 894: void chsgngfs(GFS a,GFS *c)
! 895: {
! 896: int ai;
! 897: GFS z;
! 898:
! 899: ntogfs((Obj)a,&z); a = z;
! 900: if ( !a )
! 901: *c = 0;
! 902: else if ( !current_gfs_ntoi ) {
! 903: ai = current_gfs_q - CONT(a);
! 904: MKGFS(ai,*c);
! 905: } else if ( current_gfs_q1&1 )
! 906: *c = a;
! 907: else {
! 908: /* r^((q-1)/2) = -1 */
! 909: ai = CONT(a)+(current_gfs_q1>>1);
! 910: if ( ai >= current_gfs_q1 )
! 911: ai -= current_gfs_q1;
! 912: MKGFS(ai,*c);
! 913: }
! 914: }
! 915:
! 916: void pwrgfs(GFS a,Z b,GFS *c)
! 917: {
! 918: Z an,tn,rn;
! 919: GFS t,s,z;
! 920: int ai;
! 921:
! 922: ntogfs((Obj)a,&z); a = z;
! 923: if ( !b )
! 924: itogfs(1,c);
! 925: else if ( !a )
! 926: *c = 0;
! 927: else if ( !current_gfs_ntoi) {
! 928: ai = pwrm(current_gfs_q,CONT(a),QTOS(b));
! 929: MKGFS(ai,*c);
! 930: } else {
! 931: STOQ(CONT(a),an); mulz(an,b,&tn);
! 932: STOQ(current_gfs_q1,an); remz(tn,an,&rn);
! 933: if ( !rn )
! 934: itogfs(1,c);
! 935: else {
! 936: ai = QTOS(rn);
! 937: MKGFS(ai,*c);
! 938: }
! 939: }
! 940: }
! 941:
! 942: int cmpgfs(GFS a,GFS b)
! 943: {
! 944: GFS z;
! 945:
! 946: ntogfs((Obj)a,&z); a = z;
! 947: if ( !a )
! 948: return !b ? 0 : -1;
! 949: else
! 950: if ( !b )
! 951: return 1;
! 952: else {
! 953: if ( CONT(a) > CONT(b) )
! 954: return 1;
! 955: else if ( CONT(a) < CONT(b) )
! 956: return -1;
! 957: else
! 958: return 0;
! 959: }
! 960: }
! 961:
! 962: void pthrootgfs(GFS a,GFS *b)
! 963: {
! 964: Z p;
! 965: int e,i;
! 966: GFS t,s;
! 967:
! 968: STOQ(characteristic_sf(),p);
! 969: e = extdeg_sf()-1;
! 970: t = a;
! 971: for ( i = 0; i < e; i++ ) {
! 972: pwrgfs(t,p,&s); t = s;
! 973: }
! 974: *b = t;
! 975: }
! 976:
! 977: void randomgfs(GFS *r)
! 978: {
! 979: unsigned int t;
! 980:
! 981: if ( !current_gfs_q1 )
! 982: error("addgfs : current_gfs_q is not set");
! 983: t = mt_genrand()%current_gfs_q;
! 984: indextogfs(t,r);
! 985: }
! 986:
! 987: /* arithmetic operations for 'immediate values of GFS */
! 988:
! 989: int _addsf(int a,int b)
! 990: {
! 991: if ( !a )
! 992: return b;
! 993: else if ( !b )
! 994: return a;
! 995:
! 996: a = IFTOF(a); b = IFTOF(b);
! 997:
! 998: if ( !current_gfs_ntoi ) {
! 999: a = a+b-current_gfs_q;
! 1000: if ( a == 0 )
! 1001: return 0;
! 1002: else {
! 1003: if ( a < 0 )
! 1004: a += current_gfs_q;
! 1005: return FTOIF(a);
! 1006: }
! 1007: }
! 1008:
! 1009: if ( a > b ) {
! 1010: /* tab[a]+tab[b] = tab[b](tab[a-b]+1) */
! 1011: a = current_gfs_plus1[a-b];
! 1012: if ( a < 0 )
! 1013: return 0;
! 1014: else {
! 1015: a += b;
! 1016: if ( a >= current_gfs_q1 )
! 1017: a -= current_gfs_q1;
! 1018: return FTOIF(a);
! 1019: }
! 1020: } else {
! 1021: /* tab[a]+tab[b] = tab[a](tab[b-a]+1) */
! 1022: b = current_gfs_plus1[b-a];
! 1023: if ( b < 0 )
! 1024: return 0;
! 1025: else {
! 1026: b += a;
! 1027: if ( b >= current_gfs_q1 )
! 1028: b -= current_gfs_q1;
! 1029: return FTOIF(b);
! 1030: }
! 1031: }
! 1032: }
! 1033:
! 1034: int _chsgnsf(int a)
! 1035: {
! 1036: if ( !a )
! 1037: return 0;
! 1038: else if ( !current_gfs_ntoi ) {
! 1039: a = current_gfs_q-IFTOF(a);
! 1040: return FTOIF(a);
! 1041: } else if ( current_gfs_q1&1 )
! 1042: return a;
! 1043: else {
! 1044: /* r^((q-1)/2) = -1 */
! 1045: a = IFTOF(a);
! 1046: a += (current_gfs_q1>>1);
! 1047: if ( a >= current_gfs_q1 )
! 1048: a -= current_gfs_q1;
! 1049: return FTOIF(a);
! 1050: }
! 1051: }
! 1052:
! 1053: int _subsf(int a,int b)
! 1054: {
! 1055: if ( !a )
! 1056: return _chsgnsf(b);
! 1057: else if ( !b )
! 1058: return a;
! 1059: else
! 1060: return _addsf(a,_chsgnsf(b));
! 1061: }
! 1062:
! 1063: int _mulsf(int a,int b)
! 1064: {
! 1065: int c;
! 1066:
! 1067: if ( !a || !b )
! 1068: return 0;
! 1069: else if ( !current_gfs_ntoi ) {
! 1070: a = IFTOF(a); b = IFTOF(b);
! 1071: DMAR(a,b,0,current_gfs_q,c);
! 1072: return FTOIF(c);
! 1073: } else {
! 1074: a = IFTOF(a) + IFTOF(b);
! 1075: if ( a >= current_gfs_q1 )
! 1076: a -= current_gfs_q1;
! 1077: return FTOIF(a);
! 1078: }
! 1079: }
! 1080:
! 1081: int _invsf(int a)
! 1082: {
! 1083: if ( !a ) {
! 1084: error("_invsf : division by 0");
! 1085: /* NOTREACHED */
! 1086: return -1;
! 1087: } else if ( !current_gfs_ntoi ) {
! 1088: a = invm(IFTOF(a),current_gfs_q);
! 1089: return FTOIF(a);
! 1090: } else {
! 1091: a = current_gfs_q1 - IFTOF(a);
! 1092: return FTOIF(a);
! 1093: }
! 1094: }
! 1095:
! 1096: int _divsf(int a,int b)
! 1097: {
! 1098: int c;
! 1099:
! 1100: if ( !b ) {
! 1101: error("_divsf : division by 0");
! 1102: /* NOTREACHED */
! 1103: return -1;
! 1104: } else if ( !current_gfs_ntoi ) {
! 1105: b = invm(IFTOF(b),current_gfs_q);
! 1106: a = IFTOF(a);
! 1107: DMAR(a,b,0,current_gfs_q,c);
! 1108: return FTOIF(c);
! 1109: } else if ( !a )
! 1110: return 0;
! 1111: else {
! 1112: a = IFTOF(a) - IFTOF(b);
! 1113: if ( a < 0 )
! 1114: a += current_gfs_q1;
! 1115: return FTOIF(a);
! 1116: }
! 1117: }
! 1118:
! 1119: int _pwrsf(int a,int b)
! 1120: {
! 1121: GFS at,ct;
! 1122: Z bt;
! 1123: int c;
! 1124:
! 1125: if ( !b )
! 1126: return _onesf();
! 1127: else if ( !a )
! 1128: return 0;
! 1129: if ( !current_gfs_ntoi ) {
! 1130: a = pwrm(current_gfs_q,IFTOF(a),b);
! 1131: return FTOIF(a);
! 1132: } else {
! 1133: iftogfs(a,&at);
! 1134: STOQ(b,bt);
! 1135: pwrgfs(at,bt,&ct);
! 1136: c = CONT(ct);
! 1137: return FTOIF(c);
! 1138: }
! 1139: }
! 1140:
! 1141: int _onesf()
! 1142: {
! 1143: return !current_gfs_ntoi ? FTOIF(1) : FTOIF(0);
! 1144: }
! 1145:
! 1146: int _itosf(int n)
! 1147: {
! 1148: int i;
! 1149:
! 1150: /* XXX */
! 1151: #if 0
! 1152: n %= current_gfs_p;
! 1153: #else
! 1154: n %= current_gfs_q;
! 1155: #endif
! 1156: if ( !n )
! 1157: return 0;
! 1158: i = !current_gfs_ntoi ? n : current_gfs_ntoi[n];
! 1159: i = FTOIF(i);
! 1160: if ( n < 0 )
! 1161: i = _chsgnsf(i);
! 1162: return i;
! 1163: }
! 1164:
! 1165: int _isonesf(int a)
! 1166: {
! 1167: return a == _onesf();
! 1168: }
! 1169:
! 1170: int _randomsf()
! 1171: {
! 1172: int t;
! 1173:
! 1174: t = (int) (mt_genrand() % current_gfs_q);
! 1175: if ( !current_gfs_ntoi )
! 1176: return t ? FTOIF(t) : 0;
! 1177: else
! 1178: return t!=current_gfs_q1 ? FTOIF(t) : 0;
! 1179: }
! 1180:
! 1181: int field_order_sf()
! 1182: {
! 1183: return current_gfs_q;
! 1184: }
! 1185:
! 1186: int characteristic_sf()
! 1187: {
! 1188: return current_gfs_p;
! 1189: }
! 1190:
! 1191: int extdeg_sf()
! 1192: {
! 1193: if ( !current_gfs_ext )
! 1194: return 1;
! 1195: else
! 1196: return UDEG(current_gfs_ext);
! 1197: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gfs.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2018 / engine