08.10.2018

Способ разложения целого числа на множители

Способ разложения целого числа на множители
Павлова Ирина Валентиновна
Лицей
учитель физики
Аннотация:
В статье приведен способ разложения целого числа на множители.

Abstract:
The article presents a method of decomposition of an integer into factors.

Ключевые слова:
целое число; множители; простое число

Keywords:
integer; multipliers; Prime

УДК 511
Введение. Натуральное число называется простым, если оно делится только на себя и на 1. Число, не являющееся простым, называется составным. В настоящее время существует множество способов разложения целых чисел на множители: метод факторизации Ферма, метод Лемана, метод квадратичного решета и другие. Эти методы являются  алгоритмами факторизации целых чисел. Факторизацией натурального числа называется его разложение в произведение простых множителей.
В настоящее время к методам факторизации целых чисел предъявляют требования: универсальность, полиномиальность, детерминированость и безусловеность. Универсальность метода означает, что он может использоваться для проверки простоты любых чисел. Полиномиальность означает, что наибольшее время работы алгоритма ограничено многочленом от количества цифр в проверяемом числе. Детерминизм гарантирует получение уникального предопределённого результата. Безусловность - свойство, заключающееся в том, то корректность алгоритма не зависит от каких-либо недоказанных гипотез.
Приведу сравнительный анализ своего метода (Тест) с четырьмя известными методами: методом факторизации Ферма, тестом Миллера - Рабина, тестом Агравала - Каяла -Саксены (тест AKS), тестом Люка-Лемера.
Требования    Метод  факторизации Ферма    Тест Миллера- Рабина    Тест Агравала- Каяла-Саксены (тест AKS)    Тест  Люка- Лемера    Тест
Детерминированость    Детерминированный    Вероятностный    Детерминированный      Детерминированный       Детерминированный
Полиномиальность    Полиномиальный    Полиномиальный    Полиномиальный    Полиномиальный    Полиномиальный
Универсальность    Универсальный    Универсальный    Универсальный    Работает только для чисел Мерсенна    Универсальный
Безусловеность    Безусловный    Тест дает лишь вероятностный ответ
    Безусловный    Безусловный    Безусловный
Практическое применение    Возможное применение для криптоанализа RSA    Используется в криптографии для получения больших случайных простых чисел    Алгоритм не применяется ввиду сложного исполнения    Лежит в основе проекта распределённых вычислений GIMPS    -
Актуальность. Существование алгоритма факторизации с полиномиальной сложностью является одной из важных открытых проблем современной теории чисел. Разложение числа на множители играет очень важную роль в безопасности некоторых криптосистем с открытым ключом.
Целью данной статья является представление простого алгоритма поиска множителей целого числа.
Пусть Х-число, которое надо разложить на два множителя. Один из множителей любого числа меньше квадратного корня из этого числа. Множители числа обозначим за L и S. Способ разложения числа на множители разобьём на этапы.
1 этап.
Извлечем квадратный корень из числа Х, отбросив всю дробную часть числа, приводя его к целочисленному виду
S  L=trunc (sqrt(X)).
Найдем разность между числом Х и целочисленным значением корня квадратного из Х
N=X- S  L.
Разность N  представим в виде целой части K и остатка J
K=N div S, J=N mod S.
Таким образом, число Х мы представили в виде Х= S  L+N= S  L+K+J (Рисунок 1).
До прямоугольника недостает значения D=S-J.
  
2 этап.
Сторону S каждый раз будем уменьшать на 1
S=S-1,
соответственно и D=D-1, а сторона L при этом будет увеличиваться (Рисунок 2.)

Тем самым мы будем достраивать фигуру на рисунке 1 до прямоугольника (Рисунок 3.)

R=L-D, C=R div S, y=R mod S, L=L+1+C, J=y, D=S-J.
Эти действия производим до тех пор, пока J не станет равным 0 (J=0). Максимальное количество шагов равно trunc (sqrt(X)).
Программный код в среде программирования PascalABC.Net
program mnoziteli;
var k,l,n,s,j,d,c,y,r,b:biginteger;
begin
var x:=ReadString('введите число:').ToBigInteger;
var a:=x div 2;
repeat
b:=a;
a:=(a+x div a)div 2
until a>=b;
s:=a;
n:=x-sqr(s);
k:=n div s; j:=n mod s; l:=s+k; d:= s-j;
repeat
s:=s-1;
d:=d-1;
r:=l-d;
c:=r div s;
y:=r mod s;
l:=l+1+c;
j:=y;
d:=s-j;
until j=0;
writeln('l=',l); writeln ('s=',s);
end.
Заключение. Практического применения своего метода не нахожу ввиду сложного исполнения. Может быть, реализация метода в других средах программирования покажет результат за меньшее число итераций.
Библиографический список
1. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие — Казань: Казанский университет, 2011. — 190 с.
2. Сайт ТГПУ им. Л. Н. Толстого [Электронный ресурс]. Режим доступа: URL: http://poivs.tsput.ru/ru/Math/NumberTheory (дата обращения: 06.06.2018).

http://sci-article.ru/stat.php?i=1527684634