From kragen@dnaco.net Tue Sep 29 09:24:08 1998 Date: Tue, 29 Sep 1998 09:24:07 -0400 (EDT) From: Kragen To: bsittler@nmt.edu Subject: Sophie Germain primes Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: I was reading a paper by Schneier on e-mail security protocols, and came across this definition: \item[] {\bf Sophie Germain prime.} A Sophie Germain prime of first order is a prime $p$ such that $2p+1$ is also prime. For second order Sophie Germain primes, $2(2p+1)+1=4p+3$ is also prime and a similar pattern holds for general $n$-order primes. (This is LaTeX, btw.) I whipped up a couple of quick Perl scripts to find some, `sieve': #!/usr/bin/perl -w use strict; my $max = shift || 100; my @isprime = (1) x ($max + 1); for (my $i = 2; $i <= $max; $i ++) { if ($isprime[$i]) { print "$i\n"; for (my $j = $i; $j <= $max; $j += $i) { $isprime[$j] = 0; } } } and 'sophie-germain': #!/usr/bin/perl -w use strict; # Given a list of prime numbers, decide which ones are Sophie Germain primes. my %primes = map { chomp; $_ => 1 } <>; for (sort {$a <=> $b} keys %primes) { if (exists $primes{$_ * 2 + 1}) { print "$_\n"; } } Here's what I found, right quick: 1. There are a *lot* of Sophie Germain primes. There are 1171 of them between 1 and 100,000. 2. There are 9,592 prime numbers between 1 and 100,000, of which 1171 (or one in 8.1) are Sophie Germain primes. Of these, 205 (or one in 5.7) are second-order Sophie Germain primes, and of these, 37 (or one in 5.5) are third-order Sophie Germain primes. So the Sophie Germain relationship holds more often, proportionally, among Sophie Germain primes than among all primes, and more often still among second-order Sophie Germain primes. This prompts the question: is there a number whose Sophie Germain degree is infinite? 89 is a fifth-order Sophie Germain prime, but 2879, while prime, is not a Sophie Germain prime. Kragen -- Kragen Sitaker A well designed system must take people into account. . . . It's hard to build a system that provides strong authentication on top of systems that can be penetrated by knowing someone's mother's maiden name. -- Schneier