Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?

Научные направления

Поделиться:
Разделы: Информационные технологии
Размещена 07.06.2018. Последняя правка: 07.06.2018.
Просмотров - 2136

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

Павлова Ирина Валентиновна

-

Лицей

учитель физики

Аннотация:
В статье приведен способ разложения целого числа на множители.


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).




Рецензии:

7.06.2018, 13:07 Мирмович Эдуард Григорьевич
Рецензия: Уважаемая Ирина Валентиновна! Ваша статья сырая. Примеры "сырости". "Целью данной СТАТЬЯ является представление простого алгоритма поиска множителей целого числа". "Практического применения своего метода не нахожу ввиду сложного исполнения". Как совместить эти фразы из статьи? Формулы не оцифрованы и нет возможности ссылок на них ни Вам, ни рецензенту. Что означает формула: Х=trunc(sqrt(X))? Надо объяснить рядовому читателю смысл слова, символов или оператора "trunc". "Найдем разность между числом Х и корнем квадратным из Х: N=X-S*L". Что это? Может, N=X–sqrt(S*L)? Причём, в программном разделе квадратный корень из произведения записан верно. В тексте Вы пользуетесь некоторыми обозначениями из программы: поди-знай, что понимает автор под символикой div или другими обозначениями. Ну и в принципе. Определить наличие сомножителей у нечётного числа (даже двух, не говоря уже о большем числе) – сама по себе не тривиальная проблема. Будут ли они простыми, кратными или даже повторяющимися (тогда внутри корня появляются квадраты) – это отдельная задача, составная в тематике поиска простых чисел. А вообще-то, приведение текстов "инструкций" (программ) на любых языках - хоть Pascal, хоть Ci+ или даж Бейсик в научных статьях не приветствуется. И Вы знаете, почему. Ну и описки типа "безусловеность". Рецензент воздержится от рекомендации данной статьи к опубликованию в данном журнале. Подождите другого рецензента, может он опровергнет высказанные здесь сомнения. С уважением.

07.06.2018 23:23 Ответ на рецензию автора Павлова Ирина Валентиновна:
Уважаемый Эдуард Григорьевич, спасибо за рецензию!

7.06.2018, 17:26 Поплавская Лидия Андреевна
Рецензия: Полностью согласна с рецензентом Мирмович Э.Г. Нет ни научной новизны, ни логики изложения. Путаница в обозначениях (см. этап 1). Считаю, что статья не подлежит публикации в данном журнале.
07.06.2018 23:23 Ответ на рецензию автора Павлова Ирина Валентиновна:
Уважаемая Лидия Андреевна, спасибо за рецензию!



Комментарии пользователей:

Оставить комментарий


 
 

Вверх