Для установки нажмите кнопочку Установить расширение. И это всё.
Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.
Как перевоплотить Википедию
Хотите, чтобы Википедия всегда выглядела так профессионально и современно? Мы создали расширение для браузера. Оно совершенствует любую страницу энциклопедии, которую вы посетите, с помощью магических технологий WIKI 2.
Попробуйте — вы его можете удалить в любой момент.
Установить за 5 сек.
Да-да, но позже
4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день и почти забыл как выглядит оригинальная Википедия.
Впоследствии алгоритм был улучшен Генри Коэном[en] и Хендриком Ленстрой до APR-CL, время работы которого для любого числа можно вычислить как , где — некоторая вычисляемая константа.
До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Строго говоря, алгоритм не относится к этому классу, однако медленно растущая сложность позволяет практическое использование алгоритма.
тогда называется евклидовым простым числом относительно множества .
Набор «начальных» простых чисел
Для заданного числа построим множество такое, что произведение всех евклидовых простых чисел относительно этого множества будет больше . Выберем наименьшее возможное .
Элементы из этого множества назовем набором «начальных» простых чисел.
Indq(x)
Введем некоторое число . Пусть — его первообразный корень. Тогда должно выполняться следующее условие:
,
где .
Замечание: В качестве выбираем наименьшее неотрицательное число.
Сумма Якоби
Суммой Якоби называют сумму следующего вида:
,
где суммирование идет по всем наборам классов смежности для в , кроме тех, что равны .
Ключевые леммы
Основные леммы[2], используемые при доказательстве корректности алгоритма:
Пусть — идеалы в такие, что и пусть сопряженные простые идеалы, делящие соответственно. Пускай существует такое что
. Тогда для любого выполняется:
и следовательно
Идея алгоритма
Если является составным числом, то оно имеет некий делитель . Для проверки на простоту ищем это .
Если нам известны значения для каждой пары , то по китайской теореме об остатках мы можем найти . Каждая пара выбирается следующим образом: , а — простое евклидово число относительно такое, что
В алгоритме перебираются все возможные значения для всех , исходя из того, что известно только одно
Определим множество «начальных» простых чисел, являющиеся делителями . Назовем евклидовым простым числом, если простое и
2. Проверим — делится ли на любое «начальное» или евклидово простое число. Если делитель найдется, причем не равный , то объявляем составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень для каждого евклидового простого числа .
3. Для каждого «начального» простого числа найдем числа такие, что:
,
,
Для примем .
4. Для каждого «начального» и евклидового простых чисел, таких что зафиксируем простой идеал:
1. Для каждого «начального» простого числа найдем НОД в для и набора , где пробегает все значения евклидовых простых чисел, причем , а пробегает по всем значениям из Gal. Тогда либо выносим решение о том, что составное, либо строим надлежащий идеал в кольце , а также находим числа и , такие, что:
,
или некоторое из , где
2. Для каждого «начального» простого числа сделаем следующее: если для некоторого , тогда возьмем . В этом ключе построим числа для всех , и такие, что: