(n-1) - и (n+1) - Критерии Люка 171

кратно m и выполнялось равенство		a(n−1) q =1(n), что	невозможно.
Следовательно, для q = q , получим: qmi |m. Пусть Q = Q(q)= qmi .
i	i		i
Рассмотрим число вида b(q)= am Q (n)		. Порядок этого числа по модулю n
равен Q(q). Таким	образом, для разных	q порядки чисел	b(q) взаимно

просты и равны qimi .

k

Следовательно, порядок числа b =∏b(q) равен ∏qimi = n −1.

q

i=1

13.2.4. Понятие о последовательностях Люка. (n+1) - критерий Люка

Тестирование с помощью теста Ферма можно рассматривать как поиск и анализ членов последовательностей вида fn−1(a)= an−1 −1, делящихся на n.

Аналогичный подход может быть реализован для других видов последовательностей, в частности, рекуррентных. Рассмотрим общую идею

(n +1)- критерия Люка, в котором для тестирования чисел на простоту используется знание простых делителей числа (n +1).

Пусть n >1 - нечетное число, с которым целые числа p и q связаны условием: D = p2 − 4q - квадратичный невычет по модулю n.

Построим две рекуррентные последовательности вычетов по модулю n, которые называются последовательностями Люка, ассоциированными с p и q:

U0 = 0, U1 =1, Uk +2 = pUk +1 − qUk ;

V0 = 2, V1 = p , Vk +2 = pVk +1 − qVk , k ≥0.

Существуют различные соотношения, позволяющие быстро вычислять элементы последовательностей Люка с большими номерами.

Например, U2k =UkVk , V2k =Vk2 − 2qk .

172 Глава 13. ТЕСТ ФЕРМА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ

Оказывается, для этих последовательностей можно сформулировать утверждения, аналогичные малой теореме Ферма.

Например, последовательность {Uk } обладает следующим свойством:

если n - простое, то Un+1(p,q)= 0(n). Аналогия с условием Ферма fn−1(a)= 0(n) очевидна.

Так называемый (n +1)- критерий					Люка	проверки		чисел	на	простоту
формулируется следующим образом.
Теорема.	Пусть		n >1 – нечетное		число.	Если	для любого			простого
делителя r	числа		n +1 существуют		такие простые		числа		p	и q , что
D = p2 − 4q	-	квадратичный		невычет по		модулю		n и	такие, что
Un+1(p,q)= 0(n),		U(n+1) r (p,q)≠ 0(n), то n– простое.
Данная теорема играет роль, аналогичную (n −1)- критерию Люка.
13.3. (P+1) – метод факторизации Вильямса
Пусть n - составное число и				p - его неизвестный простой делитель. На

основе последовательностей Люка можно построить метод факторизации числа

n, аналогичный		(p −1)		- методу Полларда,	если известно,		что число	p +1
является гладким [49].
Это	связано		с	рядом свойств		последовательности		Люка
U1(P,Q),U2 (P,Q),K,				ассоциированной	с	числами	P и Q ,	где
D = P2 − 4Q ≠ 0(n).
Прежде всего,			последовательность Люка сохраняет свойство делимости:
если a |b,	то	Ua |Ub .		Более того, следующие свойства показывают, что
делители числа		Ub ограничивают возможные значения индекса b.

(p+1) – Метод факторизации Вильямса 173

Допустим, M |Ub . Не исключено, что число M делит также один или несколько элементов последовательности Люка с номерами, меньшими b.

Пусть ω =ω(M ) - наименьший такой номер. Назовем ω рангом

появления M в последовательности Люка. Оказывается, если M |Ub , то ω|b.

Далее. Если p - простое, причем НОД(p,2DQ)=1, то p |UΦ(p ), где Φ(p)

выражается через символ Лежандра: Φ(p)	= p −	D	.
	p
В случае, когда D является квадратичным невычетом, Φ(p)= p +1 и
ω(p)|(p +1). Иными словами, делители	(p +1)		могут оказаться индексами

элементов последовательности Люка, которые делятся на p .

Таким образом, как и в (p −1) - методе Полларда, полагая число (p +1)

гладким по отношению к некоторой фактор-базе, можно пытаться строить числа k , делящиеся на ω(p), например, кратные (p +1).

В этом случае	p |Uk , следовательно,				при		Uk ≠ 0(n) можно	найти
нетривиальный делитель n1 числа n в виде n1 =НОД(Uk ,n).
Если Uk = 0(n),	то необходимо	повторить					вычисления для	новых
		D
				= −1		.
значений P ,Q , для которых значение		p