2015-10-22
588
При реализации выгодно выбирать 
, где e — число битов в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.
Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в d-мерном пространстве, точки ложатся не более, чем на 
гиперплоскостей, что ограничивает применение генератора в методе Монте-Карло.
В таблице ниже приведены наиболее часто используемые параметры линейных конгруэнтных генераторов, в частности, в стандартных библиотеках различных компиляторов (функция rand()).
| Source | m | a | c | выдаваемые биты результата в rand() / Random(L) |
| Numerical Recipes (англ.) | 232 | |||
| MMIX by Donald Knuth | 264 | |||
| Borland C/C++ | 232 | биты 30..16 в rand(), 30..0 в lrand() | ||
| GNU Compiler Collection | 232 | биты 30..16 | ||
| ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++ | 232 | биты 30..16 | ||
| Borland Delphi, Virtual Pascal | 232 | биты 63..32 числа (seed * L) | ||
| Microsoft Visual/Quick C/C++ | 232 | биты 30..16 | ||
| Apple CarbonLib | 231 - 1 | см. Метод Лемера (англ.) |
Криптоанализ
|
|
|
Особенностью линейного конгруэнтного метода является то, что если сомножитель и модуль соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от случайной последовательности элементов множества { 0, 1, 2, …, m-1 }. Однако, все элементы этой последовательности однозначно определяются четырьмя параметрами: X0, a, c, m.
Если криптоаналитик знает об использовании линейного конгруэнтного метода с известными параметрами, то известной становится вся последовательность чисел. В то же время, даже если криптоаналитик знает только лишь об использовании линейного конгруэнтного метода, то информация о небольшой части последовательности достаточна для выявления параметров метода и всех последующих элементов последовательности. В частности, если криптоаналитику известны значения 
, то они удовлетворяют системе уравнений:
из которой можно получить значения параметров а, с и m.
Поэтому, хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким.
Рандомизация
Этот метод доступа имеет несколько названий: перемешивание, рандомизация, хэширование. Общая схема представлена на рисунке 4:
Область размещения элементов
линейного списка
Рисунок 4
Область размещения элементов линейного списка делится на участки – бакеты. При добавлении элементов линейного списка в соответствии со значениями первичных ключей Кi алгоритм рандомизации определяет не адрес отдельного элемента (как это было в предыдущих случаях), а номер (адрес) бакета. Сам элемент размещается в бакете в первом свободном месте – после уже имеющихся в нем элементов. Таким образом, список элементов внутри бакета не упорядочен.
|
|
|
При поиске элемента алгоритм рандомизации по первичному ключу определяет вначале номер бакета, в котором должен находиться элемент. Затем уже в найденном бакете методом последовательного сканирования делается попытка найти нужный элемент (см. метод последовательного сканирования для неупорядоченного списка).
Алгоритм рандомизации состоит из следующих шагов:
1. этот шаг выполняется только для нечисловых значений ключа и состоит в их преобразовании в числовые значения. Для этого каждому символу алфавита, который используется для записи значения ключа, приписывается десятичная цифра от 0 до 9, и ключ переписывается. Например, пусть значения ключа формируются из букв русского алфавита. Припишем им десятичные цифры:
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ ь ъ ы э ю я
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
Тогда, например, ключ Сидоров запишется как 8945752 (различие прописных и строчных букв игнорируется). Очевидно, такая замена может привести к тому, что разные нечисловые значения будут иметь одинаковые числовые замены. Это одна из причин потери информации при выполнении алгоритмов рандомизации;
2. порядок числового значения ключа приводится к порядку максимального номера бакета. Например, если максимальный номер бакета - четырехзначное число, то числовой ключ 8945752, полученный в предыдущем шаге, должен быть преобразован в четырехзначное число. Для такого преобразования существуют разные способы. Некоторые из них показаны ниже (в предположении, что максимальный номер бакета – четырехзначное число):
· метод квадратов: значение ключа возводится в квадрат. В полученном числе выбирается средняя часть, состоящая из требуемого количества цифр. Например, для числа 8945752 такое преобразование будет иметь вид:
| ⇒ | ⇒ | |||
| ||||
| средняя часть числа, состоящая из 4 цифр |
· сдвиг разрядов: разряды ключа делятся на старшие и младшие и "сдвигаются" друг к другу так, чтобы число перекрывающихся разрядов соответствовало требуемому числу цифр. Совмещенные цифры складываются. Например, для числа 8945752 такое преобразование будет иметь вид:
| ⇒ | ⇒ | (13)(16)92 | ⇒ | |||
| ⇓ | совмещенные разряды | результат сложения совмещенных разрядов | окончательный результат | |||
| старшие разряды | младшие разряды |
· метод складывания: ключ делится на 3 части, средняя из которых по количеству цифр равна требуемому порядку. Первая и третья части налагаются на среднюю часть и совмещенные цифры складываются. Например, для числа 8945752 такое преобразование будет иметь вид (здесь средняя часть - 9457):
| ⇒ | 8 25 | ⇒ | (17)47(12) | ⇒ | ||
| ⇓ | наложенные части числа | результат сложения | окончательный результат | |||
| средняя часть числа |
Очевидно, рассмотренные методы могут дать одинаковые результаты для разных числовых значений ключа. Это вторая причина потери информации при рандомизации. Выбор того или иного метода из трех рассмотренных выполняется экспериментально: лучшим считается тот метод, при использовании которого бакеты заполняются элементами относительно равномерно;
3) полученное на предыдущем шаге число умножается на константу С, которая рассчитывается как отношение максимального номера бакета Nmax к максимальному n-разрядному числу, где n – порядок максимального номера бакета. Это позволяет сформировать реальные номера бакетов. Например, пусть максимальный номер бакета – 7000 (это Nmax). Очевидно, n = 4. Тогда упомянутая константа С имеет значение:
|
|
|
С = 7000/9999 = 0,7.
Рассчитаем реальный номер бакета для результата предыдущего шага, полученного методом складывания: 8473 * 0,7 = 5931.
Пример 9. Рассмотрим решение задачи добавления элементов линейного списка таблицы 11.
Поскольку в линейном списке только 4 элемента, пусть максимальный номер бакета Nmax равен 0009, тогда порядок максимального номера бакета n = 4.
Применим алгоритм рандомизации для получения номеров бакетов первичных ключей элементов таблицы 11 – фамилий Скворцов, Соколов, Строков, Супруненко. При этом используем все три метода приведения числового значения ключа к порядку максимального номера бакета.
Решение задачи состоит из следующих шагов:
1. преобразование нечисловых значений ключей в числовые (используется соотношение, приведенное ранее):
Фамилия (ключ) Числовое значение ключа
Скворцов 81257352
Соколов 8515252
Строков 8975152
Супруненко 8067045415
2. приведение ключа к требуемому порядку:
· метод квадратов. Преобразование ключа показано в таблице 15:
Таблица 15
| Числовое значение ключа | Квадрат значения | Средняя часть числа (результат) |
· сдвиг разрядов. Преобразование ключа показано таблице 16:
Таблица 16
| Числовое значение ключа | Совмещенные разряды | Результат сложения | Результат | |
| старшие разряды | младшие разряды | |||
| (15)477 | ||||
| (13)762 | ||||
| (13)(10)(12)2 | ||||
| (12)5(10)85 |
Поскольку для последнего ключа (выделен полужирным курсивом) результат имеет 5 разрядов (требуется 4), с этим значением ключа продолжается работа по тому же методу (таблица 17):
Таблица 17
| Числовое значение ключа | Совмещенные разряды | Результат сложения | Результат | |
| старшие разряды | младшие разряды | |||
· метод складывания. Преобразование ключа показано таблицей 18:
|
|
|
Таблица 18
| Числовое значение ключа | Наложенные части числа | Результат сложения | Результат | ||
| левая часть | средняя часть | правая часть | |||
| 3(13)98 | |||||
| 8 25 | (13)177 | ||||
| 8 25 | (17)776 | ||||
| (13)5(13)9 |
3) формирование реальных номеров бакетов. Для определения константы С выполним следующие вычисления:
С = Nmax/9999 = 0009/9999 = 0,0009.
Тогда номера бакетов рассчитаны по приведенной ранее формуле и представлены в таблице 19:
Таблица 19
| Фамилия (ключ) | Номер бакета | ||
| метод квадратов | сдвиг разрядов | метод складывания | |
| Скворцов | |||
| Соколов | |||
| Строков | |||
| Супруненко |
Для анализа эффективности методов построим схему распределения элементов исходного линейного списка (таблица 11) по бакетам:
1. метод квадратов. Распределение элементов по бакетам показано в таблице 20:
Таблица 20
| Номер бакета | Содержимое бакета | ||||
| Строков | Иван | Иванович | ул. Красная, 9 - 2 | ||
| Соколов | Юрий | Кузьмич | ул. Леонова, 23 - 98 | ||
| Скворцов | Олег | Иванович | пр. Мира, 45 - 3 | ||
| Супруненко | Виктор | Егорович | Каштановая аллея, 23 - 5 | ||
2. сдвиг разрядов. Распределение элементов по бакетам показано в таблице 21:
Таблица 21
| Номер бакета | Содержимое бакета | ||||
| Супруненко | Виктор | Егорович | Каштановая аллея, 23 - 5 | ||
| Соколов | Юрий | Кузьмич | ул. Леонова, 23 - 98 | ||
| Строков | Иван | Иванович | ул. Красная, 9 - 2 | ||
| Скворцов | Олег | Иванович | пр. Мира, 45 - 3 | ||
3. метод складывания. Распределение элементов по бакетам показано в таблице 22:
Таблица 22
| Номер бакета | Содержимое бакета | ||||
| Скворцов | Олег | иванович | пр. Мира, 45 - 3 | ||
| Соколов | Юрий | Кузьмич | ул. Леонова, 23 - 98 | ||
| Супруненко | Виктор | Егорович | Каштановая аллея, 23 - 5 | ||
| Строков | Иван | Иванович | ул. Красная, 9 - 2 | ||
Как показывает анализ, все три метода с одинаковой равномерностью заполняют бакеты: один бакет содержит два элемента, остальные – по одному, т.е. методы равноэффективны.
