Программные датчики. Общая модель

Основные свойства

18. a mod a = 0

19. (a + b) mod N = (a mod N + b mod N) mod N

20. (a – b) mod N = (a mod N – b mod N) mod N

21. (a * b) mod N = (a mod N) * (b mod N) mod N

Следствие:

Если m = a + b + c, то:

22. x^m mod N = x^a+b+c mod N = (x^ax^bx^c) mod N = [(x^a mod N) * (x^b mod N) * (x^c mod N)] mod N

23. (a*(b+c)) mod N = ((a*b) mod N + (a*c) mod N) mod N

24. x^a*i mod N = (x^a mod N)ⁱ mod N

Например:

3¹⁹ mod 15 = 3¹⁹ – 15 * Int(3¹⁹/15) = 1162261467 – 15*77484097 = 12

19 = 16 + 2 + 1

Следствие: если x^a mod N = 1, то и x^a*i mod N = 1

Пример 2:

Общие формулы вычисления больших степеней.

a^b mod N = (a*a*a*…*a (b раз) mod N) затем применяем формулу (a * b) mod N = (a mod N) * (b mod N) mod N

25. F(φ(x)) mod N = F(φ(x) mod N) mod N

26. Свойство коммутативности.

Обозначим x^a mod N = F_a(x), x^b mod N = F_b(x)

Будет верно тождество

F_a(F_b(x)) mod N = F_b(F_a(x)) mod N для всех x.

27. Теорема Эвклида (300 г. до н.э.)

Если Е и М удовлетворяют условию 0 Б ЕМ и НОД(М, Е) = 1, то существует единственное число D, такое что 0 < D < M и

E*D ≡ 1 (mod M) ((E*D) mod M = 1)

и кроме того D может быть вычислено с помощью расширения алгоритма Евклида при нахождении НОД(М, Е).

Алгоритм Евклида при нахождении НОД (М, Е).

28. Функция Эйлера

Φ(N) — функция Эйлера определяет для каждого положительного целого числа N

количество положительных целых чисел i не превышающих N и таких, что HOD(i,N) = 1,

При N = 1 по определению Φ (1) = 1

1 ≤ i < N

Найдем, например, Φ (8). Вычислим НОД (i, 8), 1 ≤ i < 8, (i = 1, 2, … 7)

Имеем до 4-х i = 1, 3, 5, 7 НОД (i,8) = 1 следовательно Φ (8) = 4.

Очевидно, что для простого числа Р имеем Φ(Р) = Р – 1, так как простое число не делится

нацело на меньшее число. Например, Φ (7) = 7 – 1 = 6, ибо для всех i=1,2,3,4,5,6 НОД(i,7) =

1.

Нетрудно видеть, что для двух неравных простых чисел P и Q

Φ(P*Q) = (P- 1)*(Q – 1) (16)

Например, Φ (6) = Φ (2*3) = 1*2 = 2.

29. Теорема Эйлера

Для любых целых чисел x и N (x < N)

X_Φ(N) ≡ 1 (mod N), X^Φ(N) mod N = 1 (17)

при условии, что НОД (x, N) = 1.

Например, для Φ (8) = 4 сравнение (17), будет выполнено только для

x = 1,3,5,7 для которых НОД (х, N) = 1.

Действительно, например:

для х = 2: 2^Φ(8) mod 8 = 2⁴ mod Φ = 16 mod 8 = 0

ад ля х = 3: 3⁴ mod 8 = 81 mod Φ = 1.Генерация псевдослучайных

последовательностей (ПСП) чисел и бит

Виды датчиков ПСП

1) Специально составленная и откорректированная на «случайность» таблица.

Недостаток: мал объём таблицы и большой расход памяти ПК на таблицу.

2) Физический датчик. Формирование ПСП из сигнала электронного шума

радиоламп, полупроводников, резисторов. Недостатки: наличие схемной

нестабильности генератора, необходимость частой градуировки и контроля.

Формирование ПСП с помощью использования устройств ядерного распада

радиоактивных элементов. Дорого и сложно.

3) Формирование ПСП программой ПК.

4) Программно -аппаратный датчик ПСП на регистрах сдвига.

Программные датчики. Общая модель

α _i = φ (α _{l -i},..,α_i-p) l < p,

Исходные величины α₀, α _{− 1}, α _{− 2} ,... α _{− (p − 1)} фиксируются заранее и называются

стартовыми величинами.

Линейные рекуррентные формулы

1. Мультипликативный конгруентный метод (метод вычетов)

α _i =(β ⋅ α _i-1) mod M, i = 1, 2,...

β, M, α₀ – натуральные числа – параметры программного датчика.

α₀ , α_1,…..∈ {01,..., (M -1)}

Эта ПСП зацикливается, начиная с некоторого номера i = T. Её период, равный Т, не превосходит М -1.

Пусть М = 2^q, q – количество бит целой константы ПК. Тогда:

T_max = 2^q-2 = M/4 достигается, если:

1) α ₀ – нечётное число, причём 1 ≤ α₀ ≤ M − 1;

2) β mod 8 = 3 mod 8 или β mod 8 = 5 mod 8.

Это условие выполняется, например, при β = 5^2p+1, p = 0,1,2,…, или когда β = 2m + 3, m = 3,4,5,…

2. Метод, использующий линейные смешанные формулы, в частности, смешанный

конгруентный метод.

α _i= (β ⋅ α_i-1 + C) m od M, i = 1,2

Для получения максимального периода следует брать М = 2ⁿ и использовать β = 2^q + 1,

q ≥ 2, C – нечётное и α₀ – произвольное. Хоффман рекомендует выбирать β из условия β mod 4 = 1.

Методы, использующие нелинейные рекуррентные формулы

3. Метод середины квадрата.

α_i=(((α_i-1)²) mod 2^3k –((α_i-1)²)mod2^2k ) /2^k,i = 1,2

Параметры датчика: k и α₀. Заметим, что α₀ – число, образованное средними 2k

битами 4k-разрядного двоичного числа (α_i−1 )².

4. Модификация метода – метод середины произведения.

α_i =((α_i−1 ⋅ α _i−2 )mod 2^3k –(α_i−1 ⋅ α _i−2)) / 2^k, i=1,2,…

5. Квадратичный конгруентный метод (обобщение линейного).

α_i =(γ⋅ (α_i-1)²+ β⋅ α_i-1+C)mod M,i= 1,2…..

П а р а м е т р ы д а т ч и к а: α₀, M, β, γ, С.

Если М = 2^q и q ≥ 2, то наибольший период

Т_max = M = 2^q достигается, если β, С – нечётные, γ – чётное, причём

β mod4= (γ+1) mod 4

6. Метод Маклорена-Марсальи.

Метод основан на комбинации двух простейших датчиков. Пусть {bi} и {ci}, i = 0,1,2,… есть ПСП, порожденные двумя независимо работающими датчиками D1 и D2 соответственно. А V = {V(0), V(1), …, V(k-1)} – вспомогательная таблица из k целых чисел.

Сначала таблица V заполнена k членами ПСП {bi}, т.е. V(j) = bj, j = 0,1,2,…,k-1.

Результирующая ПСП получается в результате следующей последовательности

действий:

s:= Int(c_j⋅k)

di:= V(s) i = 1,2,…

V(s):= b_i+k

Т.е. датчик D2 делает случайный выбор из таблицы V, а также случайно заполняет её

числами, порождёнными датчиком D1. Можно получить очень большой период ПСП,

если периоды датчиков D1 и D2 – взаимно простые числа.

Не нашли, что искали? Воспользуйтесь поиском: