Для установки нажмите кнопочку Установить расширение. И это всё.
Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.
Как перевоплотить Википедию
Хотите, чтобы Википедия всегда выглядела так профессионально и современно? Мы создали расширение для браузера. Оно совершенствует любую страницу энциклопедии, которую вы посетите, с помощью магических технологий WIKI 2.
Попробуйте — вы его можете удалить в любой момент.
Установить за 5 сек.
Да-да, но позже
4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день и почти забыл как выглядит оригинальная Википедия.
-метод Уильямса — метод факторизации чисел с помощью последовательностейчисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель числа . Аналогичен -методу Полларда, но использует разложение на множители числа .
Имеет хорошие показатели скорости подсчёта только в случае, когда легко факторизуется.
Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев[1].
И, следовательно, НОД то есть найден делитель искомого числа [1].
Стоит обратить внимание, что числа не известны на начальном этапе задачи. Поэтому для упрощения задачи сделаем следующее: так как то по свойству (2) Далее воспользуемся свойством (6) и получим:
Таким образом, мы без потери общности можем утверждать, что [1]
Далее пользуемся теоремой из которой делаем вывод, что
2) вводим последовательность натуральных чисел . При этом ;
3) ищем пары значений по следующему правилу:
при этом
4) значения ищутся по правилам (которые следуют из свойств и определения последовательности чисел Люка):
.
Для значений, введённых по умолчанию, то есть получаем результат:
374468
Делаем проверку этого значения. Для этого считаем НОД НОД и .
Если мы в первом шаге неудачно выбрали числа , то есть получилось так, что НОД, то тогда нужно переходить ко второму шагу. Иначе — работа завершена[1].
Второй шаг алгоритма
Пусть число имеет некоторый простой делитель, больший чем , но меньший некоторого , то есть:
, где
Вводим последовательность простых чисел .
Вводим ещё одну последовательность:
Далее определяем:
.
Используя свойство , получаем первые элементы:
.
Далее используем свойство и получаем:
.
Таким образом, мы вычисляем
Далее считаем:
НОД для
Как только получаем , то прекращаем вычисления[1].
Для значений, введённых по умолчанию, то есть получаем результат:
139,
что является верным ответом.
Сравнение скорости работы
Автором данного метода были проведены тесты и методов на машине AMDAHL 470-V7
на 497 различных числах, которые показали, что в среднем первый шаг алгоритма работает примерно в 2 раза медленнее первого шага алгоритма , а второй шаг — примерно в 4 раза медленнее[1].
Применение
В связи с тем, что -метод факторизации работает быстрее, -метод применяется на практике очень редко[1].
Рекорды
На данный момент (27.09.2023) три самых больших простых делителя[3], найденных методом , состоят из 60, 55 и 53 десятичных цифр.
Williams H. C.A p+1 method of factoring (англ.) = A p+1 method of factoring // American Mathematical Society. — 1982. — Т. 39, вып. 159. — С. 225—234. — ISSN00255718.
D. H. Lehmer. An extended theory of Lucas' functions (англ.) = An extended theory of Lucas' functions // Ann. of Math.. — 1930. — Т. 31, вып. 2. — С. 419—448.