Dave Korn wrote:
> Of course, I could point out that there is precisely
*1* bit of information
> in that huge GIF, so even compressing it to 35 bytes
isn't a great
> achievement... it's one of the set of less-common
inputs that grow bigger as a
> compromise so that real pictures, which tend to have at
least *some*
> variation, grow smaller.
>
OK, according to Shannon's definition of entropy, how much
information
is there in \pi or e or other transcendent number? AFAIK
all finite
strings are in fractional expansion of \pi (take positive
integer base
other than 10 if you want). Sure, the numbers are
correlated, because we
can express \pi or e as infinite series, though only couple
of bytes is
necessary.
But: if you take any finite string, there exists a finite
natural number
as index where the string can be found in \pi. So are there
any "random
strings" at all? What if I can express the digits
starting at 2^(2^k)-th
index analytically in a short, fast algorithm? In case no
other can,
then I have perfect one-time pad, at least for some time,
because
conventional computers will not reach the place in some
reasonable time
(yes, I know, there may be other correlations). The point I
am trying to
make: if I take e.g. a transcendent number and can
analytically express
a part of its fractional expansion, I *might* have a strong
key.
The point for this: I am researching an authenticating
scheme where keys
are *programs*, not data. It means that key can change
itself over time,
for example. The strongest keys would therefore be somewhat
recursive
polymorphic code, that enumerates all possible permutations
on some
finite set in some deterministic, though seemingly random
order.
I know that there are "short" descriptions for
lots of infinite
structures, the mentioned transcendent numbers, then take
Mandelbrot
set, various IFSs (iterated function systems), quaternions,
unmeasurable
sets, there are lots of possibilities. What I know for sure
is that for
many mathematical structures short descriptions (programs or
(partially)
recursive functions) exist. What I conjecture is that for
each finite
ordered set a short "compression function"
exists. The whole trick is
that it is almost impossible (meaning computationally
infeasible) to
look for the compression functions using a finite
deterministic
algorithm. Though a human can do it.
It will yet take some time until I have some more results
about the
categories of key programs.
Cheers,
OM
------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomo metzdowd.com
|