Четвертая неделя...

Привет всем!

Недавно я сдавала реферат по Информационной безопасности и в этом посте хотела бы также рассказать об одном их используемых алгоритмов, а именно о методе Ферма для разложения на множители.

В 1643 году Пьер де Ферма предложил метод факторизации. Он заметил, что составное число всегда может быть представлено в виде разности двух квадратов и предложил, основанный на этом наблюдении, простой метод поиска делителей.

Пусть $n = a \cdot b$, где $a$ и $b$ натуральные, не обязательно простые, делители числа $n$ и $a>b$. Тогда $n=x^2-y^2$, где $x=\frac{a+b}{2}$, $y=\frac{a-b}{2}$.

Метод разложения на множители Ферма заключается в переборе всех возможных значений величины $x$ и проверке: является ли число $n-x^2$ полным квадратом. Если это условие выполнено, то делители a и b удовлетворяют равенствам $a=(x+y)$ и $b=(x-y)$.

Метод сводится к попытке найти два целых числа a и b, близких друг к другу $(a \approx b)$. Поиск начинается с наименьшего целого числа, большего, чем $x=\sqrt{n}$. Далее пробуем найти другое целое число $y$, такое, чтобы выполнялось уравнение $y^2=x^2-n$. В каждой итерации необходимо рассмотреть, является ли результат $x^2-n$ полным квадратом. Если такое значение для y находится, то вычисляются $a$ и $b$ и осуществляется выход из цикла. В противном случае проводится еще одна итерация.

Алгоритм.

Вход: Целое нечетное составное число $n>0$.

Выход: Натуральный делитель $a>1$ числа $n$.

1. Вычислить наименьшее целое число $h$ такое, что $h \geq \sqrt{n}$, то есть $h=\lceil \sqrt{n} \rceil$.
2. Если $h^2=n$, то определить $a=h$ и завершить алгоритм.
3. Определить $x \gets h, v=x^2-n$ и счетчик $k=0$.
4. Если величина $v$ является полным квадратом, то определить $y=\sqrt{v}, a=x+y$ и закончить алгоритм.
5. Вычислить $k \gets k+1, x \gets x+1$ и $v \gets x^2-n$. Вернуться к пункту 4.

Примечание: количество проверок числа $v$ (количество повторений на четвертом шаге алгоритма) не превосходит величины $y=\frac{a-b}{2}$.

Стоит отметить, что данный метод не обязательно находит разложение на простые числа (каноническое разложение), в таком случае алгоритм должен быть повторен рекурсивно для каждого из значений $a$ и $b$, пока не будут найдены сомножители в виде простых чисел.

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

Надеюсь вам была полезна эта информация. Желаю удачной недели!