Алгоритм генерации случайного числа размера X - PullRequest
9 голосов
/ 24 августа 2011

В моем мобильном приложении я должен предоставить пользователю случайный уникальный X буквенно-цифровой код, чтобы пользователь мог ответить этим буквенно-цифровым кодом для выполнения некоторой задачи.

Количество пользователей, которые собираются использовать это приложение, составляет около 1 миллиона человек, а трафик сообщений составляет около 0,1 миллиона сообщений в день.

Я могу использовать только 26 верхних букв, 26 строчных букв и 10 цифр. Если размер случайного числа равен 5, то я могу сгенерировать 916132832 уникальных комбинаций. После того, как комбинации исчерпаны, я хочу снова использовать это поколение.

Я ищу алгоритмический подход. Есть ли алгоритмический подход для решения этой проблемы?

Ответы [ 11 ]

6 голосов
/ 24 августа 2011

Если вы согласны утилизировать случайные числа, почему вы хотите дождаться исчерпания комбинаций перед повторным использованием?

  • Это делает числа все менее случайными при переходе в конецнабор комбинаций
  • Это вынуждает вас поддерживать некоторую базу данных, чтобы знать, какие числа уже использовались, а какие нет.

Я бы просто генерировал случайные числа, не заботясь, если ониуже был использован.

Если вы действительно хотите сохранить его так, как просили, вот как вы можете это сделать:

  • Сгенерируйте все комбинации и поместите их в базу данных.table
  • Сохранить размер этой таблицы в некоторой переменной
  • Создать случайное число R между 1 и размером таблицы
  • Выбрать комбинацию, хранящуюся в R-й строкетаблица
  • Удалить R-ю строку из таблицы и уменьшить значение переменной размера
  • , если таблица пуста (а переменная размера равна 0), начать заново

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

Вы также можете сделать этов памяти, если вам этого достаточно.

3 голосов
/ 26 августа 2011

Лучший способ сделать это - использовать криптографический трюк под названием Формат сохраняющего шифрования или FPE. Ваша проблема очень похожа на это приложение FPE. Похоже, ваше дело лучше всего решить с помощью сетевого метода Feistel для генерации вашего FPE. В вашем конкретном случае 916132832 составляет примерно 2 29,7 , поэтому вам следует использовать сеть Фейстеля 30-битной ширины вместе с велосипедной ходьбой.

Вы выбираете случайный ключ AES-ключ K и сохраняете это K, а также счетчик C. C начинается с 0 и увеличивается на 1 каждый раз, когда вы вручаете код. Код является FPE-шифрованием C. Когда C достигает 916132832, вы израсходовали все коды. Теперь вы можете выбрать другую клавишу AES K ', установить C = 0 и начать все сначала. Вам может потребоваться сохранить все неподтвержденные (K, C) пары в зависимости от вашего приложения. Возможно, вы захотите, чтобы срок действия этих неподтвержденных пар истек, поэтому ваши требования к хранилищу уменьшаются.

3 голосов
/ 24 августа 2011

Ваши коды могут быть либо уникальными, либо сгенерированными алгоритмом.

Я так понимаю, вы думаете об алгоритме, который бы отображал порядковые номера в коды таким образом, что каждое число <= все возможные коды будут отображаться в предсказуемыекод.Однако он не будет случайным, но может показаться случайным только для пользователя, не знающего алгоритм. </p>

В противном случае вам придется помнить все коды, которые технически неосуществимы.

2 голосов
/ 25 августа 2011

Лучшее решение, о котором я могу подумать, - это ежедневно обновлять закрытый ключ. используйте ключ в сочетании с номером мобильного телефона, чтобы сгенерировать 5-значный код и сохранить этот код в БД. Недействительный код и очистить базу данных при обновлении закрытого ключа. Таким образом, вместо того, чтобы ждать окончания комбинаций, вы решаете, когда существующие коды станут недействительными. Этот подход дает вам возможность увеличить размер кода с 5 до любого другого размера, и вы сохраняете только те значения, которые уже были использованы.

2 голосов
/ 24 августа 2011

С 5 символами вы были бы в безопасности в течение 900 дней, а затем должны быть сброшены.

Я написал код для другого пользователя StackOverflow несколько недель назад. Это генератор случайных чисел, который генерирует только новые числа.

import java.util.BitSet;
import java.util.Random;

/**
 * Random number generator without repeat in the given range at construction time.
 * 
 * @author martijn
 */
public class NoRepeatRandom {

    private Random random;
    private BitSet used;
    private int max;

    /**
     * Creates new instance of NoRepeatRandom, with the range <code>[0-max[</code>.
     * @param max the maximum for the range
     * @param seed the seed for the underlying {@link java.util.Random}
     */
    public NoRepeatRandom(int max, long seed)
    {
        this.max = max;
        this.used = new BitSet(max);
        this.random = new Random(seed);
    }

