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

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

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

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

Общие тесты простоты

Специализированные тесты простоты

Литература


Формула


Есть более полная статья


 Просмотр этого шаблона Теоретико-числовые алгоритмы
Тесты простоты
Поиск простых чисел
Факторизация
Дискретное логарифмирование
Нахождение НОД
Арифметика по модулю
Умножение чисел


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


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

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

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

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

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

  • Тест Люка — Тест Люка  Лемера  эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самые большие простые числа всегда были числами Мерсенна даже задолго до появления компьютеров.[1] Содержание 1 История 2 Тест 3 …   Википедия

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

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

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

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

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


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

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