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

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