- Adam Young, Moti Yung, "Finding Length-3 Positive Cunningham Chains and their
Cryptographic Significance," Algorithmic Number Theory: Third International
Symposium---ANTS '98, Joe Buhler (Ed.), LNCS 1423, pages 289-298, 1998.
Abstract. A Cunningham chain of length k is a finite set of primes p

_{1},p_{2},...,p_{k}such that p_{i+1}= 2p_{i}+1, or p_{i+1}= 2p_{i}-1 for i = 1,2,3,...,k-1. In this paper we present an algorithm that finds Cunningham chains of the form p_{i+1}= 2p_{i}+1 for i = 2,3 and a prime p_{1}. Such a chain of primes were recently shown to be cryptographically significant in solving the problem of Auto-Recoverable Auto-Certifiable Cryptosystems [YY98]. For this application, the primes p_{1}and p_{2}should be large to provide for a secure enough setting for the discrete log problem. We introduce a number of simple but useful speed-up methods, such as what we call trial remaindering and explain a heuristic algorithm to find such chains. We ran our algorithm on a Pentium 166 MHz machine. We found values for p_{1}, starting at a value which is 512 bits and ending at a value for p_{1}which is 1,376 bits in length. We give some of these values in the appendix. The feasibility of efficiently finding such primes, in turn, enables the system in [YY98] which is a software-based public key system with key recovery (note that every cryptosystem which is suggested for actual use must be checked to insure that its computations are feasible).