APPENDIX A

Sample Parameters

This appendix presents elliptic curve domain parameters D = (q, FR, S, a, b, P, n, h) that are suitable for cryptographic use; see §4.2 for a review of the notation. In §A.1, an algorithm for testing irreducibility of a polynomial is presented. This algorithm can be used to generate a reduction polynomial for representing elements of the finite field F pm . Also included in §A.1 are tables of irreducible binary polynomials that are recommended by several standards including ANSI X9.62 and ANSI X9.63 as reduction polynomials for representing the elements of binary fields F2m . The 15 elliptic curves recommended by NIST in the FIPS 186-2 standard for U.S. federal government use are listed in §A.2.

A.1 Irreducible polynomials

A polynomial f (z) = am zm + · · · + a1z + a0 F p[z] of degree m ≥ 1 is irreducible over F p if f (z) cannot be factored as a product of polynomials in F p[z] each of degree less than m. Since f (z) is irreducible if and only if am−1 f (z) is irreducible, it suffices to only consider monic polynomials (i.e., polynomials with leading coefficient am = 1).

For any prime p and integer m ≥ 1, there exists at least one monic irreducible polynomial of degree m in F p[z]. In fact, the exact number of such polynomials is

Np (m) = 1 µ(d) pm/d ,

m d|m

258 A. Sample Parameters

where the summation index d ranges over all positive divisors of m, and the Mobius¨ function µ is defined as follows:

			1,	if d = 1,
µ(d)	=		0,	if d is divisible by the square of a prime,
			( 1)l ,	if d is the product of l distinct primes.
It has been shown that			−
				1			Np (m)	1
						≤
								≈		.
					2m		pm		m

Thus, if polynomials in F p[z] can be efficiently tested for irreducibility, then irreducible polynomials of degree m can be efficiently found by selecting random monic polynomials of degree m in F p[z] until an irreducible one is found—the expected number of trials is approximately m.

Algorithm A.1 is an efficient test for deciding irreducibility. It is based on the fact

that a polynomial f (z) of	degree m is irreducible over			F p	if and only if gcd( f (z), z pi	−
		m	.
z) = 1 for each i, 1 ≤ i ≤		2
Algorithm A.1 Testing a polynomial for irreducibility
INPUT: A prime p and a polynomial f (z) F p[z] of degree m ≥ 1.
OUTPUT: Irreducibility of		f (z).

1.u(z) ← z.

2.For i from 1 to m2 do:

2.1u(z) ← u(z) p mod f (z).

2.2d(z) ← gcd( f (z), u(z) − z).

2.3If d(z) = 1 then return(“reducible”).

3.Return(“irreducible”).

For each m, 2 ≤ m ≤ 600, Tables A.1 and A.2 list an irreducible trinomial or pentanomial f (z) of degree m over F2. The entries in the column labeled “T ” are the degrees of the nonzero terms of the polynomial excluding the leading term zm and the constant term 1. For example, T = k represents the trinomial zm + zk + 1, and T = (k3 , k2, k1) represents the pentanomial zm + zk3 + zk2 + zk1 + 1. The following criteria from the ANSI X9.62 and ANSI X9.63 standards were used to select the reduction polynomials:

(i)If there exists an irreducible trinomial of degree m over F2, then f (z) is the irreducible trinomial zm + zk + 1 for the smallest possible k.

(ii)If there does not exist an irreducible trinomial of degree m over F2, then f (z) is the irreducible pentanomial zm + zk3 + zk2 + zk1 + 1 for which (a) k3 is the smallest possible; (b) for this particular value of k3, k2 is the smallest possible; and (c) for these particular values of k3 and k2, k1 is the smallest possible.

A.1.

Irreducible polynomials

259

m

T

m

T

m

T

m

T

m

T

m

T

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

