Карта, увеличивающая целое число, располагается к шестиразрядной основе 26 макс., но непредсказуемо

Почему бы просто не перетасовать биты в определенном порядке перед преобразованием в значение с основанием 26? Например, бит 0 становится битом 5, бит 1 становится битом 2 и т. Д. Для декодирования просто сделайте обратное.

Вот пример на Python. (Теперь отредактировано, чтобы включить преобразование базы.)

import random

# generate a random bit order
# you'll need to save this mapping permanently, perhaps just hardcode it
# map how ever many bits you need to represent your integer space
mapping = range(28)
mapping.reverse()
#random.shuffle(mapping)

# alphabet for changing from base 10
chars = 'abcdefghijklmnopqrstuvwxyz'

# shuffle the bits
def encode(n):
    result = 0
    for i, b in enumerate(mapping):
        b1 = 1 << i
        b2 = 1 << mapping[i]
        if n & b1:
            result |= b2
    return result

# unshuffle the bits
def decode(n):
    result = 0
    for i, b in enumerate(mapping):
        b1 = 1 << i
        b2 = 1 << mapping[i]
        if n & b2:
            result |= b1
    return result

# change the base
def enbase(x):
    n = len(chars)
    if x < n:
        return chars[x]
    return enbase(x/n) + chars[x%n]

# go back to base 10
def debase(x):
    n = len(chars)
    result = 0
    for i, c in enumerate(reversed(x)):
        result += chars.index(c) * (n**i)
    return result

# test it out
for a in range(200):
    b = encode(a)
    c = enbase(b)
    d = debase(c)
    e = decode(d)
    while len(c) < 7:
        c = ' ' + c
    print '%6d %6d %s %6d %6d' % (a, b, c, d, e)

Вывод этого скрипта, показывающий процесс кодирования и декодирования:

   0            0       a            0    0
   1    134217728  lhskyi    134217728    1
   2     67108864  fqwfme     67108864    2
   3    201326592  qyoqkm    201326592    3
   4     33554432  cvlctc     33554432    4
   5    167772160  oddnrk    167772160    5
   6    100663296  imhifg    100663296    6
   7    234881024  ttztdo    234881024    7
   8     16777216  bksojo     16777216    8
   9    150994944  mskzhw    150994944    9
  10     83886080  hbotvs     83886080   10
  11    218103808  sjheua    218103808   11
  12     50331648  egdrcq     50331648   12
  13    184549376  pnwcay    184549376   13
  14    117440512  jwzwou    117440512   14
  15    251658240  veshnc    251658240   15
  16      8388608   sjheu      8388608   16
  17    142606336  mabsdc    142606336   17
  18     75497472  gjfmqy     75497472   18
  19    209715200  rqxxpg    209715200   19

Обратите внимание, что ноль соответствует нулю, но вы можете просто пропустить это число.

Это простой, эффективный и достаточно подходящий для ваших целей. Если вам действительно нужно что-то безопасное, я бы явно не рекомендовал это. По сути, это наивный блочный шифр. Коллизий не будет.

Вероятно, лучше всего убедиться, что бит N никогда не отображается на бит N (без изменений), и, вероятно, лучше всего, если некоторые младшие биты на входе будут сопоставлены с более высокими битами на выходе, В основном. Другими словами, вы можете захотеть сгенерировать отображение вручную. Фактически, приличное отображение было бы просто обратным порядком битов. (Это то, что я сделал для примера вывода выше.)

Как насчет LFSR ? Регистр сдвига с линейной обратной связью используется для генерации псевдослучайных чисел в диапазоне - операция детерминирована с учетом начального значения, но она может посещать каждое значение в диапазоне с длинным циклом.

Это зависит от того, что вы подразумеваете под непредсказуемым. Если вам нужна криптографическая безопасность, вас может заинтересовать алгоритм Blum Blum Shub , но вы, вероятно, этого не сделаете.

Я реализовал регистр сдвига с линейной обратной связью для этой цели. предоставления случайных уникальных идентификаторов. LFSR просты в реализации, и они циклически перебирают все возможные комбинации, хотя можно вычислить следующее число с учетом предыдущего числа (это непросто, но это можно сделать).

