So the obvious question is, does this speed up the cracking capabilities of
computers? On the surface, I'd say no, but then again I'm no computational
science expert. (I say no because any of the primes used in X-bitlength
encryption are already known, and these strings of primes aren't going to be
used any more frequently than any random batch of primes.)
-TD
From: Major Variola (ret) [EMAIL PROTECTED]
To: [EMAIL PROTECTED] [EMAIL PROTECTED]
Subject: Re: primes as far as the eye can see, discrete continua
Date: Wed, 08 Dec 2004 21:37:52 -0800
copied under fair use only because Roy put in the research...
NUMBER THEORY:
Proof Promises Progress in Prime Progressions
Barry Cipra
The theorem that Ben Green and Terence Tao set out to prove would have
been impressive enough. Instead, the two
mathematicians wound up with a stunning breakthrough in the theory of
prime numbers. At least that's the preliminary assessment
of experts who are looking at their complicated 50-page proof.
Green, who is currently at the Pacific Institute for the Mathematical
Sciences in Vancouver, British Columbia, and Tao of the
University of California (UC), Los Angeles, began working 2 years ago
on the problem of arithmetic progressions of primes:
sequences of primes (numbers divisible only by themselves and 1) that
differ by a constant amount. One such sequence is 13,
43, 73, and 103, which differ by 30.
In 1939, Dutch mathematician Johannes van der Corput proved that there
are an infinite number of arithmetic progressions of
primes with three terms, such as 3, 5, 7 or 31, 37, 43. Green and Tao
hoped to prove the same result for four-term
progressions. The theorem they got, though, proved the result for prime
progressions of all lengths.
It's a very, very spectacular achievement, says Green's former
adviser, Timothy Gowers of the University of Cambridge, who
received the 1998 Fields Medal, the mathematics equivalent of the Nobel
Prize, for work on related problems. Ronald Graham, a combinatorialist
at UC San Diego,
agrees. It's just amazing, he says. It's such a big jump from what
came before.
Green and Tao started with a 1975 theorem by Endre Szemeridi of the
Hungarian Academy of Sciences. Szemeridi proved that arithmetic
progressions of all
lengths crop up in any positive fraction of the integers--basically,
any subset of integers whose ratio to the whole set doesn't dwindle away
to zero as the numbers get
larger and larger. The primes don't qualify, because they thin out too
rapidly with increasing size. So Green and Tao set out to show that
Szemeridi's theorem still
holds when the integers are replaced with a smaller set of numbers with
special properties, and then to prove that the primes constitute a
positive fraction of that set.
Prime suspect. Arithmetic
progressions such as this 10-prime sequence are infinitely abundant, if
a new proof
holds up.
To build their set, they applied a branch of mathematics known as
ergodic theory (loosely speaking, a theory of mixing or averaging) to
mathematical objects called
pseudorandom numbers. Pseudorandom numbers are not truly random,
because they are generated by rules, but they behave as random numbers
do for certain
mathematical purposes. Using these tools, Green and Tao constructed a
pseudorandom set of primes and almost primes, numbers with relatively
few prime
factors compared to their size.
The last step, establishing the primes as a positive fraction of their
pseudorandom set, proved elusive. Then Andrew Granville, a number
theorist at the University of
Montreal, pointed Green to some results by Dan Goldston of San Jose
State University in California and Cem Yildirim of Bo_gazigi University
in Istanbul, Turkey.
Goldston and Yildirim had developed techniques for studying the size of
gaps between primes, work that culminated last year in a dramatic
breakthrough in the
subject--or so they thought. Closer inspection, by Granville among
others, undercut their main result (Science, 4 April 2003, p. 32; 16 May
2003, p. 1066),
although Goldston and Yildirim have since salvaged a less far-ranging
finding. But some of the mathematical machinery that these two had set
up proved to be
tailor-made for Green and Tao's research. They had actually proven
exactly what we needed, Tao says.
The paper, which has been submitted to the Annals of Mathematics, is
many months from acceptance. The problem with a quick assessment of it
is that it
straddles two areas, Granville says. All of the number theorists
who've looked at it feel that the number-theory half is pretty simple
and the ergodic theory is
daunting, and the ergodic theorists who've looked at it have thought
that the ergodic theory is pretty simple and the number theory is
daunting.
Even if a mistake does show up, Granville says, they've certainly
succeeded in bringing in new ideas of real import into the subject. And
if the proof
