“Complexity of Primes and Key of Cryptosystems.” Complexity in Science and Society, Olympia, Greece 22/07/2004.

In the first part of this talk we describe the theoretical ideas and the creation of the algorithm which permitted us to discover ten consecutive primes in arithmetic progression. In 1967 the first set of six consecutive primes in arithmetic progression was found by Lander and Parkin. In 1995 the first set of seven consecutive primes in arithmetic progression was found by Dubner and Nelson. Between November 1997 and March 1998, Dubner, Forbes, Lygeros, Mizony and Zimmermann succeeded in finding sets of eight, nine and ten consecutive primes in arithmetic progression. Although the conjecture of Hardy that there exist arbitrarily long sequences of consecutive primes in arithmetic progression was proved by Green and Tao in 2004, it is very likely that the ten primes will remain an effective record for a long time.

In the second one we present our contribution in integer factorization problem via elliptic curve which constitutes one of the best approaches to create effective and practical cryptosystems. Brent has predicted in 1985 that factors up to 50 digits could be found by the Elliptic Curve Method. Indeed, Montgomery found in November 1995 a factor of 47 digits, and Brent set in October 1997 a new genuine record with a factor of 48 digits. The original purpose of the ECMNET project was to make Brent’s prediction true, i.e. to find a factor of 50 digits or more by ECM. This goal was attained in September 1998, when Conrad Curry found a 53-digit factor. In December 1999, Lygeros and Mizony find a factor of 54 digits with a generalized Cunningham number.