From kragen@dnaco.net Tue Sep 29 09:24:08 1998
Date: Tue, 29 Sep 1998 09:24:07 -0400 (EDT)
From: Kragen <kragen@dnaco.net>
To: bsittler@nmt.edu
Subject: Sophie Germain primes
Message-ID: <Pine.SUN.3.96.980929085523.21177G-100000@picard.dnaco.net>
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@pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
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