Похоже, что можно отобразить состояния LFSR с помощью порядковых номеров (т. Е. N-го состояние LFSR - x), но на него есть патент ... Но вы все равно хотите пойти в обратном направлении.

Использование хеш-функции с семенем должно сделать его непредсказуемым.
Безопасность, очевидно, не проблема (иначе вы использовали бы криптографию ).

Фактически, вы могли бы сразу использовать MD5 и выбрать фиксированные 6 символов для простого решения, которое будет хорошо работать. Он доступен на большинстве языков и генерирует буквенно-цифровой хэш 128-битный хеш, который легко записывается в виде 32 шестнадцатеричных чисел. На самом деле это всего 16 символов (сокращается до 16).

Не рекомендуется разрабатывать собственный алгоритм для непредсказуемого хеширования.
Вот запись в блоге Coding Horror, которую вы тоже должны прочитать .

Я явно дважды цитирую ссылку Джеффа на Coding Horror, чтобы подчеркнуть.

Предположим, вы используете что-то вроде MD5 (БОГ HASH). MD5 принимает строку входных байтов любой длины и выводит 128 бит. Биты последовательно случайны на основе входной строки. Если вы отправите одну и ту же строку дважды, вы получите те же самые случайные 16 байтов. Но если вы внесете даже крошечное изменение во входную строку - даже одно изменение бит - вы получите совершенно другой выходной хэш.

Итак, когда вам нужно беспокоиться о коллизиях? Действующее практическое правило здесь исходит из парадокса дней рождения. По сути, вы можете ожидать увидеть первую коллизию после хеширования 2n / 2 элементов или 2 ^ 64 для MD5.

2 ^ 64 - большое число. Если в сети 100 миллиардов URL-адресов, и мы обработали их все с помощью MD5, увидим ли мы конфликт? Ну нет, поскольку 100000000000 намного меньше 2 ^ 64:

2 ^ 64 18,446,744,073,709,551,616
2 ^ 37 100000000000

Обновление на основе комментариев.

• С шестизначным шестнадцатеричным представлением, как я предлагаю выше, вероятность коллизий снижается до 2 ^ 12 , что составляет всего 4096 ! (прочтите всю статью Coding Horror, чтобы узнать о нюансах.)
• Если вы не хотите, чтобы ваше сокращение (одно и то же сокращенная форма URL каждый раз) повторялось, подойдет случайное число.

26 ^ 6 составляет около 300 миллионов.

Проще всего использовать генератор случайных чисел, и если у вас есть коллизия (т.е. если ваш случайно сгенерированный 6-буквенный идентификатор уже используется ), увеличивайте до тех пор, пока у вас не будет свободного идентификатора.

Я имею в виду, конечно, вы получите коллизии довольно рано (около 17 тысяч записей), но увеличение до тех пор, пока у вас не будет бесплатный идентификатор, будет достаточно быстро, по крайней мере, пока вы пространство ключей начинает переполняться (около 12 миллионов записей), и к тому времени вы все равно должны перейти на 7-буквенные идентификаторы.

Вы хотите переставить свой первоначальный автоинкрементный идентификационный номер с сетью Фейстеля. Это сообщение (которое есть в списках PostgreSQL, но на самом деле не имеет ничего общего с PostgreSQL) описывает простую сеть Фейстеля. Конечно, существует множество вариаций, но в целом это правильный подход.

Вы можете использовать инструменты Xcode, которые уже включены в OSX.

Xcode - тот же профессионал набор инструментов разработчика, используемый Apple для создать Mac OS X, а также многие другие Приложения Apple, а Xcode - это t найти готовый хороший блочный шифр для вашего размера. Но, как предлагает kquinn, вы можете самостоятельно разработать такой, который имитирует другие шифры.

Недавно я задал в основном тот же вопрос, и решение заключалось в увеличении на простое число (по модулю макс ), чтобы получить красивую, казалось бы, случайную последовательность без повторения любого числа: Уникальный код в стиле Tinyurl: потенциальный алгоритм предотвращения коллизий