    /**
     * Creates new instance of NoRepeatRandom, with the range <code>[0-max[</code>.<br />
     * <code>System.currentTimeMillis()</code> is used as seed for the underlying {@link java.util.Random}
     * @param max the maximum for the range
     */
    public NoRepeatRandom(int max)
    {
        this(max, System.currentTimeMillis());
    }

    /**
     * Gives the next random number
     * @return a new random number. When finished it returns -1.
     */
    public int next()
    {
        if (isFinished())
        {
            return -1;
        }
        while (true)
        {
            int r = random.nextInt(max);
            if (!used.get(r))
            {
                used.set(r);
                return r;
            }
        }
    }

    /**
     * Tells if the random generator has finished. Which means that all number in the range
     * [0-max[ are used.
     * @return true if all numbers are used, otherwise false.
     */
    public boolean isFinished()
    {
        return max == used.cardinality();
    }

    /**
     * Sets all the numbers in the range [0-max[ to unused. Which means that all the numbers
     * can be reused.
     */
    public void reset()
    {
        used.clear();
    }

    /**
     * 
     * @return the maximum.
     */
    public int getMax()
    {
        return max;
    }
}

Затем создайте его экземпляр:

NoRepeatRandom nrr = new NoRepeatRandom(916132832);

И чтобы сгенерировать новый код, используйте:

int codeInt = nrr.next();
if (codeInt == -1)
{
    // All the codes are used, need to reset the random generator!
}
String code = toCode(codeInt);

Единственная оставшаяся часть - разработка метода toCode(int):

public static final String charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvw013456789";

public static String toCode(int i)
{
    String code = "";

    return code;
}
1 голос
/ 31 августа 2011

Похоже, вам нужен линейный конгруэнтный генератор. LCG - простая рекурсивная функция вида X (n + 1) = (a * X (n) + c) mod m. LCG <124, 3, 916132832> делает то, что вам нужно, и поражает каждое значение в цикле. Каждое значение в цикле будет соответствовать 5-значному коду, который вы указали.

Справедливое предупреждение, из вашего описания я предполагаю, что вам на самом деле не нужен фактор случайности, просто каждое значение гарантировано уникально для цикла Этот алгоритм не совсем безопасен. Любой может взломать цикл из последнего отправленного вами кода. Если вам нужна какая-то случайность, у вас будут проблемы. Процитирую Джона фон Неймана. «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха».

1 голос
/ 24 августа 2011

У вас есть 62 символа (AZ, az, 0-9).5-значный код - это, по сути, 5-значный базовый номер 62.Сгенерируйте случайное число в соответствующем диапазоне и преобразуйте его в основание 62.

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

1 голос
/ 24 августа 2011

Если вам не нужна надежная защита, тогда простой подход -

  1. Держите счетчик x, работающий с 0 до T-1 с T=62**n, где nэто число символов, которое вы хотите использовать.
  2. Для каждого кода вам нужно просто увеличить x, а затем использовать кодировку (x * P) % T, где P - это простое число, простое число с T и % является оператором по модулю.

Будучи P взаимно простыми с T, вы гарантируете, что отображение (x * P) % T является биекцией, и поэтому все коды будут использоваться до повторного использования первого.

Ибо существует k, поэтому k*P = 1 (mod T) и, следовательно, для каждого y число x = (k * y) % T является обратным y, потому что x*P = (k*y) * P = y * (k*P) = y * 1 = y (mod T), поэтому преобразование x -> (x * P) % T) сюръективно иследовательно, также инъективен, потому что это пространство конечно.

Вы также можете попытаться использовать более сложную биективную функцию, например, ограничить T степенью двойки и использовать битовое перемешивание, но тогда, вероятно, если вам действительно нужна безопасность, это будетбудь лучшепросто использовать случайный код каждый раз, когда проверяется, не слишком ли давно он использовался с очередью и битовой таблицей или хеш-таблицей, в зависимости от того, какой из двух будет меньше.

1 голос
/ 24 августа 2011

Действительно ли существует вероятность исчерпания всех кодов?Вы говорите, что будет только 1 миллион пользователей.Если я правильно понимаю, это означает, что вам нужно будет сгенерировать только 1 миллион кодов.Если это так, то число возможных (например, 5-символьных) кодов намного больше, чем число, которое вам потребуется, и решение простое: просто продолжайте генерировать случайные коды для новых пользователей, пока не найдете тот, который нене принятоВы можете хранить и искать используемые коды в хеш-таблице.

0 голосов
/ 24 августа 2011

Если вы ищете что-то очень простое, попробуйте это:

Date date = new Date();
String random = String.valueOf(date.getTime()).substring(6);

Числа никогда не повторятся в ближайшем будущем!

...