this is truly interesting...do you have a link to the original 1996 paper? do you know if anyone has incorporated this into a program? phillip
-----Original Message----- From: owner-cypherpunks@Algebra.COM [mailto:owner-cypherpunks@Algebra.COM]On Behalf Of Eric Cordian Sent: Thursday, August 02, 2001 2:35 PM To: cypherpunks@einstein.ssz.com Subject: Pi
Interesting article recently posted on the Nature Web site about the normality of Pi.
http://www.nature.com/nsu/010802/010802-9.html
"David Bailey of Lawrence Berkeley National Laboratory in California and Richard Crandall of Reed College in Portland, Oregon, present evidence that pi's decimal expansion contains every string of whole numbers. They also suggest that all strings of the same length appear in pi with the same frequency: 87,435 appears as often as 30,752, and 451 as often as 862, a property known as normality."
Of cryptographic interest.
"While there may be no cosmic message lurking in pi's digits, if they are random they could be used to encrypt other messages as follows:
"Convert a message into zeros and ones, choose a string of digits somewhere in the decimal expansion of pi, and encode the message by adding the digits of pi to the digits of the message string, one after another. Only a person who knows the chosen starting point in pi's expansion will be able to decode the message."
While there's presently no known formula which generates decimal digits of Pi starting from a particular point, there's a clever formula which can be used to generate HEX digits of Pi starting from anywhere, which Bailey et al discovered in 1996, using the PSLQ linear relation algorithm.
If you sum the following series for k=0 to k=infinity, its limit is Pi.
1/16^k[4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6)]
(Exercise: Prove this series sums to Pi)
Since this is an expression for Pi in inverse powers of 16, it is easy to multiply this series by 16^d and take the fractional part, evaluating terms where d>k by modular exponentiation, and evaluating a couple of terms where d<k to get a digit's worth of precision, yielding the (d+1)th hexadecimal digit of Pi.
Presumedly, if one could express PI as a series in inverse powers of 10, one could do the same trick to get decimal digits. Such a series has so far eluded researchers.
-- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"