[Cryptography] converting one base to another
Ray Dillinger
bear at sonic.net
Thu Dec 4 17:25:48 EST 2014
On 12/04/2014 12:56 PM, John Denker wrote:
> On 12/03/2014 01:23 PM, Ray Dillinger wrote:
>> Whenever the pseudoentropy register gets to be small enough to hold
>> another base-5 digit, you multiply it by 5 and add the output of the
>> generator (essentially you'd be 'replacing' the base-5 digit you most
>> recently took, had you been taking digits in base-5 rather than base-2).
>
> That's not a correct solution. As stated, it's both biased
> and many-to-one. The bug is where it says "...small enough..."
True. Hmm, I thought I had gotten there, but what I got
was actually more on the lines of *LESS* biased and *MORE*
bijective than other solutions I'm aware of.
I read your "float" solution and it's mathematically correct,
but conceptually, I think I like a slightly different formulation
of it better, with two different registers: One to hold power
information, and the other to hold bits. You'd initialize both
with the value '1'.
The power information is a double float, and you multiply by
5 every time you add a base-five digit then divide by 2 every
time you take out a bit.
The bits register would hold an integer value, and you'd
multiply by 5 and add the input every time you added a base-5
digit, then take the bottom bit and divide by 2 every time you
took out a bit.
You would add a base-5 digit every time the power register
showed less than 2^61, and take a bit out every time the power
register showed less than 2^61.
You're right that it can never be perfect; bijection and
bias avoidance both fail once every time accumulated rounding
errors cause the magic value of 2^61 to fall between the
theoretically correct and calculated value in the power
register.
Errors in bias (on the order of 1 in 2^61) would occur in
both directions as the process continued and be overall
quite negligible, but failures of bijection would accumulate,
and make most of the 'nice' properties I had in mind valid
only on streams of a few tens of thousands of digits or
less. Darn.
Bear
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141204/c98bc49b/attachment.sig>
More information about the cryptography
mailing list