Вероятностный тест простоты

Вероятностный тест простоты

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

Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, тестирование простоты значительно легче факторизации заданного числа.

Тесты простоты

Ссылки





Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Вероятностный тест простоты" в других словарях:

  • Тест Соловея — Штрассена вероятностный тест простоты, открытый в 1970 х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью… …   Википедия

  • Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970 х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может… …   Википедия

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

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

  • Тест — (от слова англ. test)  «испытание», «проверка» это метод изучения глубинных процессов деятельности человека, посредством его высказываний или оценок факторов функционирования системы управления Содержание 1 Программирование 2 Математика …   Википедия

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

  • Вероятностный алгоритм — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

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

  • Детерминированный алгоритм — Детерминированный алгоритм  алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных. Содержание 1 Недетерминированный алгоритм 2 Использование …   Википедия


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

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