Re: Speculative, but at least interesting

From: Todd Trimble (trimble1_at_optonline.net)
Date: 09/07/04 

Date: Tue, 7 Sep 2004 16:47:13 +0000 (UTC)

On 07 Sep 2004, Jesse F. Hughes wrote:
>Sam Wormley <swormley1@mchsi.com> writes:
>
>> Long Standing Math Puzzle May be Solves
>> http://www.guardian.co.uk/uk_news/story/0,3604,1298728,00.html
>>
>>
>>From the story.
>,----
>| Mathematicians could be on the verge of solving two separate million
>| dollar problems. If they are right - still a big if - and somebody
>| really has cracked the so-called Riemann hypothesis, financial
>| disaster might follow. Suddenly all cryptic codes could be
>| breakable. No internet transaction would be safe.
>|
>| [...]
>|
>| The Riemann hypothesis would explain the apparently random pattern
>| of prime numbers - numbers such as 3, 17 and 31, for instance, are
>| all prime numbers: they are divisible only by themselves and
>| one. Prime numbers are the atoms of arithmetic. They are also the
>| key to internet cryptography: in effect they keep banks safe and
>| credit cards secure.
>`----
>
>*Would* the Riemann hypothesis "explain" the pattern of primes?
>
>If so, would this really threaten cryptography?
>
>Sorry, I've always been fuzzy on this Riemann stuff. But the
>connection to primes is just about the value of pi(x) as x goes to
>infinity, right? Are there any actual results showing that a proof of
>the Riemann hypothesis would yield a fast means of factoring large
>primes[1]?
>

I am by no means an expert, but assuming the truth of the generalized
Riemann hypothesis, the Miller-Rabin test yields a fast deterministic
procedure for deciding primality. See

http://www.fact-index.com/m/mi/miller_rabin_primality_test.html

So it will tell you (within polynomial time, as a function of ln n)
whether or not n is composite, assuming GRH, but this isn't the
same as actually factorizing n if n is composite (presumably what
Gates meant to say).

The book "The Music of the Primes" by Marcus du Sautoy attempts to
convey to a lay audience how the "pattern of the primes" is related
to the zeta function and RH. While it's too impressionistic to be
completely satisfying for mathematicians, it's a good read none the
less.

Todd Trimble

>Footnotes:
>[1] If Bill Gates says that's the issue, then that's the issue.
>Don't argue.
>
>,----
>| ``The obvious mathematical breakthrough would be development of an
>| easy way to factor large prime numbers.'' -Bill Gates, The Road
>| Ahead, pg. 265
>`----
>
>--
>Jesse F. Hughes
>
>One is not superior merely because one sees the world as odious.
> -- Chateaubriand (1768-1848)

Relevant Pages
Quantcast