Гипо́теза Аграва́ла — теоретико-числовая гипотеза, высказанная Маниндрой Агравалом в 2002; образует основу для теста Агравала — Каяла — Саксены. Гипотеза Агравала утверждает:
Пусть и — два взаимно простых положительных целых числа. Если
,
то либо является простым, либо .
Следствия Если гипотеза Агравала верна, это уменьшит вычислительную сложность теста Агравала — Каяла — Саксены с до .
Верность или ложность гипотезы Гипотеза Агравала была проверена с помощью компьютера для и . Однако эвристический аргумент Карла Померанса и Хендрика Ленстры предполагает, что имеется бесконечно много контрпримеров. В частности, эвристические аргументы показывают, что такие контрпримеры имеют асимптотическую плотность, большую для любого .
Если гипотеза Агравала не верна согласно вышеприведённым аргументам, модифицированная версия гипотезы Поповича может остаться верной:
Пусть и — два взаимно простых положительных целых. Если
и
,
тогда либо простое, либо .
Примечания
Литература
Агравал