−		51	6, 3, 1		101	7, 6, 1		151	3		201	14		251	7, 4, 2
1		52	3		102	29		152	6, 3, 2		202	55		252	15
1		53	6, 2, 1		103	9		153	1		203	8, 7, 1		253	46
1		54	9		104	4, 3, 1		154	15		204	27		254	7, 2, 1
2		55	7		105	4		155	62		205	9, 5, 2		255	52
1		56	7, 4, 2		106	15		156	9		206	10, 9, 5		256	10, 5, 2
1		57	4		107	9, 7, 4		157	6, 5, 2		207	43		257	12
4, 3, 1		58	19		108	17		158	8, 6, 5		208	9, 3, 1		258	71
1		59	7, 4, 2		109	5, 4, 2		159	31		209	6		259	10, 6, 2
3		60	1		110	33		160	5, 3, 2		210	7		260	15
2		61	5, 2, 1		111	10		161	18		211	11, 10, 8		261	7, 6, 4
3		62	29		112	5, 4, 3		162	27		212	105		262	9, 8, 4
4, 3, 1		63	1		113	9		163	7, 6, 3		213	6, 5, 2		263	93
5		64	4, 3, 1		114	5, 3, 2		164	10, 8, 7		214	73		264	9, 6, 2
1		65	18		115	8, 7, 5		165	9, 8, 3		215	23		265	42
5, 3, 1		66	3		116	4, 2, 1		166	37		216	7, 3, 1		266	47
3		67	5, 2, 1		117	5, 2, 1		167	6		217	45		267	8, 6, 3
3		68	9		118	33		168	15, 3, 2		218	11		268	25
5, 2, 1		69	6, 5, 2		119	8		169	34		219	8, 4, 1		269	7, 6, 1
3		70	5, 3, 1		120	4, 3, 1		170	11		220	7		270	53
2		71	6		121	18		171	6, 5, 2		221	8, 6, 2		271	58
1		72	10, 9, 3		122	6, 2, 1		172	1		222	5, 4, 2		272	9, 3, 2
5		73	25		123	2		173	8, 5, 2		223	33		273	23
4, 3, 1		74	35		124	19		174	13		224	9, 8, 3		274	67
3		75	6, 3, 1		125	7, 6, 5		175	6		225	32		275	11, 10, 9
4, 3, 1		76	21		126	21		176	11, 3, 2		226	10, 7, 3		276	63
5, 2, 1		77	6, 5, 2		127	1		177	8		227	10, 9, 4		277	12, 6, 3
1		78	6, 5, 3		128	7, 2, 1		178	31		228	113		278	5
2		79	9		129	5		179	4, 2, 1		229	10, 4, 1		279	5
1		80	9, 4, 2		130	3		180	3		230	8, 7, 6		280	9, 5, 2
3		81	4		131	8, 3, 2		181	7, 6, 1		231	26		281	93
7, 3, 2		82	8, 3, 1		132	17		182	81		232	9, 4, 2		282	35
10		83	7, 4, 2		133	9, 8, 2		183	56		233	74		283	12, 7, 5
7		84	5		134	57		184	9, 8, 7		234	31		284	53
2		85	8, 2, 1		135	11		185	24		235	9, 6, 1		285	10, 7, 5
9		86	21		136	5, 3, 2		186	11		236	5		286	69
6, 4, 1		87	13		137	21		187	7, 6, 5		237	7, 4, 1		287	71
6, 5, 1		88	7, 6, 2		138	8, 7, 1		188	6, 5, 2		238	73		288	11, 10, 1
4		89	38		139	8, 5, 3		189	6, 5, 2		239	36		289	21
5, 4, 3		90	27		140	15		190	8, 7, 6		240	8, 5, 3		290	5, 3, 2
3		91	8, 5, 1		141	10, 4, 1		191	9		241	70		291	12, 11, 5
7		92	21		142	21		192	7, 2, 1		242	95		292	37
6, 4, 3		93	2		143	5, 3, 2		193	15		243	8, 5, 1		293	11, 6, 1
5		94	21		144	7, 4, 2		194	87		244	111		294	33
4, 3, 1		95	11		145	52		195	8, 3, 2		245	6, 4, 1		295	48
1		96	10, 9, 6		146	71		196	3		246	11, 2, 1		296	7, 3, 2
5		97	6		147	14		197	9, 4, 2		247	82		297	5
5, 3, 2		98	11		148	27		198	9		248	15, 14, 10		298	11, 8, 4
9		99	6, 3, 1		149	10, 9, 7		199	34		249	35		299	11, 6, 4
4, 3, 2		100	15		150	53		200	5, 3, 2		250	103		300	5

Table A.1. Irreducible binary polynomials of degree m, 2 ≤ m ≤ 300.

