Как стать автором
Обновить

Алгоритм Соловея-Штрассена

Алгоритмы *
Из песочницы

Тест Соловея–Штрассена


Роберт Соловей и Фолькер Штрассен разработали алгоритм вероятностного тестирования простоты числа, который использует символ Якоби. Определяет числа как составные или вероятно простые. Распознает числа Кармайкла как составные.
Читать дальше →
Всего голосов 17: ↑8 и ↓9 -1
Просмотры 19K
Комментарии 3

Факторизация чисел и сумма неизвестных делителей. Часть IV

Информационная безопасность *Криптография *Алгоритмы *Математика *Научно-популярное



Возможность единственного представления составного нечетного натурального числа (СННЧ) N в виде произведения степеней простых (кроме 2) чисел составляет существо основной теоремы арифметики (ОТА). Для больших чисел, содержащих в своей записи $10^2 -10^3$ и более цифр, эта возможность, а точнее задача не получила приемлемого для практики (за обозримое время) решения до наших дней. Кратко эту задачу называют задачей факторизации больших чисел(ЗФБЧ). Ее формулировка проста и известна уже несколько тысячелетий: для заданного натурального числа N = pq найти все его нетривиальные делители.
Читать дальше →
Всего голосов 6: ↑5 и ↓1 +4
Просмотры 3.6K
Комментарии 5