Генератор чисел (ГЧ) на основе линейной конгруэнтной последовательности X_i+1 = ( AЧ X_i + B)(mod C), не обеспечивающий полного периода, когда C – простое число.

___________________________________________________________________________________________

X_i+1 = (AЧ X_i + B)(mod C), (1)

при условиях 0 Ј X_i < C, 1 < A< C, 0 < B < C, C > 3 и (A, C) = 1, (2)

1. числа, обеспечивающие генерацию X_i в диапазоне 0 Ј X_i < C;

n>2 всегда чётная, т. е. V(n) є 0 (mod 2); (3)

– i-тый множитель канонического разложения числа V(C), ci – его степень;

Далее нам понадобятся ссылки на теоремы, которые здесь приводятся без доказательств. Окончания теорем обозначены символом Ё .

всегда существует, и при том единственное число X_i = X_a такое, что

X_a = (AЧ X_a + B)(mod C)Ё (5)

Теорема BG. В выражении (1), если C – простое число, то весь диапазон чисел 0 ё (C–1) разбивается на m участков, каждый длиной s чисел, так что

m · s = C – 1 = V(C) ; (6)

ts = T(V(C)) – 1; (8)

Любое значение s не может быть чем–либо другим, кроме как делителем числа V(C), исключая 1. Ё

Это значит, что наименьшее значение s = 2, или 1< s ЈV(C); (9)

Теорема BL. Если в (1) А = С–1, то при любом С длина участка s минимальна и равна s = 2, а количество участков m максимально и равно m = (C–1)/2, если С нечетное, или m = C/2, если С – чётное. Ё

Теорема BN. В выражении (1), при заданном простом числе C и выбранном значении s, обеспечивающим необходимое количество m участков, число A определяется из выражения: A^s = 1 (mod C); (11)

ta = V(s); Ё (12)

Таким образом, количество значений А, обеспечивающее максимальную длину участка s_max равно: ta_max = V(V(C)). Естественно, что это количество значений А максимально. а количество участков при такой длине s_max равно m = 1. Согласно теореме BL, минимальное количество значений А равно V(2) = 1. Поскольку общее количество значений А из диапазона (2) равно С – 2, то оставшееся количество значений А равно С – 3 – V(V(C)). И, наконец, общее количество значений А можно выразить формулой Гаусса [3]: С – 2 = Здесь все значения s_i выбираются из выражения (8). Если предположить, что все значения А распределены равномерно между 1 и С–1, и если иметь в виду ограничение (14), то при С>4е+4, вышеупомянутые количества будут составлять » 0.99 и более от вычисленных.

a) всегда, не зависимо от начального значения X[0], за конкретным значением Xa следует Xb, а за ним всегда следует конкретное значение Xc и т. д. Это нежелательное явление при использовании ГЧ в криптографии;

b) при проверке по всем тестам можно достичь отличных результатов, но невозможно сконструировать ГЧ, в периоде которого встречались бы “случайные неслучайности”;

c) увеличение количества чисел в таких ГЧ достигается только путём увеличения числа C. Если учесть, что обычная разрядность компьютера 2³², то, чтобы не произошло переполнение разрядной сетки, необходимо выполнение условия:

(A·(C – 1)+B) Ј (2³²–1); (13)

C^0.5 < A < (C – C^0.5), (14)

ceil(k·C) Ј B Ј floor(k·C), (15)

где k = () » 0.2113248654051871;

Таким образом, используя 4-х байтную целую арифметику и ГЧ с полным периодом, можно получить ряд чисел максимальной длины » 2.65 ·10⁶. Использование же подпрограмм для 8–10-байтной арифметики существенно сказывается на скорости работы программы.

В предлагаемом ГЧ с множеством участков (МГЧ) обычно количество участков m выбирается в пределах от 2 до 50. Если задать начальное значение X[0], принадлежащее i-му участку, то будут сгенерированы все значения X, принадлежащие этому участку и значения начнут повторяться. В этом случае необходимо взять X[0] с i+1-го участка, и так до тех пор, пока не будут использованы X[0] со всех m участков. Таким образом, в итоге будут получены все C значений X в диапазоне от 0 до C – 1. Здесь учитывается и Xа, согласно теореме BF.

1.2 Выбора начального значения X[0] с каждого участка. Количество сочетаний выбора начальных значений равно s^m;

1.3.1 Последовательно, получив все значения X с i-го участка, как описано выше, перейти к участку i+1. И так переходить от участка к участку, пока не будет достигнут конец участка m;

1.3.3 На участке i получить k значений, на участке j получить p значений. Иначе: номер очередного выбираемого участка – функция F₁, количество выбираемых чисел с этого участка – функция F₂. Переходя от участка к участку, получать разные количества X. При этом обеспечить равномерный закон распределения на протяжении от 0 до C – 1. Т. е., каждое число на участке от 0 до С – 1 должно встретиться только один раз.

Всё это дaет возможность при заданных значениях A, B и C получить не 1 ряд сгенерированных чисел, как в случае полного периода, а приблизится к теоретически возможному количеству рядов: – C!. Используя только п. 1.3.1 и 1.3.2, можно получить m!· s^m ; рядов, каждый длиной в С чисел. Для вышеописанного примера меньшее простое число C=2641061. Выбрав, скажем, m=43, находим s=61420, и количество чисел, которые можно получить при этом

N = 43! Ч 61420^43Ч 2.641061Ч 10⁶=1.25964Ч 10²⁶⁵.

На рис. 1 схематично представлен ГЧ с полным периодом генерации чисел,

на рис. 2 – МГЧ, при m = 5.

Описанный МГЧ используется совместно с многими другими элементами в разработанном автором криптографическом алгоритме, который условно назван SDK.

..

Теперь более детально произведем разбор примера, в котором С – простое число. Предположим, что нам необходим МГЧ, в котором С находится в диапазоне 6·105 ± 5 % и m = 10 ± 2 . Подходящим простым числом является 582649. С – 1 = 582648 = 2³·3·11·2207. Из этого видно, что количество участков может быть 2, 3, 4, 6, 8, 11, 12, 22 ... Наиболее подходит нам число m=11. Если бы в разложении С – 1 не было необходимого набора множителей – пришлось бы брать другое значение С. Далее: s = 582648 / 11 = 52968; Из (11), с учетом (13), (14) и (15) определяем A и B. Результаты расчетов для этого примера, а также для трёх других примеров, в которых C – простое число, сведены в таблицу 1.

Для приведенных четырех примеров были проведены статистические испытания.

Для каждого примера генерировались 4 файлa, согласно пунктов 1.3.1, ё 1.3.4. Последние два файла генерировались длиной 3·C . Каждое значение X приводилось к диапазону 0 ё 1 и умножалось на 256. Полученные файлы проверялись статистическими тестами при уровне значимости 0.99 . Результаты тестирования приведены в таблице 2.

(С – 2)!(mod C) = 1 и (С – 3)!(mod C) = (С–1)/2. Ё (16)

Теорема BR. Если С – простое число, (C>3), и если С!⁺ – произведение четных чисел, до числа С, а С!^– – произведение нечетных чисел до числа (С – 2), то:

1. Если С(mod 4) = 1, то C!^– є C!⁺(mod C); (17)

2. Если C(mod 4) = 3, то: либо С!^–(mod C) = 1 и C!⁺(mod C) = С–1, (18)

либо наоборот, С!⁺(mod C) = 1, а C!^- (mod C) = С–1. Ё

Теорема BS. Если С – простое число, (C>3), и если С!^H – произведение чисел от 2 до (С–1)/2, а С!^K – произведение чисел от (С–1)/2+1 до (С–1), то:

1. Если С(mod 4) = 1, то C!^H є C!^K(mod C); (19)

2. Если C(mod 4) = 3, то: либо С!^H(mod C) = 1 и C!^K(mod C) = С–1, (20)

либо наоборот, С!^К(mod C) = 1, а C!^Н(mod C) = С–1. Ё

(21)

Z = C–((C–k)!)(mod C), если k(mod 2) = 0. Ё

Справедливо и обратное утверждение: если существуют натуральные числа X >0 и Y > 0, такие, что подстановка их в выражение (22) превращает его в тождество, то С – составное число. Ё

При X = Y, определим корни уравнения X² + 2Ч X – K = 0. (24)

K (mod K1) № X (25)

при всех Х в диапазоне от 2 Ј X Ј X1 и X(mod 2) є 0. Ё

t = (T(C) + T(C)(mod 2) – 2)/2. (26)

Если T(C)(mod 2) № 0, то среди всех X, Y одна пара такая, что X = Y; Ё

Теорема BY. Если T(C)(mod 2) № 0, то sqrt(C) = K1, (27)

где K1 – натуральное число, причем K1 = X + 1 из (22). Ё

1. Кнут Д. Искусство программирования для ЭВМ: пер. с англ.– М.: Мир, 1977.– Т.2.