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