- Тест Агравала — Каяла — Саксены
-
Тест Агравала — Каяла — Саксены
В информатике тест Агравала—Каяла—Саксены (или тест AKS) — это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёными Маниндрой Агарвалом, Нираджем Каялом и Нитином Саксеной и впервые опубликованный 6 августа 2002 года в статье «PRIMES is in P».[1] До этой публикации принадлежность задачи распознавания простоты классу P являлась открытой проблемой. За своё открытие авторы получили премию Гёделя в 2006 году.
В 2005 году был предложен вариант алгоритма, который выполняется за (log6+ε(n)) операций, где n — тестируемое число.[2]
Примечания
- ↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena PRIMES is in P // Annals of Mathematics. — 2004. — Т. 160. — № 2. — С. 781–793.
- ↑ H. W. Lenstra, Jr. and Carl Pomerance, «Primality Testing with Gaussian Periods», preliminary version July 20, 2005.
Ссылки
- Л. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел
Wikimedia Foundation. 2010.
Тест Агравала — В информатике тест Агравала Каяла Саксены (или тест AKS) это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентами Нираджем Каялом (англ … Википедия
Тест Агравала-Каяла-Саксены — Тест простоты Агравала Каяла Саксены (или тест простоты AKS) это первый безусловный универсальный полиномиальный детерминированный тест простоты чисел, придуманный тремя индийскими учёными Маниндрой Агарвалом, Нираджем Каялом и Нитином Саксеной и … Википедия
Тест простоты — Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… … Википедия
Тест Ферма — Тест простоты Ферма в теории чисел это тест простоты натурального числа n, основанный на малой теореме Ферма. Содержание Если n простое число, то оно удовлетворяет сравнению для любого a, где n не делит a. Выполнение сравнения… … Википедия
Тест Миллера (теория чисел) — У этого термина существуют и другие значения, см. Тест Миллера. Не следует путать с «Тестом Миллера Рабина» вероятностным полиномиальным тестом простоты. Тест Миллера детерминированный полиномиальный тест простоты. В 1976 году Миллер… … Википедия
Вероятностный тест простоты — Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в… … Википедия
Тест простоты Люка — В теории чисел тест простоты Люка это тест простоты натурального числа n; для его работы необходимо знать разложение на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Простое число — Простое число это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы… … Википедия
Класс P — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отр … Википедия