A hash-like function with a short inconsistent digest and no collisions?

Sergey Sokolov2012-07-29 08:09:59

Programming

Sergey Sokolov, 2012-07-29 08:09:59

For integers in a range, 0..Myou need to get n-character matches that do not look sequential:
0 JZQ736
1 KVYZ97
2 PW7NB3
Prompt f-th f(i) = sto get such micro-hashes without collisions in a given range. And it would be quite cool to reverse function f1(s) = ito get an integer from the code, or to find out that the code is leftist.
Crypto resistance is not required, this is for the marketing beauty of the tickets.

Answer the question

In order to leave comments, you need to log in

9 answer(s)

MikeMirzayanov, 2012-07-29
@sergiks

It can be so. Works for all m from 1 to MOD-1. If not enough, then you can either increase the constants (then the length can grow), or slightly adapt the algorithm. I adjusted it so that it was like in the example of 6 characters in the code. In fact, you can do everything in 64-bit variables, it's just more convenient in Java.

    private static final BigInteger MULTIPLIER = BigInteger.valueOf(13L);
    private static final BigInteger MOD = BigInteger.valueOf(99990001L);
    private static final BigInteger ADDEND = BigInteger.valueOf(699930007L);

    public static String encode(long m) {
        if (m <= 0 || m >= MOD.longValue()) {
            throw new IllegalArgumentException("Argument is out of range.");
        }
        return BigInteger.valueOf(m).modInverse(MOD).multiply(MULTIPLIER)
                .add(ADDEND).toString(36).toUpperCase();
    }

    public static long decode(String encoded) {
        return new BigInteger(encoded.toLowerCase(), 36).subtract(ADDEND).divide(MULTIPLIER)
                .modInverse(MOD).longValue();
    }

Here are examples of what happens (for different m):

1 BKPXGK
2 MBOAIK
3 PWNQV8
4 RP5H1K
5 SRUICK
10000 X2JV9T
10001 PWMTFN
10002 U025II
10003 TRK6AU
10004 JRJEMK
10005 UARMRU
10006 S2NCNJ
10007 R1E1UK
10008 HRCMBX
10009 WU4GN7
99989996 FVI2O7
99989997 GY73Z7
99989998 IQOU5J
99989999 MBOAI7
99990000 X2MNK7

xanep, 2012-07-29
@xanep

You don't need a hash function because you will not be able to convert back, and collisions are possible in any case. The best solution for you is to convert from decimal to N-script, where N is the number of characters you want to use (26 Latin letters + 10 digits?). How to do this is written on the wiki . So that the numbers do not look sequential, you can wrap the bits of the original number in reverse order.

CKOPOBAPKuH, 2012-07-29
@CKOPOBAPKuH

> Tell me an analogue of hash functions, but shorter, and without collisions?
in such a setting, a unicorn can help you.

Vitaly Sivkov, 2014-01-13
@Sivkoff

Good day to all.
If someone needs it, I implemented @MikeMirzayanov 's algorithm in php .

Gribozavr, 2012-07-29
@gribozavr

Mathematical approach: take two primes, a and m, with M < a < m, m being the largest prime less than {alphabet power}^{number of characters in the code}. f(i) = i * a (mod m), f(s) = i * a^-1 (mod m), where a^-1 is the reciprocal of a modulo m.
Programming approach: f(i) = bits of i in reverse order. Then successive tickets will not appear to have consecutive codes. After converting to a string, you can add random characters to fixed locations.

ekim, 2012-07-29
@ekim

it?
www.manhunter.ru/webmaster/421_kak_sdelat_svoy_servis_korotkih_ssilok.html

AlexanderG, 2012-07-29
@AlexanderG

Try to use any PRNG (pseudo-random number generator), take your index as a seed. Since the numbers are pseudo random, each grain will uniquely correspond to a known result, which satisfies the condition of the problem. For example, a linear congruential method might be appropriate: it maps a seed to a single result; allows you to perform the inverse transformation; easy to implement.

Lico, 2012-07-29
@Lico

CRC-24?

Gokjer, 2012-07-29
@Gokjer

In the case of not very large M, you can generate M random n-character combinations (checking for uniqueness by shoving into some dictionary / tree / ..), match each number with a combination in order and just remember them.