§ 3.5. Доказательство корректности алгоритма Ферма

Теперь мы должны доказать, что алгоритм Ферма выполняет свою задачу, и что он всегда завершает работу. При доказательстве удобно разделить случай составного и случай простого числа на входе. В первом случае мы должны показать,

что существует натуральное число такое что целое число. Это означает, что если составное, то алгоритм всегда находит делитель, меньший прежде, чем х становится равным А если простое, то мы должны проверить, что число не может оказаться целым при

Предположим, что можно представить в виде произведения где Мы хотим найти такие целые числа х и у, что Другими словами,

Поскольку разумно попытаться положить Решая эту систему уравнений относительно двух неизвестных, мы получаем

И действительно, простое вычисление показывает, что

Отметим, что должны быть целыми, а это значит, что оба числа должны быть четными. Именно поэтому мы и требуем, чтобы было нечетным; тогда каждое из чисел и будучи делителем также нечетно, а значит и и четные. Если число четное, то алгоритм может работать неправильно. Если, например, для нечетного к, то алгоритм никогда не завершит свою работу.

Если простое, то единственные возможные значения a и b — это Таким образом, и это наименьшее значение для которого число целое. Рассмотрим теперь, что происходит, если составное. Если то алгоритм находит делитель на шаге 1. Значит, мы можем предполагать, что составное и не является полным

квадратом. Другими словами, Мы утверждаем, что тогда алгоритм останавливается, так как

Начнем с доказательства неравенств.

Правое неравенство говорит, что Заменяя на и вычитая из обеих частей мы приходим к неравенству Однако поэтому обе части неравенства можно разделить на результате мы получаем Это рассуждение показывает, что неравенство эквивалентно неравенству а Поскольку по предположению, мы показали, что

Рассмотрим теперь левое неравенство. Отметим для начала, что поскольку нам достаточно доказать, что Ясно, что последнее неравенство выполняется тогда и только тогда, когда Однако формула (5.1) дает

и правая часть неотрицательна. Тем самым мы доказали неравенство эквивалентное исходному.

Вернемся к алгоритму. Напомним, что значение переменной х вначале равно затем оно увеличивается на 1 при каждом выполнении цикла. Поэтому из неравенства (5.2) вытекает, что если число составное, то алгоритм дойдет до раньше, чем до Однако при получаем

Таким образом, достигнув этого значения, алгоритм завершит работу, а его вывод будет состоять из множителей a и b. Поэтому если составное, то алгоритм всегда останавливается при некотором вычислив два делителя этого числа.

Заметим, что данное составное число можно представить в виде где возможно, несколькими различными способами. Какое из разложений находит алгоритм Ферма? Поиск начинается при увеличивается на каждом шаге. Значит, найденные алгоритмом делители о и b таковы, что разность

— наименьшая из возможных.

Алгоритм Ферма сообщает нам кое-что важное о системе шифрования RSA. Напомним, что безопасность системы RSA зависит от сложности разложения на множители числа являющегося произведением двух простых. Если нам удастся разложить то шифр будет взломан. Алгоритм деления методом проб мог бы создать иллюзию, что выбрав большие простые сомножители, мы могли бы добиться того, что сложно разложить. Однако это не так. Если множители большие, но их разность мала, то очень легко разложить на множители алгоритмом Ферма. Мы вернемся к этому вопросу в главе 12.