Почему 48-битное начальное число в классе "Утилиты"
Почему этот класс использует 48-битное начальное число в своей формуле линейного соответствия? Я бы ожидал 32 или 64...
Я знаю, что он принимает биты более высокого порядка при запросе 32-битных значений. Но почему только 16 дополнительных битов? Был ли это "случайный" выбор?
3 ответа
Вам нужно больше битов состояния, чем битов вывода, потому что природа LCG такова, что младшие биты состояния совсем не очень случайны. Поэтому, если вы хотите 32-битные выходы, вам нужно более 32 бит состояния.
Почему использовать 48, а не 64? Потому что 48 достаточно, и вы разрабатываете это десятилетия назад, поэтому есть веские причины не использовать больше ресурсов, чем это строго необходимо.
Линейный конгруэнтный генератор (LCG) характеризуется тремя параметрами a, c и m. Только определенные комбинации дают максимальный период, и не все одинаково хорошо изучены. На выбор, вероятно, повлиял обычный компромисс между сложностью и предполагаемым использованием. К счастью, класс достаточно хорошо спроектирован для наследования, поэтому возможны и другие реализации.
Математика, стоящая за этим, исходит из теории чисел и математического определения генераторов псевдослучайных чисел. Это, конечно, не "случайный" (интерпретируемый как произвольный) выбор.
Генератор случайных чисел на компьютере на самом деле пытается быть настоящим генератором псевдослучайных чисел.
Вы можете думать о генераторе псевдослучайных чисел как о функции расширения, которая принимает seed а затем выводит поток номеров G(seed),
В идеале вы хотели бы, чтобы ваш генератор псевдослучайных чисел был неотличим от истинного генератора случайных чисел, но вы также должны понимать, что ваш генератор псевдослучайных чисел должен быть эффективно выбран (полиномиальное время) и детерминирован (то есть, он выдает точно такой же поток, учитывая тот же входное семя).
Таким образом, наличие только 32-битного начального пространства означает, что злоумышленник, желающий определить, является ли ваш поток действительно случайным (или нарушить алгоритм шифрования в зависимости от генератора случайных чисел), должен только пройти 32-битное пространство ключей (начальное пространство) и сэмплировать выходные данные генератора для сравнения с предоставленным вами "случайным" потоком и проверки соответствия. Добавление еще 16 битов значительно увеличивает дальность в пространстве ключей (начальных чисел), делая намного труднее перечисление всех возможных ключей (начальных чисел).
Что касается того, почему бы не перейти на полные 64-битные... вероятно, когда алгоритм был реализован, возможности аппаратной обработки не поддерживали 64-битные операции так эффективно, как это может быть сделано сегодня на современных процессорах на базе x64, поэтому они остановились на 48.