Метод факторизации Ферма онлайн

Метод Ферма − теория

Метод Ферма для разложения числа на множители основывается на следующем утверждении:

Утверждение 1. (метод факторизации Ферма). Пусть n>1 нечетное число¹) и пусть оно представлено в виде произведения двух натуральных множителей:

¹) В данной статье под словом число будем понимать натуральное (целое положительное) число.

Тогда n может быть представлен в виде разности квадратов двух чисел:

Обратно. Пусть n>1 нечетное число и пусть оно представляется в виде разности двух квадратов (2). Тогда n можно представить в виде произведения двух чисел.

Доказательство. Пусть n представлен в виде (1). Произведение ab можно представить в следующем виде:

Тогда

где

Пусть теперь n представлен в виде разности квадратов двух чисел, т.е. в виде (2). Тогда можно записать

где

Данное утверждение дает возможность разложить нечетное число на два множителя. Отметим, что множители могут быть как простыми, так и составными.

Для разложения числа n на множители (факторизации) методом Ферма, нужно вычислить квадратный корень от n: s₁=√n. Выбрать наименьшее натуральное число больше s₁:s=⌈s₁⌉=⌈√n⌉. Задать k=0,1,... и вычислить x=s+k, l=x²−n и выяснить, является ли число l полным квадратом какого-то натурального числа y. Если l²=y, то остановить процедуру. Получить множители числа n: a=x+y, b=x−y. Если l не является квадратом некторого натурального числа, то увеличить k на 1: k=k+1, вычислить x=s+k, l=x²−n и повторить процедуру.

Метод факторизации Ферма − алгоритм

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

1. Вычислить наименьшее целое число s такое, что s²≥ √n, т.е. s=⌈√n⌉.
2. Если s²=n, то a=s и завершить алгоритм.
3. Взять x=s, l=x²−n и счетчик шагов k=0.
4. Если l является полным квадратом, то вычислить y=√l , a=x+y и закончить алгоритм.
5. Вычислить k=k+1, x=x+1, l=x²−n. Перейти к пункту 4.

Другой делитель числа n равно b=n/a.

Покажем, что количество шагов алгоритма не превосходит величины

Имеем x=s+k. Тогда k=x−s. Учитывая, что a=x+y, получим k=x−s=a−y−s. Так как справедливо неравенство a>s>b, имеем

Следовательно

Отметим, что процедуру разложения можно оптимизировать. Вместо вычисления на каждом шаге квадрат x² в выражении l=x²−n, можно вычислить в начале процедуры x₀=s, , а на следующих шагах

Рассмотрим метод Ферма на конкретных примерах.

Метод факторизации Ферма − примеры и решения

Пример 1. Разложить число n=517 на множители.

Решение. Находим наименьшее целое число s такое, что , то есть . Далее задавая k=0,1,... вычисляем l=(s+k)²−n. Если на каком то шаге l является квадратом натурального числа, то процедуру останавливаем:

При k=6 получили l=324, который является квадратом числа 18. Останавливаем процедуру и вычисляем множители a=x+y=29+18=47 и b=x−y=29−18=11. Таким образом разложение числа 517 имеет следующий вид: 517=47·11.

Ответ. 517=47·11.

Пример 2. Разложить число n=43 на множители.

Решение. Находим наименьшее целое число s такое, что , то есть . Далее задавая k=0,1,... вычисляем l=(s+k)²−n. Если на каком то шаге l является квадратом натурального числа, то процедуру останавливаем:

При k=15 получили l=441, который является квадратом числа 21. Останавливаем процедуру и вычисляем множители a=x+y=22+21=43 и b=x-y=22-21=1. Таким образом разложение числа 43 имеет следующий вид: 43=43·1. Это значит, что число 43 является простым числом.

Ответ. Число 43 простое.

Отметим, что метод Ферма эффективно работает, когда множители близки к числу s=√n.

При проверке, является ли число l полным квадратом необходимо вычислить квадратный корень из большого целого числа. Мы могли бы использовать для этого алгоритм Нютона. Но это очень медленная операция. Поэтому для повышения производительности алгоритма мы рассмотрим алгоритм вычисления целозначного квадратного корня от натурального числа.

Алгоритм вычисления целозначного квадратного корня от натурального числа

• Вход: Натуральное число n>0
• Выход: Натуральное число q, удовлетворяющее неравенству q²≤n<(q+1)².

1. Взять x=n
2. Вычислить .
3. Если y<x, то положить x=y и перейти к шагу 2.
4. Положить q=x и завершить алгоритм.

Докажем, что приведенный алгоритм находит целое число q такое, что q²≤n<(q+1)², т.е. q=⌊√n⌋.

Пусть x, n>0. Из неравенства следует, что

или

Тогда . Отсюда следует:

или

Таким образом, на каждом шаге алгоритма x≥q (так как ). Третий шаг алгоритма показывает, что последваптельность значений x убывает. Покажем, что алгоритм остановится тольно при x=q.

Предположим, что это не так и что на некотором шаге y≥x алгоритм остановлен, но x≠q, т.е. x>q.

Вычислим

Так как x>q, то x²>q². Поскольку x целое число, то x²≥(q+1)². Но (q+1)²>n. Следовательно x²>n. Тогда из уравнения (6) следует, что y−x<0, что противоречит нашему начальному предположению y≥x.

Пример. Найти целозначный корень числа n=129.

Решение.

Присвоим x=n=129. Вычислим

Так как y<x, то присвоим x=65. Вычисляем:

Так как y<x, то присвоим x=33. Вычисляем:

y<x. Присвоим x=18. Вычисляем:

y<x. Присвоим x=11. Вычисляем:

y=x. Останавливаем алгоритм. x=11 целозначный корень от числа 129, квадрат которого не превосходит 129.

Ответ..