.
Е.А.Абалина Проверка чисел на простоту с помощью метода Лукаса-Лемера Бакалаврская работа, 2012 г.
Е.A.Павлычева Проверка чисел на простоту с помощью метода Миллера - Рабина Бакалаврская работа, 2012 г.
(выпускница шк. №15 г.Иваново).
Научный руководитель С.И.Хашин
Проверка на простоту - важнейшая задача современной криптографии. Когда клиент отправляет в банк электронное платежное поручение, он ставит под ним свою электронную подпись. Для каждого документа подпись своя, не совпадает с подписями под другими документами. И при вычислении элктронной подписи, и при её проверке нельзя обойтись без простых чисел.
Простые числа - это те, которые не делятся ни на что, кроме 1 и самого себя. Это числа 2, 3, 5, 7 и так далее.
Ясно, что число 17 - простое. Почему? Да не делится оно ни на что.
А 101 ? Тоже простое. Оно не делится на 2, 3, 5, 7, 11. Стоп! А дальше проверять не будем. Если 101 делится на некоторое число p, обзначим частное через q, тогда 101=p*q. Не могут оба множителя, p и q быть больше 10. То есть, если бы у 101 были делители, то был бы делитель меньший 10.
То есть для проверки числа N на простоту, надо проверять его делимость на все простые числа,
меньшие .
А вот, например, в ГОСТ 34.10-2012 (стандарт на электронную подпись) разработчик системы должен найти простое число q, удовлетворяющее некоторым условиям и лежащее в пределах
В качестве примера, в ГОСТе предлагается число
А оно точно простое? Как проверить? Вы действительно собираетесь делить на все простые числа, вплоть до ...? Нет ли какого другого способа?
Конечно, есть. Например в языке Java имется класс BigInteger работающий с целыми числами произвольной длины. И у этого класса есть метод isProbablePrime, проверяющий будет ли число простым. Probable - значит "вероятно", то есть Java не дает 100% гарантии, что число простое. На самом деле, полного решения у этой задачи до сих пор нет. Поэтому и приходится довольствоваться ответом типа "число q скорее всего, простое". Хотя вероятность ошибки так мала, что ею можно спокойно пренебречь.
Как же язык Java проверяет числа на простоту? Для этого используется комбинация двух методов: метод Миллера-Рабина и метод Лукаса-Лемера.
Изучению особенностей реализации этих двух методов в языке Java и посвящены эти две работы.
