On this page, all polynomials are listed by their coefficients with the least-significant bit on the left. For example, x^3 + x + 1 is listed as 1101.

I. Comprehensive Testing of Irreducible/Primitive TSRs.

II. Proportion of Irreducible TSRs which are Primitive.

III. Irreducible Pairs.

I. Comprehensive Testing of Irreducible/Primitive TSRs.

Linear Feedback Shift Registers (LFSRs) of order n and primitive transformations of order m were combined to form Transformation Shift Registers (TSRs). All possibilities for small m and n were combined and the resulting characteristic polynomials for the TSRs were tested for irreducibility and (if necessary) primitivity. In the tables of results, the characteristic polynomials of the LFSRs are listed in the first column. Each subsequent column represents a particular primitive transformation. To ensure the columns line up neatly, the characteristic polynomials of the transformations are listed separately. A '.' heads each column and a 'x' marks every fifth transformation. If a particular LFSR and transformation form an irreducible TSR, there will be a 'I' in the relevant table entry. If the TSR is also primitive, there will be a 'P' instead.

Please choose the parameters m,n

		m
		1	2	3	4	5	6	7	8	9	10
n	1	m1n1	m2n1	m3n1	m4n1	m5n1	m6n1	m7n1	m8n1	m9n1	m10n1
	2	m1n2	m2n2	m3n2	m4n2	m5n2	m6n2	m7n2	m8n2	m9n2	m10n2
	3	m1n3	m2n3	m3n3	m4n3	m5n3	m6n3	m7n3	m8n3	m9n3	m10n3
	4	m1n4	m2n4	m3n4	m4n4	m5n4	m6n4	m7n4	m8n4	m9n4	m10n4
	5	m1n5	m2n5	m3n5	m4n5	m5n5	m6n5	m7n5	m8n5	m9n5	m10n5
	6	m1n6	m2n6	m3n6	m4n6	m5n6	m6n6	m7n6	m8n6	m9n6	m10n6
	7	m1n7	m2n7	m3n7	m4n7	m5n7	m6n7	m7n7	m8n7	m9n7	m10n7
	8	m1n8	m2n8	m3n8	m4n8	m5n8	m6n8	m7n8	m8n8	m9n8	m10n8
	9	m1n9	m2n9	m3n9	m4n9	m5n9	m6n9	m7n9	m8n9	m9n9	m10n9
	10	m1n10	m2n10	m3n10	m4n10	m5n10	m6n10	m7n10	m8n10	m9n10	m10n10
	11	m1n11	m2n11	m3n11	m4n11	m5n11	m6n11	m7n11	m8n11	m9n11	m10n11
	12	m1n12	m2n12	m3n12	m4n12	m5n12	m6n12	m7n12	m8n12	m9n12	m10n12

II. Proportion of Irreducible TSRs which are Primitive.

Values in the last two columns have been rounded.