260		A. Sample Parameters
	m	T		m	T			m	T	m	T	m	T	m	T
	301	9, 5, 2		351	34			401	152	451	16, 10, 1	501	5, 4, 2	551	135
	302	41		352	13, 11, 6			402	171	452	6, 5, 4	502	8, 5, 4	552	19, 16, 9
	303	1		353	69			403	9, 8, 5	453	15, 6, 4	503	3	553	39
	304	11, 2, 1		354	99			404	65	454	8, 6, 1	504	15, 14, 6	554	10, 8, 7
	305	102		355	6, 5, 1			405	13, 8, 2	455	38	505	156	555	10, 9, 4
	306	7, 3, 1		356	10, 9, 7			406	141	456	18, 9, 6	506	23	556	153
	307	8, 4, 2		357	11, 10, 2			407	71	457	16	507	13, 6, 3	557	7, 6, 5
	308	15		358	57			408	5, 3, 2	458	203	508	9	558	73
	309	10, 6, 4		359	68			409	87	459	12, 5, 2	509	8, 7, 3	559	34
	310	93		360	5, 3, 2			410	10, 4, 3	460	19	510	69	560	11, 9, 6
	311	7, 5, 3		361	7, 4, 1			411	12, 10, 3	461	7, 6, 1	511	10	561	71
	312	9, 7, 4		362	63			412	147	462	73	512	8, 5, 2	562	11, 4, 2
	313	79		363	8, 5, 3			413	10, 7, 6	463	93	513	26	563	14, 7, 3
	314	15		364	9			414	13	464	19, 18, 13	514	67	564	163
	315	10, 9, 1		365	9, 6, 5			415	102	465	31	515	14, 7, 4	565	11, 6, 1
	316	63		366	29			416	9, 5, 2	466	14, 11, 6	516	21	566	153
	317	7, 4, 2		367	21			417	107	467	11, 6, 1	517	12, 10, 2	567	28
	318	45		368	7, 3, 2			418	199	468	27	518	33	568	15, 7, 6
	319	36		369	91			419	15, 5, 4	469	9, 5, 2	519	79	569	77
	320	4, 3, 1		370	139			420	7	470	9	520	15, 11, 2	570	67
	321	31		371	8, 3, 2			421	5, 4, 2	471	1	521	32	571	10, 5, 2
	322	67		372	111			422	149	472	11, 3, 2	522	39	572	12, 8, 1
	323	10, 3, 1		373	8, 7, 2			423	25	473	200	523	13, 6, 2	573	10, 6, 4
	324	51		374	8, 6, 5			424	9, 7, 2	474	191	524	167	574	13
	325	10, 5, 2		375	16			425	12	475	9, 8, 4	525	6, 4, 1	575	146
	326	10, 3, 1		376	8, 7, 5			426	63	476	9	526	97	576	13, 4, 3
	327	34		377	41			427	11, 6, 5	477	16, 15, 7	527	47	577	25
	328	8, 3, 1		378	43			428	105	478	121	528	11, 6, 2	578	23, 22, 16
	329	50		379	10, 8, 5			429	10, 8, 7	479	104	529	42	579	12, 9, 7
	330	99		380	47			430	14, 6, 1	480	15, 9, 6	530	10, 7, 3	580	237
	331	10, 6, 2		381	5, 2, 1			431	120	481	138	531	10, 5, 4	581	13, 7, 6
	332	89		382	81			432	13, 4, 3	482	9, 6, 5	532	1	582	85
	333	2		383	90			433	33	483	9, 6, 4	533	4, 3, 2	583	130
	334	5, 2, 1		384	12, 3, 2			434	12, 11, 5	484	105	534	161	584	14, 13, 3
	335	10, 7, 2		385	6			435	12, 9, 5	485	17, 16, 6	535	8, 6, 2	585	88
	336	7, 4, 1		386	83			436	165	486	81	536	7, 5, 3	586	7, 5, 2
	337	55		387	8, 7, 1			437	6, 2, 1	487	94	537	94	587	11, 6, 1
	338	4, 3, 1		388	159			438	65	488	4, 3, 1	538	195	588	35
	339	16, 10, 7		389	10, 9, 5			439	49	489	83	539	10, 5, 4	589	10, 4, 3
	340	45		390	9			440	4, 3, 1	490	219	540	9	590	93
	341	10, 8, 6		391	28			441	7	491	11, 6, 3	541	13, 10, 4	591	9, 6, 4
	342	125		392	13, 10, 6			442	7, 5, 2	492	7	542	8, 6, 1	592	13, 6, 3
	343	75		393	7			443	10, 6, 1	493	10, 5, 3	543	16	593	86
	344	7, 2, 1		394	135			444	81	494	17	544	8, 3, 1	594	19
	345	22		395	11, 6, 5			445	7, 6, 4	495	76	545	122	595	9, 2, 1
	346	63		396	25			446	105	496	16, 5, 2	546	8, 2, 1	596	273
	347	11, 10, 3		397	12, 7, 6			447	73	497	78	547	13, 7, 4	597	14, 12, 9
	348	103		398	7, 6, 2			448	11, 6, 4	498	155	548	10, 5, 3	598	7, 6, 1
	349	6, 5, 2		399	26			449	134	499	11, 6, 5	549	16, 4, 3	599	30
	350	53		400	5, 3, 2			450	47	500	27	550	193	600	9, 5, 2

Table A.2. Irreducible binary polynomials of degree m, 301 ≤ m ≤ 600.