Cunningham chain

A Cunningham chain (after Allan Joseph Champneys Cunningham ) of the first kind is a sequence of prime numbers of the form:

${\displaystyle a_{0}=p\quad a_{n+1}=2\!\cdot \!a_{n}+1,}$

i.e. p, 2p + 1, 2 (2p + 1) +1, 2 (2 (2p + 1) +1) +1, ...

All prime numbers in such a sequence, with the exception of the last prime number, are Sophie Germain primes .

The first Cunningham chain is the sequence: 2, 5, 11, 23, 47. It results for and can be explicitly represented as follows: a _n = 3 · 2 ⁿ - 1 for n = 0, 1, 2, 3 , 4. ${\displaystyle a_{0}=2}$

A Cunningham chain of the second kind is a sequence of prime numbers of the form:

${\displaystyle a_{0}=p\quad a_{n+1}=2\!\cdot \!a_{n}-1}$

Two examples of Cunningham chains of the second type are sequence 2, 3, 5 and sequence 1531, 3061, 6121, 12241, 24481.

The longest known Cunningham chain of any kind is of the first kind, has length 17 and starts with 2759832934171386593519. It was found in March 2008. The first chain of length 16 was found in 1997.

Cryptography

Cunningham chains are studied in cryptography because they provide the framework for an implementation of the Elgamal cryptosystem, which is used as the Elgamal encryption method and Elgamal signature method .

Tables with Cunningham chains

Cunningham chains of the first type with k links

Smallest Cunningham chain with k chain links
k	p
1	13
2	3
3	41
4th	1229
5	2
6th	89
7th	1,122,659
8th	19,099,919
9	85,864,769
10	26,089,808,579
11	665.043.081.119
12	554,688,278,429
13	4,090,932,431,513,069
14th	95,405,042,230,542,329

k = 5:

p	2p + 1	4p + 3	8p + 7	16p + 15
2	5	11	23	47
53639	107279	214559	429119	858239
53849	107699	215399	430799	861599
61409	122819	245639	491279	982559
66749	133499	266999	533999	1067999
143609	287219	574439	1148879	2297759
167729	335459	670919	1341839	2683679
186149	372299	744599	1489199	2978399
206369	412739	825479	1650959	3301919
268049	536099	1072199	2144399	4288799
296099	592199	1184399	2368799	4737599
340919	681839	1363679	2727359	5454719
422069	844139	1688279	3376559	6753119
446609	893219	1786439	3572879	7145759

k = 6:

p	2p + 1	4p + 3	8p + 7	16p + 15	32p + 31
89	179	359	719	1439	2879
63419	126839	253679	507359	1014719	2029439
127139	254279	508559	1017119	2034239	4068479
405269	810539	1621079	3242159	6484319	25937279

Cunningham chains of the second type with k links

Smallest Cunningham chain with k chain links
k	p
1	11
2	7th
3	2
4th	2131
5	1531

k = 5:

p	2p-1	4p-3	8p-7	16p-15
1531	3061	6121	12241	24481
6841	13681	27361	54721	109441
15391	30781	61561	123121	246241
44371	88741	177481	354961	709921
57991	115981	231961	463921	927841
83431	166861	333721	667441	1334881
105871	211741	423481	846961	1693921

k = 7:

p	2p-1	4p-3	8p-7	16p-15	32p-31	64p-63
16651	33301	66601	133201	266401	532801	1065601

A generalized Cunningham chain

A sequence of prime numbers of the form: p, a p + b , a ( a p + b ) + b , ... with a fixed a and a fixed b , which are prime to each other, is called a generalized Cunningham chain.

• Examples of generalized Cunningham chains with the number k = 5

k = 5:

a	b	p	a (p) + b = ap + b	a (ap + b) + b = a 2 p + ab + b	a (a 2 p + ab + b) + b = a 3 p + a 2 b + ab + b	a (a 3 p + a 2 b + ab + b) + b = a 4 p + a 3 b + a 2 b + ab + b
3	2	1129	3389	10169	30509	91529
5	2	373	1867	9337	46687	233437

literature

• David Darling: The Universal Book of Mathematics. From Abracadabra to Zeno's Paradoxes . John Wiley and Sons, Hoboken NJ 2004, ISBN 0-471-27047-4 , p. 84.

Web links

• longest CC (of the first kind) and other records (English)
• longest CC (of the second kind) and other records (English)

Individual evidence

1. ^ J. Wroblewski: 1st known CC17
2. ^ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III . New York: Springer (1998): 290