Nth digit of PI
Kirby Urner
Here's another "math through programming" challenge:
Recent number theory breakthrough: you can get the
nth digit of PI without doing all the work needed
to compute all the digits up to the nth digit (same
with some other numbers -- not sure if we know all
the relevant criteria as to which).
The original algorithm worked for PI expressed as
a hexadecimal number, but I found a web page purporting
to give the algorithm for a base 10 PI, but I couldn't
figure out how to make it work in Python.[1][2]
Anyone?
Another question: does the algorithm for getting
the nth digit of PI actually do less work (in terms
of flipflops) than would an algorithm that gets
all digits up to n inclusive? I assume so, as I
read about someone getting a trillionth digit or
something -- but I don't think we've got PI to that
many places.
Kirby
[1] http://www.mathsoft.com/asolve/plouffe/plouffe.html
[2] http://www.lacim.uqam.ca/plouffe/Simon/articlepi.html
Rajarshi Ray
After all, what makes pi pi is ALL of its digits in a particular
sequence.
--
Sir, I have found you an argument. I am not obliged to find you
an understanding.
- Samuel Johnson
Peter Schneider-Kamp
>
> The original algorithm worked for PI expressed as
> a hexadecimal number, but I found a web page purporting
> to give the algorithm for a base 10 PI, but I couldn't
> figure out how to make it work in Python.[1][2]
Can you give the algorithm in some kind of pseudo code?
Pseudo python would be appreciated ...
If I understood it right the calculation has to be done
like this for every pair of primes in the denominator:
1) calculate k1 and k2 for 1/(a*b) = k1/a+k2/b
2) calculate m1, m2, m3 for (k1/a+k2/b)/c = m1/a+m2/b+m3/c
So that means one basically needs a continued fraction
algorithm and a factorization algorithm, right?
thinking-the-article-is-not-really-clear-about-it-ly
y'rs Peter
BTW: The algorithm for base 16 works ... very slowly:
def hexdcm(a,b,d,e):
x = long(a % b)
if d:
for k in range(d):
y = x << 4
x = y % b
else:
y = a
c = [y-x]
for j in range(e):
y = x << 4
x = y % b
c.append(y-x)
sum = 0
for j in range(e+1):
sum = sum + (1L << ((e-j) << 2)) * (c[j] / b)
return sum
def sum(d,e):
sum = 0L
for n in range(d+1):
sum = sum + hexdcm(120L*n**2L+151L*n+47L,\
(8L*n+1L)*(2L*n+1L)*(8L*n+5L)*(4L*n+3L),d-n,e)
return sum
def pi(d,e):
s = sum(d,e) % 16L**(e+1L)
return int((s - s % 16L**e) / 16L**e)
def upto(n):
for i in range(n+1):
if not i % 50:
if i:
print s+"\n ",
else:
print "3.",
s = ""
s = s + "%x" % pi(i+1,4)
print "\n"
--
Peter Schneider-Kamp ++47-7388-7331
Herman Krags veg 51-11 mailto:pe...@schneider-kamp.de
N-7050 Trondheim http://schneider-kamp.de
Harald Hanche-Olsen
| Besides the gee-whiz aspect of such algorithms, do they have any
| value?
They appear to have considerable entertainment value. And, for some
reason I could never fathom, every new supercomputer ever made is
supposed to crank out ever more digits of pi to prove their worth.
| After all, what makes pi pi is ALL of its digits in a particular
| sequence.
Nah. Digits don't have anything to do with it. What makes pi pi is
its definition, whatever your favourite definition might be. For
example, the smallest positive x so that sum((-1)^n x^(2n+1)/(2n+1)!)
[summed from n=0 to infinity] is zero. Digits be damned!
How-I-want-a-drink--alcoholic-of-course--after-the-heavy-chapters-
involving-quantum-mechanics-ly y'rs,
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- "There arises from a bad and unapt formation of words
a wonderful obstruction to the mind." - Francis Bacon
Kirby Urner
>Besides the gee-whiz aspect of such algorithms, do they have any value?
>After all, what makes pi pi is ALL of its digits in a particular
>sequence.
Supposedly there were some deep points about number
theory in this vicinity -- according to the web pages
anyway. I'm no expert.
Anyway, the "gee whiz" factor isn't to be underestimated,
either.
Kirby
Kirby Urner
>Can you give the algorithm in some kind of pseudo code?
>Pseudo python would be appreciated ...
Sorry Peter, you've already gotten way further than
I did on this. Thanks for sharing your code for
hex-PI. I look forward to running it.
Kirby
Jim Nastos
> Don't you just hate presumptuous bastards like Ullrich who will jump
> your gun without even considering if you actually have a point?? Perhaps
> you should be glad you're a non-expert; the more expert you get, it
> seems the more of a pompous ass you become too.
On the contrary, it seems to me that the more 'expert' one gets, the
more qualified they are in asking the right questions to probe 'pompous
asses.'
You seemed to have totally missed his point, so stop criticizing someone
for 'jumping a gun' without considering if *he* 'actually [had] a point.'
Jeeeeezz....
- Jim Nastos
Rajarshi Ray
>
> Rajarshi Ray <raja...@home.com> wrote:
>
> >Besides the gee-whiz aspect of such algorithms, do they have any value?
> >After all, what makes pi pi is ALL of its digits in a particular
> >sequence.
>
> Supposedly there were some deep points about number
> theory in this vicinity -- according to the web pages
> anyway. I'm no expert.
Ah, that's what I wanted to hear. The importance of this discovery is
then what makes pi amenable to such a calculation, and also if other
transcendental numbers can be treated like this e.g. 'e'.
Don't you just hate presumptuous bastards like Ullrich who will jump
your gun without even considering if you actually have a point?? Perhaps
you should be glad you're a non-expert; the more expert you get, it
seems the more of a pompous ass you become too.
> Anyway, the "gee whiz" factor isn't to be underestimated,
> either.
>
> Kirby
--
Mark Jackson
> Besides the gee-whiz aspect of such algorithms, do they have any value?
> After all, what makes pi pi is ALL of its digits in a particular
> sequence.
Well, if you're captured by an alien who asserts that s/he has
calculated pi to a gazillion decimal places, and your survival depends
on determining whether the claim is true or not, you can check a few
digits at random and either be certain it's false or 99.99. . .% sure
it's true. Never know when *that's* going to come in handy; in fact
IIRC this very plot was once used on McGyver.
--
Mark Jackson - http://www.alumni.caltech.edu/~mjackson
You can never solve all difficulties at once.
- Paul Dirac
david_...@my-deja.com
Rajarshi Ray <raja...@home.com> wrote:
> Kirby Urner wrote:
> >
> > Rajarshi Ray <raja...@home.com> wrote:
> >
value?
> > >After all, what makes pi pi is ALL of its digits in a particular
> > >sequence.
> >
> > theory in this vicinity -- according to the web pages
> > anyway. I'm no expert.
>
> Ah, that's what I wanted to hear. The importance of this discovery is
> then what makes pi amenable to such a calculation, and also if other
> transcendental numbers can be treated like this e.g. 'e'.
You wonder if I've ever heard of "Google", but you're unable
to click on the links he provided, even after I suggested you do so.
> Don't you just hate presumptuous bastards like Ullrich who will jump
> your gun without even considering if you actually have a point??
Jump what gun? I've done nothing but ask _questions_ about your
"point" - questions which you have simply refused to answer.
When most people have points they're willing to explain when
people ask about the details.
>Perhaps
> you should be glad you're a non-expert; the more expert you get, it
> seems the more of a pompous ass you become too.
>
> > Anyway, the "gee whiz" factor isn't to be underestimated,
> > either.
> >
> > Kirby
>
> --
> Sir, I have found you an argument. I am not obliged to find you
> an understanding.
>
> - Samuel Johnson
>
Sent via Deja.com http://www.deja.com/
Before you buy.
Mike Mccarty Sr
Harald Hanche-Olsen <han...@math.ntnu.no> wrote:
)+ Rajarshi Ray <raja...@home.com>:
)
)| Besides the gee-whiz aspect of such algorithms, do they have any
)| value?
)
)They appear to have considerable entertainment value. And, for some
)reason I could never fathom, every new supercomputer ever made is
)supposed to crank out ever more digits of pi to prove their worth.
[snip]
The computation of PI to a large number of digits is an excellent
*test* of the computer. Has nothing to do with computing PI per se.
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
Andrew Dalke
>Well, if you're captured by an alien who asserts that s/he has
>calculated pi to a gazillion decimal places, and your survival depends
>on determining whether the claim is true or not, you can check a few
>digits at random and either be certain it's false or 99.99. . .% sure
>it's true. Never know when *that's* going to come in handy; in fact
>IIRC this very plot was once used on McGyver.
I heard a related comment once. If you are taken by aliens and want
to be able to prove the event, ask them for a list of the first 100
Mersenne primes. This assumes they are willing and technologically
able, but if it happens, its pretty good proof.
Hmm, or you could be the inventor of a marvelous new primality
test method and want to play a grand hoax on the world - which is
more likely? :)
Andrew
Dik T. Winter
> Recent number theory breakthrough: you can get the
> nth digit of PI without doing all the work needed
> to compute all the digits up to the nth digit (same
> with some other numbers -- not sure if we know all
> the relevant criteria as to which).
I checked the pages and have to make a correction here. There is no such
claim. The only claim is that it can be done without using much memory.
As one of the referred pages says:
"we have not found a faster algorithm, nor have we proven that one does
not exist."
Se essentially the amount of work is still the same, but the memory
requirents are smaller.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Rajarshi Ray
>
> In article <bivnjsoq0amb8qjmq...@4ax.com> ur...@alumni.princeton.edu writes:
> > Recent number theory breakthrough: you can get the
> > nth digit of PI without doing all the work needed
> > to compute all the digits up to the nth digit (same
> > with some other numbers -- not sure if we know all
> > the relevant criteria as to which).
>
> I checked the pages and have to make a correction here. There is no such
> claim. The only claim is that it can be done without using much memory.
> As one of the referred pages says:
> "we have not found a faster algorithm, nor have we proven that one does
> not exist."
> Se essentially the amount of work is still the same, but the memory
> requirents are smaller.
Aw, poor Ullrich. You've shattered his dream of making a fast parallel
calculation of Pi! How dare you!!
> --
> dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
> home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
--
david_...@my-deja.com
"Dik T. Winter" <Dik.W...@cwi.nl> wrote:
> In article <bivnjsoq0amb8qjmq...@4ax.com>
ur...@alumni.princeton.edu writes:
> > Recent number theory breakthrough: you can get the
> > nth digit of PI without doing all the work needed
> > to compute all the digits up to the nth digit (same
> > with some other numbers -- not sure if we know all
> > the relevant criteria as to which).
>
> I checked the pages and have to make a correction here. There is no
such
> claim. The only claim is that it can be done without using much
memory.
> As one of the referred pages says:
> "we have not found a faster algorithm, nor have we proven that one
does
> not exist."
> Se essentially the amount of work is still the same, but the memory
> requirents are smaller.
??? In one of the references cited the authors say
"The computation can
be achieved without having to compute the preceeding digits. We claim
that the algorithm has a more theoretical rather
than practical interest, we have not found a faster algorithm, nor have
we proven that one does not exist."
The statement "The computation can be achieved without having to
compute the preceeding digits." could be a lie, I suppose, but
it's certainly at least a _claim_ that they can calculate the
n-th digit without finding the preceding ones.
Regarding the "have not found a faster algorithm": Are
you certain they're saying that none of this is any faster
than finding the first n digits, or do they mean that they
have not found a faster "digit-extraction" algorithm than
the original Bailey-Borwein-Plouffe algorithm?
The other reference begins
"David Bailey, Peter Borwein and Simon Plouffe have recently computed
the ten billionth digit in the hexadecimal
expansion of pi. They utilized an astonishing formula:
[astonishing formula goes here]
which enables one to calculate the dth digit of pi without being forced
to calculate all the preceding d-1 digits."
If these algorithms _really_ take as much time as finding
all the digits, as you seem to be saying, it's hard to see why
they'd have everybody so excited (or rather why they _did_ have
everybody so excited back when this was news). It's also hard to
see why people would suggest that one point to the digit-extraction
algorithms would be to be able to check the accuracy of calculations
of _all_ the digits.
> --
> dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland,
+31205924131
> home: bovenover 215, 1025 jn amsterdam, nederland;
http://www.cwi.nl/~dik/
>
Robert Israel
> ??? In one of the references cited the authors say
>"The computation can
>be achieved without having to compute the preceeding digits. We claim
>that the algorithm has a more theoretical rather
>than practical interest, we have not found a faster algorithm, nor have
>we proven that one does not exist."
> Regarding the "have not found a faster algorithm": Are
>you certain they're saying that none of this is any faster
>than finding the first n digits, or do they mean that they
>have not found a faster "digit-extraction" algorithm than
>the original Bailey-Borwein-Plouffe algorithm?
> The other reference begins
>"David Bailey, Peter Borwein and Simon Plouffe have recently computed
>the ten billionth digit in the hexadecimal
> expansion of pi. They utilized an astonishing formula:
>[astonishing formula goes here]
> which enables one to calculate the dth digit of pi without being forced
>to calculate all the preceding d-1 digits."
> If these algorithms _really_ take as much time as finding
>all the digits, as you seem to be saying, it's hard to see why
>they'd have everybody so excited (or rather why they _did_ have
>everybody so excited back when this was news). It's also hard to
>see why people would suggest that one point to the digit-extraction
>algorithms would be to be able to check the accuracy of calculations
>of _all_ the digits.
There are two different algorithms here, for two different problems.
The BBP algorithm can find a hexadecimal (or more generally, base
2^k) digit of pi, faster than any known algorithm that would find
all the digits up to this one. This is the exciting one.
Plouffe has another algorithm that can find a digit in an arbitrary
base. This takes C*n^3*log(n)^3 time for the n'th digit, so it is not
faster than other methods that would compute the first n digits, but it
does take very little memory. This one has "a more theoretical rather
than practical interest".
Whether there is an algorithm for the n'th decimal digit that performs
as well as BBP is still an open question.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Clive Tooth
>[...]
>There are two different algorithms here, for two different problems.
>
>The BBP algorithm can find a hexadecimal (or more generally, base
>2^k) digit of pi, faster than any known algorithm that would find
>all the digits up to this one. This is the exciting one.
Although BBP do mention that "This algorithm is, by a factor of
log(log(log(n))), asymptotically slower than the fastest known algorithms
for generating the n-th digit by generating all of the first n digits of
log(2) or pi."
>Plouffe has another algorithm that can find a digit in an arbitrary
>base. This takes C*n^3*log(n)^3 time for the n'th digit, so it is not
>faster than other methods that would compute the first n digits, but it
>does take very little memory. This one has "a more theoretical rather
>than practical interest".
>
>Whether there is an algorithm for the n'th decimal digit that performs
>as well as BBP is still an open question.
An O(n^2) algorithm is described at
http://www.stud.enst.fr/~bellard/pi/pi_n2/pi_n2.html
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
Russell Wallace
> Plouffe has another algorithm that can find a digit in an arbitrary
> base. This takes C*n^3*log(n)^3 time for the n'th digit, so it is not
> faster than other methods that would compute the first n digits, but it
> does take very little memory.
Correct me if I'm wrong, but I thought memory was the limiting factor?
i.e. that a good algorithm on typical hardware can fill all the
available memory with digits of pi in a few days or so?
> This one has "a more theoretical rather
> than practical interest".
Well, anything beyond the first 10-20 digits of pi is of purely
theoretical interest :)
--
"To summarize the summary of the summary: people are a problem."
Russell Wallace
mailto:rwal...@esatclear.ie
http://www.esatclear.ie/~rwallace
Clive Tooth
>Robert Israel wrote:
>> Plouffe has another algorithm that can find a digit in an arbitrary
>> base. This takes C*n^3*log(n)^3 time for the n'th digit, so it is not
>> faster than other methods that would compute the first n digits, but it
>> does take very little memory.
>
>Correct me if I'm wrong, but I thought memory was the limiting factor?
>i.e. that a good algorithm on typical hardware can fill all the
>available memory with digits of pi in a few days or so?
You are wrong. The discussion was about methods of calculating digit N of pi
(in some base) without computing digits 1 thru N-1 . This can be done in
about O(log(N)) bits of memory.
Tim Dixon
wrote:
>Besides the gee-whiz aspect of such algorithms, do they have any value?
>After all, what makes pi pi is ALL of its digits in a particular
>sequence.
I can think of a great use for such an algorithm, if one existed (I
think this is a misunderstanding and a closer examination will reveal
that all they've found is that such an algorithm isn't theoretically
impossible or something like that).
The strongest possible encryption is a secret key one time pad. A one
time pad is an encryption method by which each byte (or couple bytes)
is encrypted using a different key which is discarded and not used
again. It's not possible to break this kind of encryption without
compromising the "key pad" itself because discovering one byte tells
you nothing about any of the other bytes. Being unable to test a
sequence of bytes makes it impossible to tell whether you've cracked
the byte or not, and even if you did that, you'd still not have the
rest of the message. An advantage is the the algorithm can be very
simple (a simple XOR against the key would suffice) because the
security is in the key, not the algorithm.
There are two problems: one is that it's a secret key system and not
a public key system, so it's not useful for many applications. It
doesn't work for something like SSL or PGP, for instance. This is a
characteristic of secret key systems.
The second is the enormous effort involved in producing one time pads.
You need enough bits in your pad to encrypt the entire message;
essentially for a 16K message, your key would have to be 16K long as
well. Naturally, you need to get the key to the recipient via some
secure means and communicate what portion of the pad is used by a
particular message.
Suppose, however, that you could get digit 'n' of pi directly (or e,
or any other inifinte, nonrepeating sequence). All I have to do is
communicate which digit of pi the message key starts at, and I can
generate the rest of the key. I still have the unbreakable nature of
the one time pad, but now I only have to keep secret the starting
point; I can generate the key on the fly. Keeping *that* secure is
still nontrivial, of course. :-)
>
>Kirby Urner wrote:
>>
>> Here's another "math through programming" challenge:
>>
Courageous
> Suppose, however, that you could get digit 'n' of pi directly (or e,
> or any other inifinte, nonrepeating sequence). All I have to do is
> communicate which digit of pi the message key starts at, and I can
> generate the rest of the key.
This is a collosally bad idea, IMO.
C/
Tim Dixon
Robert Israel
>Just for curiosity, why?
Because the real key is the number of the digit that you start at, and
that's pitifully small by cryptographic standards. The time to generate
the n'th digit is not much less than the time to generate all the digits
up to the n'th, given that you have lots of memory available. So the
cryptanalyst with a computer somewhat bigger than yours could try all
the keys you could be using.
Tim Dixon
>In article <394a5ed7...@10.1.1.28>,
>Tim Dixon <tdix...@spam.fwi.com> wrote:
>>On Fri, 16 Jun 2000 16:33:59 GMT, Courageous <jkra...@san.rr.com>
>>wrote:
>
>
>>>> Suppose, however, that you could get digit 'n' of pi directly (or e,
>>>> or any other inifinte, nonrepeating sequence). All I have to do is
>>>> communicate which digit of pi the message key starts at, and I can
>>>> generate the rest of the key.
>>>
>>>This is a collosally bad idea, IMO.
>
>>Just for curiosity, why?
>
>Because the real key is the number of the digit that you start at, and
>that's pitifully small by cryptographic standards. The time to generate
>the n'th digit is not much less than the time to generate all the digits
>up to the n'th, given that you have lots of memory available. So the
>cryptanalyst with a computer somewhat bigger than yours could try all
>the keys you could be using.
>
Right, but in the hypothetical example where I can get *any* digit of
pi, that could be any of an infinite number of starting points.
hack
Courageous <jkra...@san.rr.com> wrote:
>
>> Suppose, however, that you could get digit 'n' of pi directly (or e,
>> or any other inifinte, nonrepeating sequence). All I have to do is
>> communicate which digit of pi the message key starts at, and I can
>> generate the rest of the key.
>
>This is a collosally bad idea, IMO.
>
It works fine if the number of bits in 'n' is large enough, e.g. 16K bits.
Your key would then be the 16K bits of pi starting around bit 10^5000 (to
encode a message of 16K bits). Of course, you haven't gained much: you
might as well use 'n' itself!
Michel.
Steven D. Majewski
On Fri, 16 Jun 2000, Tim Dixon wrote:
> The strongest possible encryption is a secret key one time pad. A one
> time pad is an encryption method by which each byte (or couple bytes)
> is encrypted using a different key which is discarded and not used
> again.
>
> There are two problems: one is that it's a secret key system and not
> a public key system, so it's not useful for many applications. It
> doesn't work for something like SSL or PGP, for instance. This is a
> characteristic of secret key systems.
>
> The second is the enormous effort involved in producing one time pads.
> You need enough bits in your pad to encrypt the entire message;
> essentially for a 16K message, your key would have to be 16K long as
> well. Naturally, you need to get the key to the recipient via some
> secure means and communicate what portion of the pad is used by a
> particular message.
Nowadays, Music CDs and DVDs are an easily available source of a stream
of bits. All you have to do is secretly agree upon a disk, and maybe
a starting track or location in the stream. ( There's also an infinite
set of algorithms to agree to run that stream thru. For example:
break the stream into 3-bit chunks, take a group of 7 chunks and drop
all but the first and last, concatenate them all and rechunk them into
8-bit bytes, and XOR them with the data stream. That's not too complicated
for someone to memorize. )
Only problems is that encryption based on a physical artifact is
vulnerable to physical snooping: someone dressed in black breaks into
your house in the middle of the night and catalogs your CD collection
( or if you're not too smart, finds the one left sitting next to the
computer! ) Books used to be used as one time pads, and they had the
same vulnerability -- sometimes it was possible, by close inspection,
to tell where the book had been frequently left open. ( The Bible
was a popular choice, as there were reasons to make carrying one
around constantly not be considered suspicious behaviour. )
--- Steve Majewski
Chop wood, carry water.
Aahz Maruch
Steven D. Majewski <sd...@virginia.edu> wrote:
>
>Only problems is that encryption based on a physical artifact is
>vulnerable to physical snooping: someone dressed in black breaks into
>your house in the middle of the night and catalogs your CD collection
>( or if you're not too smart, finds the one left sitting next to the
>computer! ) Books used to be used as one time pads, and they had the
>same vulnerability -- sometimes it was possible, by close inspection,
>to tell where the book had been frequently left open. ( The Bible
>was a popular choice, as there were reasons to make carrying one
>around constantly not be considered suspicious behaviour. )
Close, but no cigar. What you're describing that's vulnerable is the
use of a book as an encryption key rather than a one-time pad. If it
were literally a one-time pad, there'd be no particular physical marks.
Of course, I don't think the concept of a one-time pad existed as such
back then.
--
--- Aahz (Copyright 2000 by aa...@netcom.com)
Androgynous poly kinky vanilla queer het <*> http://www.rahul.net/aahz/
Hugs and backrubs -- I break Rule 6
"The only problem with Microsoft is they just have no taste." --Steve Jobs
(From _Triumph of the Nerds_ PBS special)
Mike Mccarty Sr
)wrote:
)
)>
)>> Suppose, however, that you could get digit 'n' of pi directly (or e,
)>> or any other inifinte, nonrepeating sequence). All I have to do is
)>> communicate which digit of pi the message key starts at, and I can
)>> generate the rest of the key.
)>
)>This is a collosally bad idea, IMO.
)>
)>
)
)Just for curiosity, why?
For one thing, it doesn't implement a one-time-pad. If I guess that you
are using PI as your key, then I can decrypt all your messages.
Mike
Steven D. Majewski
On 16 Jun 2000, Aahz Maruch wrote:
> Close, but no cigar. What you're describing that's vulnerable is the
> use of a book as an encryption key rather than a one-time pad. If it
> were literally a one-time pad, there'd be no particular physical marks.
> Of course, I don't think the concept of a one-time pad existed as such
> back then.
Well -- the concept of one time pads goes back to the 1920's or earlier,
and the ones the German's used were written down on paper -- the "one
time" implied that they were destroyed after they were used.
It's a modern day computer notion that even better than a real physical
pad of paper that can be intercepted or stolen, is a shared algorithm that
generates a random one time pad.
But your "Close, but no cigar" comment is justified on other grounds:
the one time pad is supposed to be random, and using a non random pad
makes it theoretically vulnerable. I just wonder how practically
vulnerable it is, given a extremely large choice of non-random bit-streams
to choose from.
I believe the idea of using a book text as an easily shared but very
large key is a pretty ancient idea --certainly predating the one-time pad.
Does anyone have a reference ? I can't remember where I first saw it
mentioned.
-- Steve Majewski
Cut wood, carry water.
Russell Wallace
> >i.e. that a good algorithm on typical hardware can fill all the
> >available memory with digits of pi in a few days or so?
>
> You are wrong. The discussion was about methods of calculating digit N of pi
> (in some base) without computing digits 1 thru N-1 . This can be done in
> about O(log(N)) bits of memory.
Yes, that's what I mean. The O(log N) memory consumption would, it
seems to me, make it possible to reach far higher values of N than if
you had to calculate digits 1 thru N-1, even if the amount of
computation required isn't much different.
Clive Tooth
> Clive Tooth wrote:
> >
> > Russell Wallace wrote in message <394889...@esatclear.ie>...
> > >Correct me if I'm wrong, but I thought memory was the limiting factor?
> > >i.e. that a good algorithm on typical hardware can fill all the
> > >available memory with digits of pi in a few days or so?
> >
> > You are wrong. The discussion was about methods of calculating digit N of pi
> > (in some base) without computing digits 1 thru N-1 . This can be done in
> > about O(log(N)) bits of memory.
>
> Yes, that's what I mean. The O(log N) memory consumption would, it
> seems to me, make it possible to reach far higher values of N than if
> you had to calculate digits 1 thru N-1, even if the amount of
> computation required isn't much different.
A calculation of the Nth digit of pi, where the limit was the amount of
_memory_ available, say 100MB on some typical PC, would mean an
extremely large N and a truly stupendous amount of time. Greater than
the age of the universe, etc.
Steven D. Arnold
>In article <394a5ed7...@10.1.1.28>,
>Tim Dixon <tdix...@spam.fwi.com> wrote:
> >>
> >>This is a collosally bad idea, IMO.
>
>
>Because the real key is the number of the digit that you start at, and
>that's pitifully small by cryptographic standards. The time to generate
>the n'th digit is not much less than the time to generate all the digits
>up to the n'th, given that you have lots of memory available. So the
>cryptanalyst with a computer somewhat bigger than yours could try all
>the keys you could be using.
Perhaps we could specify a key; the key would be a sequence which we would
find in pi. The next bit in pi would be the start of our one-time
pad. For example, the key might be the first ten words in today's London
Times.
This would likely give us a very large n and yet it is still an easy
requirement to transmit.
Course, this idea too might have holes the size of a Mack truck -- I liked
the previous idea too until you shot it down. ;-)
--
Steven D. Arnold Que quiero sera ste...@neosynapse.net
"If you have built castles in the air, your work need not be lost; that
is where they should be. Now put the foundations under them!" -- Thoreau
James Graves
>On 16 Jun 2000 17:36:32 GMT, isr...@math.ubc.ca (Robert Israel) wrote:
>
>>Tim Dixon <tdix...@spam.fwi.com> wrote:
>>
>>
>>>>> Suppose, however, that you could get digit 'n' of pi directly (or e,
>>>>
>>
>>>Just for curiosity, why?
>>
>>Because the real key is the number of the digit that you start at, and
>>that's pitifully small by cryptographic standards. The time to generate
>>the n'th digit is not much less than the time to generate all the digits
>>up to the n'th, given that you have lots of memory available. So the
>>cryptanalyst with a computer somewhat bigger than yours could try all
>>the keys you could be using.
>>
>
>pi, that could be any of an infinite number of starting points.
Using transcendentals for encryption is an interesting idea, one that's
been banging around in my head for a while.
I am under the impression that there are an infinite number of
transcendental numbers. If there was some way to arbitrarily pick one
and the starting point, that might be harder to crack. Then again, if
the black hats have your encryption algorithm (which is good to assume)
it wouldn't be any more secure than spending all the key bits on the
starting position inside of Pi.
This scheme still has the weaknesses of conventional stream
cyphers, in that it can be brute-forced. A cypher can give you N years
of protection for your data (based on estimations of future computing
power). But a one-time-pad is _forever_ if the pad was generated
correctly and used only once.
James Graves
--
____________________________________________________________________________
Free Speech Under Attack in the UK: http://www.liberty.org.uk/cacib/
Jeff Massung
far as I go. In theory, pi (and e) are infinite, but has that been proven
that there is not end to their decimals?
Jeff
Robert Szefler
oh, come on, pi and e are irrational, so their decimal representations are
infinite and non-periodic. It's quite easy to prove e's irrationality. And
it's a bit harder for pi.
Moreover, they're transcendental numbers (do I spell it right?) ie. not a
root of any integer-coefficient-polynomial. This is substantially harder
to prove than the above ones.
steve
Jan Kristian Haugland
On Wed, 21 Jun 2000, Jeff Massung wrote:
> Please, this interests me -- I've had differention equations, but that's as
> far as I go. In theory, pi (and e) are infinite, but has that been proven
> that there is not end to their decimals?
>
> Jeff
Someone else already answered your question, but what
do you mean by "in theory, pi and e are infinite"?
Boris Borcic
Come on, it can obviously be defended as a shorthand for :
"In theory, an exact decimal representation of pi and e
would be of infinite length".
Together with :
"I am not familiar with other meanings of 'infinite'
applied to numerical values"
A legitimate state of affair, wouldn't you say ?
BB
Jan Kristian Haugland
Yes, it's natural to expect that the statement "pi is
infinite" means "a decimal representation of pi would
be of infinite length", but the problem is that that
already answers the question he was posing. Perhaps
"in theory" here means something strange.
François Pinard
> I am under the impression that there are an infinite number of
> transcendental numbers.
There is an aleph1 number of real numbers and an aleph0 number of non
transcendental numbers (since we can enumerate all algebraic equations).
Aleph1 > aleph0, an aleph1 number of transcendental numbers remain. Right?
--
François Pinard http://www.iro.umontreal.ca/~pinard
Suchandra Thapa
>Tim Dixon <tdix...@spam.fwi.com> wrote:
>>On 16 Jun 2000 17:36:32 GMT, isr...@math.ubc.ca (Robert Israel) wrote:
>>
>>>Tim Dixon <tdix...@spam.fwi.com> wrote:
>>>>On Fri, 16 Jun 2000 16:33:59 GMT, Courageous <jkra...@san.rr.com>
>>>>wrote:
>>>
>>>
>>>>>> Suppose, however, that you could get digit 'n' of pi directly (or e,
>>>>>> or any other inifinte, nonrepeating sequence). All I have to do is
>>>>>> communicate which digit of pi the message key starts at, and I can
>>>>>> generate the rest of the key.
>>>>>
>>>>>This is a collosally bad idea, IMO.
>>>
>>>>Just for curiosity, why?
>>>
>>>Because the real key is the number of the digit that you start at, and
>>>that's pitifully small by cryptographic standards. The time to generate
>>>the n'th digit is not much less than the time to generate all the digits
>>>up to the n'th, given that you have lots of memory available. So the
>>>cryptanalyst with a computer somewhat bigger than yours could try all
>>>the keys you could be using.
>>>
>>
>>Right, but in the hypothetical example where I can get *any* digit of
>>pi, that could be any of an infinite number of starting points.
>
>Using transcendentals for encryption is an interesting idea, one that's
>been banging around in my head for a while.
>
>and the starting point, that might be harder to crack. Then again, if
>the black hats have your encryption algorithm (which is good to assume)
>it wouldn't be any more secure than spending all the key bits on the
>starting position inside of Pi.
A possible problem with using transcedentals as keys is the distribution
of numbers in the representation of the transcendental. It's possible
to have irrational non repeating numbers that would be horrible as a key.
For example, 0.01001000100001... is irrational and non repeating however
using it for encryption would not be very wise. More subtly, it could
be possible that 27 occurs more often in pi or e than chance would dictate.
Things like this would decrease your keyspace and it would be very
difficult to verify that the transcendental you're using does not have
this problem.
--
------------------------------------------------------------------
Suchandra S. Thapa
s-t...@uchicago.edu
------------------------------------------------------------------
Harald Hanche-Olsen
| There is an aleph1 number of real numbers
That is a statement of the continuum hypothesis, which is known to be
independent of ZFC (the Zermelo-Fraenkel set theory including the
axiom of choice, on which we tend to imagine all of modern mathematics
is based).
| and an aleph0 number of non transcendental numbers (since we can
| enumerate all algebraic equations). Aleph1 > aleph0, an aleph1
| number of transcendental numbers remain. Right?
For aleph1 substitute c, and all this is true (where c is the
cardinality of the continuum: c > aleph0 as Cantor showed with his
diagonal argument).
belatedly-'cause-I've-been-vacationing-in-Arizona-ly y'rs,
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- "There arises from a bad and unapt formation of words
a wonderful obstruction to the mind." - Francis Bacon
Moshe Zadka
> + François Pinard <pin...@iro.umontreal.ca>:
>
> | There is an aleph1 number of real numbers
>
> That is a statement of the continuum hypothesis, which is known to be
> independent of ZFC (the Zermelo-Fraenkel set theory including the
> axiom of choice, on which we tend to imagine all of modern mathematics
> is based).
Ummmm....a lot of modern mathematics based on ZFC + existence of "large"
cardinals. These can be trivially shown to be strictly stronger then ZFC
via Goedel's theorem, and the fact that under a large cardinal, life seems
to be like ZFC.
matrijn-is-this-progessing-in-the-direction-you-forsee-ly y'rs, Z.
--
Moshe Zadka <mos...@math.huji.ac.il>
There is no GOD but Python, and HTTP is its prophet.
Randall Hopper
|Please, this interests me -- I've had differention equations, but that's as
|far as I go. In theory, pi (and e) are infinite, but has that been proven
|that there is not end to their decimals?
I don't know the mathematically-rigorous answer to your question. But one
of the interesting things that you can show with a Fourier integral
(possibly other ways too) is that:
Pi^2/8 = sum(n=1..inf, 1/(2n-1)^2)
You can see that the sum is 1/1 + 1/9 + 1/125 + .... The terms get smaller
and smaller, which means making the decimal representation longer and
longer. In the limit, the decimal representation is infinitely long
because the denominator is infinitely large.
Solving for pi: multiplying by 8, you still have infinitely many digits,
and taking the square root, you still have infinitely many digits. That's pi.
Randall
------------------------------------------------------------------------------
#!/usr/bin/env python
#
# pi = sqrt( 8 * sum(n=1..inf, 1/(2n-1)^2) )
# Not a realistic way to compute pi; convergence is hideously slow.
# But with rational number arithmetic and lots of storage...
#
import math
ITERATIONS = 50000
sum = 0
for v in range(2*ITERATIONS-1,0,-2):
sum = sum + 1/v**2.0
print "pi is approx %g (%d iterations)" % ( math.sqrt( sum * 8 ), ITERATIONS )
Roy Smith
> Pi^2/8 = sum(n=1..inf, 1/(2n-1)^2)
Interesting, I've never seen that one before.
It's not a very efficient way to compute pi (I know, that's not what you were
trying to do). A little experimentation shows that 1000 terms only gets you 4
significant digits correct, and 10,000 terms still only had 5!
--
Roy Smith <r...@popmail.med.nyu.edu>
New York University School of Medicine
Andrew Dalke
>But one of the interesting things that you can show with a Fourier
>integral (possibly other ways too) is that:
>
> Pi^2/8 = sum(n=1..inf, 1/(2n-1)^2)
>
>You can see that the sum is 1/1 + 1/9 + 1/125 + .... The terms get smaller
>and smaller, which means making the decimal representation longer and
>longer. In the limit, the decimal representation is infinitely long
>because the denominator is infinitely large.
I've seen the proof that e is irrational, but don't recall the details.
The sketch you outlined isn't sufficient. Consider
sum(n=1..inf, 1/n^2) = 1 + 1/2 + 1/4 + 1/8 + ... = 2
For any finite N in the sum 1..N, the denominator is infinitely large,
but the infinite sum is an integer.
Andrew
da...@acm.org
Randall Hopper
|I've seen the proof that e is irrational, but don't recall the details.
|The sketch you outlined isn't sufficient. Consider
|
| sum(n=1..inf, 1/n^2) = 1 + 1/2 + 1/4 + 1/8 + ... = 2
|
|For any finite N in the sum 1..N, the denominator is infinitely large,
|but the infinite sum is an integer.
Good point. Thanks for the correction.
--
Randall Hopper
aa...@yahoo.com
