Arndt - Algorithms for Programmers (523138), страница 44
Текст из файла (страница 44)
Choosing those PPs where the highest nonzero coefficient is aslow as possible one gets the list in [FXT: file data/lowbit-primpoly.txt].2,1,03,1,04,1,05,2,06,1,01 Thereby the one-liner x=127;for(z=1,x-1,if(polisirreducible(Mod(1,2)+t^z+t^x),print1(" ",z))) finds all primitive trinomials for certain exponents of Mersenne primes in no time:89: 38 51127: 1 7 15 30 63 64 97 112 120126521: 32 48 158 168 353 363 473 489607: 105 147 273 334 460 502.CHAPTER 12. SHIFT REGISTER SEQUENCES2587,1,08,4,3,2,09,4,010,3,011,2,012,6,4,1,0[-snip-]31,3,032,7,5,3,2,1,033,6,4,1,034,7,6,5,2,1,0[-snip-]397,8,7,6,5,1,0398,10,8,6,4,1,0399,9,6,4,2,1,0400,5,3,2,0The corresponding data actually used for the computations can be found in [FXT: fileauxbit/lowbitprimpoly.h]:extern const ulong lowbit_primpoly[]={// hex_val, // ==dec_val (deg) [weight]0x1,// 1 (0) [1]0x3,// 3 (1) [2]0x7UL,// ==7 (2) [3]0xbUL,// ==11 (3) [3]0x13UL,// ==19 (4) [3]0x25UL,// ==37 (5) [3]0x43UL,// ==67 (6) [3]0x83UL,// ==131 (7) [3]0x11dUL,// ==285 (8) [5]0x211UL,// ==529 (9) [3]0x409UL,// ==1033 (10) [3]0x805UL,// ==2053 (11) [3]0x1053UL,// ==4179 (12) [5][-snip-]0x80000009UL,// ==2147483657 (31) [3]0x1000000afUL,// ==4294967471 (32) [7]0x200000053UL,// ==8589934675 (33) [5]0x4000000e7UL,// ==17179869415 (34) [7][-snip-]In fact the highest k 6= n so that ck 6= 0 grows slowly with n.
For n ≤ 400 the entries where the secondcoefficient is bigger than in all prior lines are:2,1,05,2,08,4,3,2,012,6,4,1,032,7,5,3,2,1,046,8,5,3,2,1,0104,9,8,6,5,4,3,2,0108,10,9,7,6,5,4,3,2,1,0360,12,9,8,6,4,3,1,0Thereby one can store the list in compact format even if it extends to high degrees.Note that the ‘reflected’ form of a PP is again a PP: if n, a, b, c, 0 is primitive, then n − a, n − b, n − c, 0is also primitive.A list of all PPs for degree n = 256 with the second-highest order ≤ 15 is given in [FXT: filedata/lowbit256-primpoly.txt]256,10,5,2,0256,10,8,5,4,1,0256,10,9,8,7,4,2,1,0256,11,8,4,3,2,0256,11,8,6,4,3,0256,11,10,9,4,2,0256,11,10,9,7,4,0256,12,7,5,4,2,0256,12,8,7,6,3,0[-snip-]CHAPTER 12. SHIFT REGISTER SEQUENCES259256,15,14,13,12,10,9,8,7,6,5,4,3,2,0256,15,14,13,12,11,9,6,0256,15,14,13,12,11,9,8,6,4,3,2,0256,15,14,13,12,11,10,7,5,4,3,2,0256,15,14,13,12,11,10,8,6,3,2,1,0[-end- (a few PP with second degree 16 follow)]256,16,3,1,0256,16,11,9,7,2,0Similar tables for degrees 127, 128 and 521 can be found under the obvious names.The total number of PPs of degree n is Pn = φ(2n − 1)/n:n12345678910Pn11226618164860n11121314151617181920Pn17614463075618002048771077762759424000n21222324252627282930Pn8467212003235696027648012960001719900420249647416321840780817820000nIf n is the exponent of a Mersenne prime we have Pn = 2 n−2 , this is almost the number of length-nnecklaces: Pn = Nn − 2.
For n a power of two the Pn = 2x where x = 2n−2 − n − 1, this is the numberof length-2n SRS.For degree n up to 8 the complete list of PPs is (see [FXT: file data/all-primpoly.txt] which extendsto degree 11):2,1,03,1,03,2,04,1,04,3,05,2,05,3,05,3,2,1,05,4,2,1,05,4,3,1,05,4,3,2,06,1,06,4,3,1,06,5,06,5,2,1,06,5,3,2,06,5,4,1,07,1,07,3,07,3,2,1,07,4,07,4,3,2,07,5,2,1,07,5,3,1,07,5,4,3,07,5,4,3,2,1,07,6,07,6,3,1,07,6,4,1,07,6,4,2,07,6,5,2,07,6,5,3,2,1,07,6,5,4,07,6,5,4,2,1,07,6,5,4,3,2,08,4,3,2,08,5,3,1,08,5,3,2,08,6,3,2,08,6,4,3,2,1,08,6,5,1,08,6,5,2,08,6,5,3,08,6,5,4,08,7,2,1,08,7,3,2,08,7,5,3,08,7,6,1,08,7,6,3,2,1,08,7,6,5,2,1,08,7,6,5,4,2,0A list a primitive trinomials is given in [FXT: file data/all-trinomial-primpoly.txt].
Primitive trinomials of the most simple form n, 1, 0 ∼ xn + x + 1 exist for n ≤ 400 andn ∈ 2, 3, 4, 6, 7, 15, 22, 60, 63, 127, 153. In fact these numbers are the sequence A073639 in [64], whereone finds in addition 471, 532, 865, 900, 1366 with the next candidate being 4495.PPs with exactly five nonzero coefficients are given in [FXT: file data/pentanomial-primpoly.txt]. Noprimitive pentanomial exists for n < 5 but for all higher degrees one seems to exist (to my knowledge thishas not been proven so far).
Entries of the form xn +x3 +x2 +x+1 are there for n ∈ 5, 7, 17, 25, 31, 41, 151For n ≤ 400 the entries where the second coefficient is bigger than in all prior lines are:5,3,2,1,06,4,3,1,012,6,4,1,032,7,6,2,034,8,4,3,048,9,7,4,072,10,9,3,0CHAPTER 12. SHIFT REGISTER SEQUENCES26088,11,9,8,0108,12,11,5,0141,13,6,1,0168,16,9,6,0322,17,2,1,0360,26,25,1,0PkA list of PPs of the special form xn + j=0 xj is given in [FXT: file data/lowblock-primpoly.txt].There an entry like n, k = 16,5 should be read as 16,5,4,3,2,1,0 = x16 + x5 + x4 + x3 + x2 + x + 1.For n ≤ 400 the entries where the second coefficient is bigger than in all prior lines are:2,15,310,713,1133,1934,2536,2955,3968,5376,5981,6185,83116,111164,147228,223311,285365,36312.2.2Irreducible polynomials of certain forms *This section consists of some tables of irreducible polynomials of special forms.Low-block and full polynomialsThe Plist [FXT: file data/all-lowblock-irredpoly.txt] contains all irreducible polynomials of the formqxs + k=0 xq where q < s and s ≤ 400.
Note that the reversed polynomials are also irreducible. A subsetPd−1of the list are those polynomials where all coefficients are one: The ‘full’ polynomial p = k=0 xk =1 + x + x2 + . . . + xd−1 can be irreducible only if d (= s + 1) is prime. The first examples of suchpolynomials that are irreducible ared:2:3:5:11:(irred. poly.)x + 1x^2 + x + 1x^4 + x^3 + x^2 + x + 1x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1In a way these are the ‘Mersenne primes’ among the polynomials over GF (2).
Note that, with theexception of x2 + x + 1, none of them is primitive. The list of those primes up to d = 2000 is:2, 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139,149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373,379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563,587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821,827, 829, 853, 859, 877, 883, 907, 941, 947, 1019, 1061, 1091, 1109,1117, 1123, 1171, 1187, 1213, 1229, 1237, 1259, 1277, 1283, 1291,1301, 1307, 1373, 1381, 1427, 1451, 1453, 1483, 1493, 1499, 1523,1531, 1549, 1571, 1619, 1621, 1637, 1667, 1669, 1693, 1733, 1741,1747, 1787, 1861, 1867, 1877, 1901, 1907, 1931, 1949, 1973, 1979,1987, 1997it can be generated with the pari/gp one-liner:forprime(d=2,N,s=sum(x=0,d-1,t^x);if(polisirreducible(Mod(1,2)*s),print1(", ",d)))where N is the search limit.CHAPTER 12. SHIFT REGISTER SEQUENCES261Alternating polynomialsThe ‘alternating’ polynomial 1 +is odd:d:1:3:5:Pdk=0x2 k+1 = 1 + x + x3 + x5 .
. . + x2d+1 can be irreducible only if d(irred. poly.)x^3 + x + 1x^7 + x^5 + x^3 + x + 1x^11 + x^9 + x^7 + x^5 + x^3 + x + 1The list up to d = 5001, 3, 5, 7, 9, 13, 23, 27, 31, 37, 63, 69, 117, 119, 173, 219, 223,247, 307, 363, 383, 495can be obtained viafor(d=1,N,p=(1+sum(t=0,d,x^(2*t+1)));if(polisirreducible(Mod(1,2)*p),print1(d,", ")))Special trinomials I:1 + xd + xk dThe polynomial p = 1 + xd + x2d is irreducible whenever d is a power of three:1:3:9:27:81:243:...x^2 + x + 1x^6 + x^3 + 1x^18 + x^9 + 1x^54 + x^27 + 1x^162 + x^81 + 1x^486 + x^243 + 1Similarly, p = 1 + xd + x3d is irreducible whenever d is a power of seven:1:7:49:343:x^3 + x + 1x^21 + x^7 + 1x^147 + x^49 + 1x^1029 + x^343 + 1The test for the irreducibility of p = 1 + xd + x4d can be done viafor(d=1,N,(p=(1+x^d+x^(4*d))); if(polisirreducible(Mod(1,2)*p),print(d,":gets1:3:5:9:15:25:27:45:75:81:125:135:225:243:375:405:...x^4 + x + 1x^12 + x^3 + 1x^20 + x^5 + 1x^36 + x^9 + 1x^60 + x^15 + 1x^100 + x^25 + 1x^108 + x^27 + 1x^180 + x^45 + 1x^300 + x^75 + 1x^324 + x^81 + 1x^500 + x^125 + 1x^540 + x^135 + 1x^900 + x^225 + 1x^972 + x^243 + 1x^1500 + x^375 + 1x^1620 + x^405 + 1The list of reversed polynomials1:3:5:9:15:25:27:45:75:81:125:135:225:243:...x^4 + x^3 + 1x^12 + x^9 + 1x^20 + x^15 + 1x^36 + x^27 + 1x^60 + x^45 + 1x^100 + x^75 + 1x^108 + x^81 + 1x^180 + x^135 + 1x^300 + x^225 + 1x^324 + x^243 + 1x^500 + x^375 + 1x^540 + x^405 + 1x^900 + x^675 + 1x^972 + x^729 + 1",p)))OneCHAPTER 12.
SHIFT REGISTER SEQUENCESMight help to see that d always factors as d = 3i 5j ,enhanced) using262i, j ∈ N, that is the list can be reproduced (andfordiv((3*5)^7,i,s=(i);print1(" ",4*s))4, 12, 20, 36, 60, 100, 108, 180, 300, 324, 500, 540, 900, 972,1500, 1620, 2500, 2700, 2916, 4500, 4860, 7500, 8100, 8748, 12500,13500, 14580, 22500, 24300, 37500, 40500, 43740, 62500, 67500,72900, 112500, 121500, 187500, 202500, 218700, 312500, 337500,364500, 562500, 607500, 937500, 1012500, 1093500, 1687500, 1822500,2812500, 3037500, 5062500, 5467500, 8437500, 9112500, 15187500,25312500, 27337500, 45562500, 75937500, 136687500, 227812500,683437500, ...Similar regularities can be observed for related forms, likefor(d=1,N,(p=(1+x^(5*d)+x^(6*d)));if(polisirreducible(Mod(1,2)*p),print(d,":1:3:7:9:21:27:49:63:81:147:189:",p)))x^6 + x^5 + 1x^18 + x^15 + 1x^42 + x^35 + 1x^54 + x^45 + 1x^126 + x^105 + 1x^162 + x^135 + 1x^294 + x^245 + 1x^378 + x^315 + 1x^486 + x^405 + 1x^882 + x^735 + 1x^1134 + x^945 + 1Special trinomials II:1 + xd−k + xdIrreducible polynomials of the form p = 1 + xd−1 + xd .
The first few are2:3:4:6:7:...x^2x^3x^4x^6x^7+++++x +x^2x^3x^5x^6++++11111The list for d ≤ 1000:1, 2, 3, 4, 6, 7, 9, 15, 22, 28, 30, 46, 60, 63,127, 153, 172, 303, 471, 532, 865, 900, ...The equivalent list for p = 1 + xd−2 + xd and d ≤ 1000:3, 5, 11, 21, 29, 35, 93, 123, 333, 845, ...And for p = 1 + xd−3 + xd and d ≤ 1000:4, 5, 6, 7, 10, 12, 17, 18, 20, 25, 28, 31, 41, 52, 66,130, 151, 180, 196, 503, 650, 761, 986, ...p = 1 + xd−4 + xd is irreducible for only few d ≤ 1000:7, 9, 15, 39, 57, 81, 105, ...p = 1 + xd−5 + xd and d ≤ 1000:6, 9, 12, 14, 17, 20, 23, 44, 47, 63, 84,129, 236, 278, 279, 297, 300, 647, 726, 737,12.3Computations with binary polynomialsFunctions that operate on binary polynomials (see section 12.2) can be found in [FXT: fileauxbit/bitpolmodmult.h].
To represent a polynomial over Z/2Z as binary word one simply has toset a bit where the coefficient is one. We stick to the convention that the constant term goes to the lowestbit.CHAPTER 12. SHIFT REGISTER SEQUENCES12.3.1263Basic operationsThe following routines can be found in [FXT: file auxbit/bitpol.h].Multiplication of two polynomials is identical to the usual (binary algorithm for) multiplication, exceptthat no carry occurs:inline ulong bitpol_mult(ulong a, ulong b)// Return A * B// b=2 corresponds to multiplication with ’x’// Note that the result silently overflows// if deg(A)+deg(B) > BITS_PER_LONG{ulong t = 0;while ( b ){if ( b & 1 ) t ^= a;b >>= 1;a <<= 1;}return t;}With a multiplication function at hand, it is straight forward to implement the algorithm for binaryexponentiation: (Note that overflow will occur even for moderate exponents)inline ulong bitpol_power(ulong a, ulong x)// Return A ** x{if ( 0==x ) return 1;ulong s = a;while ( 0==(x&1) ){s = bitpol_square(s);x >>= 1;}a = s;while ( 0!=(x>>=1) ){s = bitpol_square(s);if ( x & 1 ) a = bitpol_mult(a, s);}return a;}The remainder with polynomial division can be implemented asinline ulong bitpol_rem(ulong a, ulong b)// Return R = A % B = A - (A/B)*B{while ( b <= a ){ulong t = b;while ( (a^t) > t ) t <<= 1;// =^= while ( highest_bit(a) > highest_bit(t) )a ^= t;}}Polynomial divisioninline ulong bitpol_div(ulong a, ulong b)// Return R = A / B{if ( b <= a ){ulong t = b;ulong qb = 1;while ( (a^t) > t ) { t <<= 1; qb <<= 1; }ulong h = highest_bit(t);ulong q = 0;dot <<= 1;CHAPTER 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
