В кольце целых чисел по модулю Mвсегда найдутся числаa,Mтакие, что

a^N = 1 по mod M.

a^n=N=1 по mod M.

N – это делитель .

Если число - то любой делитель =N.

возьмём для частного случая

P – простое число, a — степень

Если n=2^q, то число является простым

2 ⁿ +1 = 2 ^r + 1 –числа Ферма.

где r = 2^q

- числа Ферма.

Числа являются простыми не для любого q.

На сегодняшний день известны значения q=0,1,2,3,4.

Q
N
N
M
0

a – удовлетворяющее данным условиям.

Пересчитаем основание a:

N’ = ;

(a’) ^N = 1 (a’) ^N/2a = 1 a’ = a^z, где z=2 ^a.

Если изображение имеет размер 1024 * 1024 пиксела, то

M = 65537; a=3; N = 65536.

Достоинства и недостатки методов:

Фурье.

Недостатки: используем комплексные числа, числа все иррационные, нет возможности использовать для малой разрядной сетки.

Достоинства: работа в традиционной арифметике, коэффициенты Фурье имеют простой физический смысл.

Теоретико-числовые преобразования:

Недостатки: арифметика по модулю M, коэффициенты носят абстрактный характер.

Достоинства: вся работа с целыми числами, маленькая разрядная сетка (17 разрядов).

Существуют быстрые алгоритмы взятия линейного преобразования:

Выигрыш может быть получен при использовании метода быстрых теоретико-числовых преобразований. Этот метод наиболее эффективен, если число отсчетов

Схема одномерного преобразования:

Нарисуем для n=4:

Количество ступеней для числа n —

Число выходов на каждой ступени – 2N.

Вернемся к схеме преобразования:

Пренебрегаем данной сложностью. Всего N строк, на каждой строке , всего

Сложность прямого преобразования

Сложность быстрого преобразования:

, где k — коэффициент сложности

Рассмотрим случай, когда .

Т. е.

Например, N=512, k=3