m	n	# of P	# of I	Actual P:I	Predicted P:I
1	2	1	1	1.00000	0.66667
1	3	2	2	1.00000	0.85714
1	4	2	3	0.66667	0.53333
1	5	6	6	1.00000	0.96774
1	6	6	9	0.66667	0.57143
1	7	18	18	1.00000	0.99213
1	8	16	30	0.53333	0.50196
1	9	48	56	0.85714	0.84540
1	10	60	99	0.60606	0.58651
1	11	176	186	0.94624	0.94577
1	12	144	335	0.42985	0.42198
2	2	1	1	1.00000	0.80000
2	3	1	2	0.50000	0.85714
2	4	2	2	1.00000	0.75294
2	5	5	6	0.83333	0.87977
2	6	5	6	0.83333	0.63297
2	7	14	16	0.87500	0.96905
2	8	18	24	0.75000	0.75001
2	9	28	42	0.66667	0.80091
2	10	58	76	0.76316	0.68665
2	11	141	154	0.91558	0.94439
2	12	146	262	0.55725	0.59326
3	2	1	1	1.00000	0.66667
3	3	2	2	1.00000	0.98630
3	4	4	5	0.80000	0.49231
3	5	4	4	1.00000	0.96133
3	6	14	17	0.82353	0.62293
3	7	20	22	0.90909	0.98918
3	8	15	30	0.50000	0.46143
3	9	72	74	0.97297	0.98630
3	10	44	96	0.45833	0.58087
3	11	168	174	0.96552	0.94577
3	12	185	415	0.44578	0.44347
4	2	1	1	1.00000	0.94118
4	3	3	5	0.60000	0.79121
4	4	2	2	1.00000	0.93751
4	5	6	9	0.66667	0.85831
4	6	6	9	0.66667	0.74158
4	7	18	19	0.94737	0.92736
4	8	30	32	0.93750	0.93750
4	9	43	64	0.67188	0.71272
4	10	62	85	0.72941	0.80781
4	11	220	237	0.92827	0.94156
4	12	262	374	0.70053	0.72999
5	2	2	3	0.66667	0.60606
5	3	4	4	1.00000	0.85147
5	4	5	11	0.45455	0.47302
5	5	14	14	1.00000	0.99778
5	6	18	26	0.69231	0.51448
5	7	68	68	1.00000	0.97814
5	8	34	86	0.39535	0.44519
5	9	172	216	0.79630	0.83844
5	10	169	297	0.56902	0.60216
5	11	509	544	0.93566	0.94440
5	12	380	1034	0.36750	0.36431
6	2	3	4	0.75000	0.73846
6	3	5	12	0.41667	0.93439
6	4	2	2	1.00000	0.69214
6	5	14	18	0.77778	0.87130
6	6	22	34	0.64706	0.66520
6	7	67	77	0.87013	0.96600
6	8	50	71	0.70423	0.68132
6	9	237	279	0.84946	0.93438
6	10	178	282	0.63121	0.61697
6	11	621	671	0.92548	0.93025
6	12	625	982	0.63646	0.62202
7	2	6	9	0.66667	0.65116
7	3	10	12	0.83333	0.85460
7	4	11	37	0.29730	0.49852
7	5	27	28	0.96429	0.95410
7	6	51	102	0.50000	0.55638
7	7	200	200	1.00000	1.00000
7	8	127	268	0.47388	0.46919
7	9	409	504	0.81151	0.84288
7	10	478	852	0.56103	0.56278
7	11	1327	1412	0.93980	0.94577
7	12	1159	3148	0.36817	0.39288
8	2	7	7	1.00000	0.99611
8	3	20	39	0.51282	0.78793
8	4	9	9	1.00000	0.99609
8	5	62	91	0.68132	0.85829
8	6	23	40	0.57500	0.77561
8	7	124	134	0.92537	0.92736
8	8	188	190	0.98947	0.99454
8	9	333	567	0.58730	0.70810
8	10	587	685	0.85693	0.85495
8	11	1557	1656	0.94022	0.93890
8	12	1784	2337	0.76337	0.77158
9	2	16	25	0.64000	0.63158
9	3	34	34	1.00000	1.00000
9	4	36	99	0.36364	0.44963
9	5	100	103	0.97087	0.95977
9	6	146	242	0.60744	0.63157
9	7	583	643	0.90669	0.98917
9	8	288	650	0.44308	0.42044
9	9	1499	1501	0.99867	0.99960
9	10	1239	2441	0.50758	0.54940
9	11	3738	3982	0.93872	0.94101
9	12	3887	8767	0.44337	0.44962
10	2	25	31	0.80645	0.78049
10	3	70	140	0.50000	0.84889
10	4	21	28	0.75000	0.73456
10	5	228	230	0.99130	0.99356
10	6	106	201	0.52736	0.60110
10	7	591	626	0.94409	0.95199
10	8	469	645	0.72713	0.73171
10	9	1515	2220	0.68243	0.79191
10	10	1946	2573	0.75632	0.76769
10	11	6033	6480	0.93102	0.94270
10	12	4848	8688	0.55801	0.56339

III. Irreducible Pairs.

Please choose the order of the irreducible polynomials

Order
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20