Тест Агравала — Каяла — Саксены

Тест Агравала — Каяла — Саксены

Тест Агравала — Каяла — Саксены

В информатике тест Агравала—Каяла—Саксены (или тест AKS) — это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёными Маниндрой Агарвалом, Нираджем Каялом и Нитином Саксеной и впервые опубликованный 6 августа 2002 года в статье «PRIMES is in P».[1] До этой публикации принадлежность задачи распознавания простоты классу P являлась открытой проблемой. За своё открытие авторы получили премию Гёделя в 2006 году.

В 2005 году был предложен вариант алгоритма, который выполняется за \mathcal{O}(log6+ε(n)) операций, где n — тестируемое число.[2]

Примечания

  1. ↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena PRIMES is in P // Annals of Mathematics. — 2004. — Т. 160. — № 2. — С. 781–793.
  2. ↑ H. W. Lenstra, Jr. and Carl Pomerance, «Primality Testing with Gaussian Periods», preliminary version July 20, 2005.

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Тест Агравала — Каяла — Саксены" в других словарях:

  • Тест Агравала — В информатике тест Агравала  Каяла  Саксены (или тест AKS)  это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентами Нираджем Каялом (англ …   Википедия

  • Тест Агравала-Каяла-Саксены — Тест простоты Агравала Каяла Саксены (или тест простоты AKS) это первый безусловный универсальный полиномиальный детерминированный тест простоты чисел, придуманный тремя индийскими учёными Маниндрой Агарвалом, Нираджем Каялом и Нитином Саксеной и …   Википедия

  • Тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… …   Википедия

  • Тест Ферма — Тест простоты Ферма в теории чисел  это тест простоты натурального числа n, основанный на малой теореме Ферма. Содержание Если n  простое число, то оно удовлетворяет сравнению для любого a, где n не делит a. Выполнение сравнения… …   Википедия

  • Тест Миллера (теория чисел) — У этого термина существуют и другие значения, см. Тест Миллера. Не следует путать с «Тестом Миллера Рабина»  вероятностным полиномиальным тестом простоты. Тест Миллера  детерминированный полиномиальный тест простоты. В 1976 году Миллер… …   Википедия

  • Вероятностный тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в… …   Википедия

  • Тест простоты Люка — В теории чисел тест простоты Люка это тест простоты натурального числа n; для его работы необходимо знать разложение на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Простое число — Простое число  это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы… …   Википедия

  • Класс P — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отр …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»