Характеристика метода Уильямса

Размещено на http://www.allbest.ru/

Введение

(P + 1) -- метод Уильямса -- метод факторизации чисел n ? N с помощью последовательностей чисел Люка, разработанный в 1982 году. Алгоритм находит простой делитель p числа n. Аналогичен (P ? 1) -- методу Полларда, но использует разложение на множители числа p + 1. Имеет хорошие показатели производительности только в случае, когда p + 1 легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев.

1. Описание алгоритма

Рассматривается последовательность чисел Люка:

u0 = 0, u1 = u, un+1 = Цun - Иun-1,

где Ц и И -- фиксированные целые числа.

p -- простой делитель числа n, причем p + 1 является B-степенно гладким, то есть

где qi -- простые числа, ? B.

Пусть ? последовательность чисел , такая, что каждый ее член удовлетворяет условиям

i = 1,...,k.

Пусть , тогда p + 1 | R. Далее, если для последовательности чисел Люка И взаимно прост с n и выполняется условие

,

то по свойствам последовательности чисел Люка

p | НОД

Далее алгоритм вычисляет элемент последовательности ur и находит НОД.

Для дальнейших выкладок нам понадобится ввести последовательности чисел Люка и перечислить некоторые их свойства.

Пусть {\displaystyle P}P и {\displaystyle Q}Q - некоторые фиксированные целые числа. Последовательности чисел Люка определяются как[1]:

{\displaystyle U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1,\quad U_{n+2}(P,Q)=P\cdot U_{n+1}(P,Q)-Q\cdot U_{n}(P,Q),n\geq 0}

{\displaystyle V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P,\quad V_{n+2}(P,Q)=P\cdot V_{n+1}(P,Q)-Q\cdot V_{n}(P,Q),n\geq 0}

Пусть также {\displaystyle \Delta =P^{2}-4Q.}

Последовательности имеют следующие свойства:

{\displaystyle \left\{{\begin{matrix}U_{n}(V_{k}(P,Q),Q^{k})=U_{nk}(P,Q)/U_{k}(P,Q),\\V_{n}(V_{k}(P,Q),Q^{k})=V_{nk}(P,Q)\end{matrix}}\right.\quad (5)}

Для доказательства данных свойств рассмотрим явные формулы последовательности чисел Люка:

{\displaystyle U_{n}(P,Q)={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}}

где б{\displaystyle \alpha } и в{\displaystyle \beta } - корни характеристического многочлена

{\displaystyle x^{2}-P\cdot x+Q}

Используя явные формулы и теорему Виетта:

{\displaystyle P=\alpha +\beta ;\quad Q=\alpha \cdot \beta ,}

получаем выражения (1), (2), (3), (4) и (5). {\displaystyle (1),(2),(3),(4)} {\displaystyle (5).}

Далее выделяем ещё одно свойство:

И, наконец, формулируем теорему:

Если p -- нечётное простое число {\displaystyle p\mid Q}

{\displaystyle \left\{{\begin{matrix}U_{(p-\epsilon )m}(P,Q)\equiv 0\mod p,\\V_{(p-\epsilon )m}(P,Q)\equiv 2Q^{m(1-\epsilon )/2}\mod p\end{matrix}}\right.\quad (T1)}

Доказательство данной теоремы трудоёмкое, и его можно найти в книге Д. Г. Лемера[2].

2. Оценка сложности

2.1 Первый шаг алгоритма

Пусть -- простой делитель факторизуемого числа , и выполнено разложение:

где -- простые числа.

Пусть

Введём число где степени выбираются таким образом, что

Тогда [1]

Далее, согласно теореме если НОД то

И, следовательно, НОД то есть найден делитель искомого числа [1].

Стоит обратить внимание, что числа не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как то по свойству (2) Далее воспользуемся свойством (6) и получим: число теорема множитель делитель

Таким образом, мы без потери общности можем утверждать, что [1]

Далее пользуемся теоремой из которой делаем вывод, что

И, следовательно, [1]

Теперь выбираем некоторое число такое, что НОД

Обозначаем:

Окончательно, нужно найти НОД[1]

Для поиска поступаем следующим образом[1]:

1) раскладываем в двоичный вид: где .

2) вводим последовательность натуральных чисел . При этом ;

3) ищем пары значений по следующему правилу:

при этом

4) значения ищутся по правилам (которые следуют из свойств и определения последовательности чисел Люка):

.

Для значений, введённых по умолчанию, то есть получаем результат:

374468

Делаем проверку этого значения. Для этого считаем НОД НОД и .

Если мы в первом шаге неудачно выбрали числа , то есть получилось так, что НОД, то тогда нужно переходить ко второму шагу. Иначе -- работа завершена[1].

2.2 Второй шаг алгоритма

Пусть число имеет некоторый простой делитель, больший чем , но меньший некоторого , то есть:

,

где

Вводим последовательность простых чисел .

Вводим ещё одну последовательность:

Далее определяем:

.

Используя свойство , получаем первые элементы:

.

Далее используем свойство и получаем:

.

Таким образом, мы вычисляем

Далее считаем:

НОД для

Как только получаем , то прекращаем вычисления[1].

Для значений, введённых по умолчанию, то есть получаем результат:

139,

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

Таким образом, Автором данного метода были проведены тесты и методов на машине AMDAHL 470-V7 на 497 различных числах, которые показали, что в среднем первый шаг алгоритма работает примерно в 2 раза медленнее первого шага алгоритма , а второй шаг -- примерно в 4 раза медленнее[1]. В связи с тем, что - метод факторизации работает быстрее, - метод применяется на практике очень редко[1].

1. Примеры

С N = 112729 и A = 5, последовательные значения{\ displaystyle V_ {M}}Размещено на http://www.allbest.ru/

являются:

V 1 из seq (5) = V 1! из seq (5) = 5

V 2 из seq (5) = V 2! из seq (5) = 23

V 3 из seq (23) = V 3! из seq (5) = 12098

V 4 из seq (12098) = V 4! из seq (5) = 87680

V 5 seq (87680) = V 5! из seq (5) = 53242

V 6 seq (53242) = V 6! из seq (5) = 27666

V 7 из seq (27666) = V 7! seq (5) = 110229.

В этот момент gcd (110229-2,112729) = 139, поэтому 139 является нетривиальным множителем 112729. Обратите внимание, что p + 1 = 140 = 2 2 Ч 5 Ч 7. Число 7! это самый низкий факториал, кратный 140, поэтому на этом шаге будет найден подходящий фактор 139.

Используя другое начальное значение, скажем, A = 9, мы получаем:

V 1 из seq (9) = V 1! из seq (9) = 9

V 2 из seq (9) = V 2! из seq (9) = 79

V 3 из seq (79) = V 3! из seq (9) = 41886

V 4 из seq (41886) = V 4! из seq (9) = 79378

V 5 seq (79378) = V 5! из seq (9) = 1934

V 6 seq (1934) = V 6! из seq (9) = 10582

V 7 из seq (10582) = V 7! из seq (9) = 84241

V 8 из seq (84241) = V 8! из seq (9) = 93973

V 9 seq (93973) = V 9! из seq (9) = 91645.

В этот момент gcd (91645-2,112729) = 811, поэтому 811 является нетривиальным множителем 112729. Обратите внимание, что p-1 = 810 = 2 Ч 5 Ч 3 4 . № 9! это самый низкий факториал, кратный 810, поэтому на этом шаге будет найден подходящий фактор 811. Фактор 139 не найден на этот раз, потому что p-1 = 138 = 2 Ч 3 Ч 23, который не является делителем 9!

Как видно из этих примеров, мы заранее не знаем, будет ли найденное простое число гладким p + 1 или p-1.

2.3 Факторизовать число 23927

Разложение числа 23927 на множители. Находим наименьшее целое число s такое, что s2?v23927, то есть s=v23927=155. Далее задавая k=0,1,... вычисляем l=(s+k)2?n. Если на каком то шаге l является квадратом натурального числа, то процедуру останавливаем.

Разложение числа 23927 на множители:

23927=337·71

Выполнено за 0.00078600 сек.

От x=155 до x=204 Шагов 50

Список литературы

1. Williams H. C. A p+1 method of factoring (англ.) = A p+1 method of factoring // American Mathematical Society. -- 1982. --,. --. -- ISSN 00255718.

2. D. H. Lehmer An extended theory of Lucas' functions (англ.) = An extended theory of Lucas' functions // Ann. of Math.. -- 1930. --,. --.

3. Bach E., Shallit J. Factoring with cyclotomic polynomials Math.Comp. 1989. V. 52 (185). P. 201--219.

4. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие. -- Казань: Казанский Университет, 2011. -- С. 60-61. -- 190 с.

Размещено на Allbest.ru