[Cryptography] converting one base to another

[Ray Dillinger]

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>