Prev: Why does JH Conway say -1 is prime?
Next: Sum of permutations
From: Dan Cass on 25 Jan 2010 00:43
> How can I map an integer N between 1 and 1,000,000 to
> a string f(N) of
> 12 letters where I can map back from f(N) to N, and
> f(N+1) bears no
> resemblance to f(N)? (Better yet f(N+m) bears no
> resemblance to f(N)
> for m=1 to 1000 or f(m) for any m not equal to N.)
>
> C-B

Since 26^12 = 95428956661682176,
you can do much better than 1,000,000.
From: David R Tribble on 25 Jan 2010 20:16
Charlie-Boo wrote:
> How can I map an integer N between 1 and 1,000,000 to a string f(N) of
> 12 letters where I can map back from f(N) to N, and f(N+1) bears no
> resemblance to f(N)? (Better yet f(N+m) bears no resemblance to f(N)
> for m=1 to 1000 or f(m) for any m not equal to N.)

It looks like you are asking for a hashing function that hashes
values in [1, 1 000 000] into a subset of 26^12 possible values
(assuming you meant 12 members from an alphabet of 26 letters).

Someone else pointed out that 26^12 = 95,428,956,661,682,176.
So you need a function that hashes 20-bit values into a 57-bit
values. Finding a suitable hashing function with few collisions
should be fairly easy.
From: Mok-Kong Shen on 26 Jan 2010 13:27
Charlie-Boo wrote:
> How can I map an integer N between 1 and 1,000,000 to a string f(N) of
> 12 letters where I can map back from f(N) to N, and f(N+1) bears no
> resemblance to f(N)? (Better yet f(N+m) bears no resemblance to f(N)
> for m=1 to 1000 or f(m) for any m not equal to N.)

Your N is less than 2^20. You would need a mapping g(N) that bijectively
maps N to [0, 2^20-1]. After you get g(N) you can transcribe that
integer to letters according to some scheme without difficulty, I
suppose. Such a g(n) can be a polynomial mod 2^20 and is termed
a permutation polynomial. Conditions for

g(x)= c_0 + c_1*x + c_2*x^2 + c_3*x^3 + ........ mod 2^n

to be a permutation polynomial that has the further property that
x(i+1) = g(x_i) mod 2^n gives a sequence of full period 2^n is:

c_3 + c_5 + c_7 + .... = 2*c_2 mod 4

c_4 + c_6 + c_8 + .... = c_1 + c_2 - 1 mod 4

c_1 = 1 mod 2

c_0 = 1 mod 2

See V. Anashin, A. Khrennikov, Applied Algebraic Dynamics, Berlin,
2009, p.283.

M. K. Shen



From: Michael Stemper on 26 Jan 2010 17:45
In article <e28bb4a6-529a-47c5-9ddc-6c11dc4056ed(a)b9g2000yqd.googlegroups.com>, Charlie-Boo <shymathguy(a)gmail.com> writes:
>How can I map an integer N between 1 and 1,000,000 to a string f(N) of
>12 letters where I can map back from f(N) to N, and f(N+1) bears no
>resemblance to f(N)?

Depending upon what kinds of resemblance are or are not acceptable,
you might consider using Gray codes modified for base 26 instead of
for base 2.

--
Michael F. Stemper
#include <Standard_Disclaimer>
COFFEE.SYS not found. Abort, Retry, Fail?
From: Ilmari Karonen on 26 Jan 2010 22:15
On 2010-01-26, David R Tribble <david(a)tribble.com> wrote:
> Charlie-Boo wrote:
>> How can I map an integer N between 1 and 1,000,000 to a string f(N) of
>> 12 letters where I can map back from f(N) to N, and f(N+1) bears no
>> resemblance to f(N)? (Better yet f(N+m) bears no resemblance to f(N)
>> for m=1 to 1000 or f(m) for any m not equal to N.)
>
> It looks like you are asking for a hashing function that hashes
> values in [1, 1 000 000] into a subset of 26^12 possible values
> (assuming you meant 12 members from an alphabet of 26 letters).
>
> Someone else pointed out that 26^12 = 95,428,956,661,682,176.
> So you need a function that hashes 20-bit values into a 57-bit
> values. Finding a suitable hashing function with few collisions
> should be fairly easy.

Or, if you want to be absolutely sure of there being no collisions,
find a block cipher that works with 57 (or 58) bit blocks and use the
"hasty pudding trick" to restrict it to the 26^12 possible values.

(The "hasty pudding trick" is a cryptography term for the fact that,
given a permutation f of some finite set Y, you can construct a
permutation g of a subset X of Y simply by iterating f until the
output is in X -- i.e. letting g(x) = f^{k_x}(x), where k_x is the
smallest positive integer such that f^{k_x}(x) is in X. Furthermore,
applying the same trick to the inverse of f yields the inverse of g.)

Mind you, that's probably not really necessary: the probability of a
random hash giving a collision among 1,000,000 out of 26^12 values is
less than one in 190,000.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Why does JH Conway say -1 is prime?
Next: Sum of permutations