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