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"
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"
Phillip H. Zakas wrote:
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?
David Bailey has a brief explanation of the Pi digit algorithm on his Web page at NERSC... http://hpcf.nersc.gov/~dhbailey/pi-alg Also check out "Recognizing Numerical Constants" by David H. Bailey and Simon Plouffe at... http://www.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html and click on the link titled "Formulas for Pi and Related Constants." More interesting stuff at... http://www.multimania.com/bgourevitch/ref/ottawaPi.pdf Where plouffe discusses some more of the math and reveals the 400 billionth binary digit of Pi. Lots more if you use a search engine. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
At 11:34 AM 8/2/2001 -0700, Eric Cordian wrote:
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.
I tried to something like this in the late '80s to allow efficient loss-less compression using "conditioned" PRNs which could generate suitable auto correlated streams. Unfortunately, I did not discover a similar method of locating the desired sequences. The search during the compression phase was to computationally difficult and I abandoned the effort. steve
On Thu, 2 Aug 2001, Eric Cordian wrote:
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."
Note that Reed College is known to be one of the best sources of hallucinigens locally. I wonder where "10000" or "99999" occurs in Pi? alan@ctrl-alt-del.com | Note to AOL users: for a quick shortcut to reply Alan Olsen | to my mail, just hit the ctrl, alt and del keys. "All power is derived from the barrel of a gnu." - Mao Tse Stallman
participants (4)
-
Alan Olsen -
Eric Cordian -
Phillip H. Zakas -
Steve Schear