ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Программные датчики. Общая модельОсновные свойства 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. xm mod N = xa+b+c mod N = (xaxbxc) mod N = [(xa mod N) * (xb mod N) * (xc mod N)] mod N 23. (a*(b+c)) mod N = ((a*b) mod N + (a*c) mod N) mod N 24. xa*i mod N = (xa mod N)i mod N Например: 319 mod 15 = 319 – 15 * Int(319/15) = 1162261467 – 15*77484097 = 12 19 = 16 + 2 + 1 Следствие: если xa mod N = 1, то и xa*i mod N = 1 Пример 2: Общие формулы вычисления больших степеней. ab 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. Свойство коммутативности. Обозначим xa mod N = Fa(x), xb mod N = Fb(x) Будет верно тождество Fa(Fb(x)) mod N = Fb(Fa(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 = 24 mod Φ = 16 mod 8 = 0 ад ля х = 3: 34 mod 8 = 81 mod Φ = 1.Генерация псевдослучайных последовательностей (ПСП) чисел и бит Виды датчиков ПСП 1) Специально составленная и откорректированная на «случайность» таблица. Недостаток: мал объём таблицы и большой расход памяти ПК на таблицу. 2) Физический датчик. Формирование ПСП из сигнала электронного шума радиоламп, полупроводников, резисторов. Недостатки: наличие схемной нестабильности генератора, необходимость частой градуировки и контроля. Формирование ПСП с помощью использования устройств ядерного распада радиоактивных элементов. Дорого и сложно. 3) Формирование ПСП программой ПК. 4) Программно -аппаратный датчик ПСП на регистрах сдвига. Программные датчики. Общая модель α i = φ (α l -i,..,αi-p) l < p, Исходные величины α0, α − 1, α − 2 ,... α − (p − 1) фиксируются заранее и называются стартовыми величинами.
Линейные рекуррентные формулы 1. Мультипликативный конгруентный метод (метод вычетов) α i =(β ⋅ α i-1) mod M, i = 1, 2,... β, M, α0 – натуральные числа – параметры программного датчика. α0 , α1,…..∈ {01,..., (M -1)} Эта ПСП зацикливается, начиная с некоторого номера i = T. Её период, равный Т, не превосходит М -1. Пусть М = 2q, q – количество бит целой константы ПК. Тогда: Tmax = 2q-2 = M/4 достигается, если: 1) α 0 – нечётное число, причём 1 ≤ α0 ≤ M − 1; 2) β mod 8 = 3 mod 8 или β mod 8 = 5 mod 8. Это условие выполняется, например, при β = 52p+1, p = 0,1,2,…, или когда β = 2m + 3, m = 3,4,5,… 2. Метод, использующий линейные смешанные формулы, в частности, смешанный конгруентный метод. α i= (β ⋅ αi-1 + C) m od M, i = 1,2 Для получения максимального периода следует брать М = 2n и использовать β = 2q + 1, q ≥ 2, C – нечётное и α0 – произвольное. Хоффман рекомендует выбирать β из условия β mod 4 = 1. Методы, использующие нелинейные рекуррентные формулы 3. Метод середины квадрата. αi=(((αi-1)2) mod 23k –((αi-1)2)mod22k ) /2k,i = 1,2 Параметры датчика: k и α0. Заметим, что α0 – число, образованное средними 2k битами 4k-разрядного двоичного числа (αi−1 )2. 4. Модификация метода – метод середины произведения. αi =((αi−1 ⋅ α i−2 )mod 23k –(αi−1 ⋅ α i−2)) / 2k, i=1,2,… 5. Квадратичный конгруентный метод (обобщение линейного). αi =(γ⋅ (αi-1)2+ β⋅ αi-1+C)mod M,i= 1,2….. П а р а м е т р ы д а т ч и к а: α0, M, β, γ, С. Если М = 2q и q ≥ 2, то наибольший период Тmax = M = 2q достигается, если β, С – нечётные, γ – чётное, причём β 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(cj⋅k) di:= V(s) i = 1,2,… V(s):= bi+k Т.е. датчик D2 делает случайный выбор из таблицы V, а также случайно заполняет её числами, порождёнными датчиком D1. Можно получить очень большой период ПСП, если периоды датчиков D1 и D2 – взаимно простые числа. Не нашли, что искали? Воспользуйтесь поиском:
|