Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?
Научные направления
Поделиться:
Статья опубликована в №79 (март) 2020
Разделы: Математика
Размещена 11.03.2020. Последняя правка: 28.04.2020.
Просмотров - 842

Применение алгоритма Гельфонда – Шенкса при факторизации натуральных чисел, состоящих из двух простых сомножителей (поиск единиц)

Усов Геннадий Григорьевич

к.т.н.

МГУ, 1972

пенсионер

Аннотация:
Изложенный в статье алгоритм факторизации натуральных чисел основан на совершенно новом направлении факторизации – на определении единиц при анализе формулы малой теоремы Ферма. В алгоритме задача дискретного логарифмирования при поиске единиц решается с помощью алгоритма Гельфонда-Шенкса. При этом в алгоритм Гельфонда-Шенкса к большому и малому шагам добавлен средний шаг.


Abstract:
The algorithm of factorization of natural numbers presented in the article is based on a completely new direction of factorization - the definition of units in the analysis of the formula of Fermat’s small theorem. In the algorithm, the discrete logarithm problem when searching for units is solved using the Gelfond-Shanks algorithm. At the same time, the middle step is added to the Gelfond-Shanks algorithm for large and small steps.


Ключевые слова:
факторизация натуральных чисел; малая теорема Ферма; алгоритм Гельфонда-Шенкса

Keywords:
factorization of natural numbers; Fermat's little theorem; Gelfond-Shanks algorithm


УДК 511

Введение

Задача разложения натуральных чисел на произведение простых сомножителей интересовала математиков с давних времен.

Существует много алгоритмов факторизации натуральных чисел, как простых, так и сложных.

Все простые алгоритмы факторизации натуральных чисел, имеющие разную скорость определения сомножителей этих чисел, можно разбить на две группы:

- алгоритмы, в которых для определения сомножителей применяется метод пробных делений;

- алгоритмы, в которых определяются квадраты двух натуральных чисел A и B, удовлетворяющих уравнению для натурального числа N [1]:

N = A^2 – B^2                                                                                          (1)

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

Цели и задачи

Задачей данной статьи является факторизация нечётных чисел N, имеющих два простых сомножителя x и y, отличных от 1 и от N, т е.

N = x * y                                                                                                   (2)

Как известно, большинство существующих алгоритмов факторизации натуральных чисел опираются на анализ получаемых значений формулы малой теоремы Ферма (МТФ):

P = a^(N-1) (mod N)   или   P = a^((N-1)/2) (mod N)                                 (3)

Оказалось, что можно найти информацию о сомножителях натуральных чисел из формулы (3), если анализировать порядок получения всех значений формулы МТФ для различных показателей степени, т.е. анализировать следующую последовательность чисел Pn с точки зрения порядкового номера этих чисел:

P(1) = 1,       P(i) = (P(i-1) * a) (mod N),        2<= i <= N                          (4)

Рассматривались разные основания степени для формулы МТФ, однако наиболее успешными при определении сомножителей получились результаты работы с основанием степени 2.

Для основания степени 2 значения последовательности чисел Pn (4) можно записать следующим образом:

P(1) = 1, P(i) = (P(i-1) * 2) (mod N),               2<= i <= N                        (5)

Всего в последовательности чисел Pn будет N чисел, т. е. её длина pn будет равна:

pn = N.

Эта последовательность начинается с числа 1 и заканчивается числом Pn = 2^(N-1) (mod N).

Последовательность чисел Pn можно разбить на несколько одинаковых последовательностей чисел Qn и на последовательность чисел Rn, которая состоит из начальных чисел последовательности чисел Qn.

Последовательность чисел Qn начинается с числа 1 и заканчивается числом (N + 1)/2. Длину этой последовательности определим как qn.

Последовательность чисел Rn начинается с числа 1 и заканчивается числом 2^(N-1) (mod N). Длину этой последовательности определим как rn.

Тогда получается уравнение:

N = a * qn + rn,                                                                                    (6)

где а – количество последовательностей чисел Qn в последовательности чисел Pn.

Есть некоторые последовательности натуральных чисел, для которых известны числа qn и rn. Это:

- числа Мерсенна Mn = (2^N – 1) (mod N),    qn = N,        rn = Mn (mod qn);

- числа Fn = (2^N + 1) (mod N),                      qn = 2 * N,    rn = Fn (mod qn).

 

Исследования показали, что имеет место формула соотношения суммы сомножителей x и y числа N, определенных в (2), и значений qn и rn при некотором натуральном числе b:

x + y = rn + b * qn,           где 0 <= b < a.                                           (7)

Для большинства чисел N, определенных в (2),  число b будет равно 0.

Если из формулы (7) определяется значение (x + y), то, используя формулу (1), можно определить согласно [1]:

A = (x + y) * 2,      B^2 = A^2 – N,      x – y = B / 2

Далее решаются два уравнения с двумя неизвестными: x и y.

Если В не является целочисленным корнем, то ищется другое значение b и другая комбинация значений qn и rn из уравнения (7).

Таким образом, если удаётся определить qn, rn и b, то задача факторизации числа N (2), у которого два сомножителя, может быть решена.

 

Поскольку все последовательности чисел Qn и последовательность чисел Rn «разделены» числом 1, то длины этих последовательностей можно определить, если будут определены порядковые номера чисел 1 в последовательности чисел Pn.

В дальнейшем будет применяться термин «единица».

Определение: единицей называется значение числа последовательности чисел Pn, равное 1 c порядковым номером К в этой последовательности.

Можно записать следующее свойство единицы из формулы (5):

если P(K) = 1 (mod N) для K > 1, то число N является делителем числа Мерсенна 2^K – 1.

При поиске единицы имеет место задача дискретного логарифмирования, которая заключается в следующем [2]:

для заданных целых чисел g и а определить натуральное число х из уравнения:

g^x = h (mod p)                                                                           (8)

В уравнение (8) подставляются h = 1 и g = 2, и получается уравнение дискретного логарифмирования для поиска единиц:

2^x = 1 (mod N)

Существует много алгоритмов для решения задачи дискретного логарифмирования.  

Автор статьи остановился на алгоритме Гельфонда – Шенкса, который представляет собой наиболее удобный алгоритм для понимания задачи дискретного логарифмирования. Данный алгоритм ещё называют методом согласования.

Алгоритм Гельфонда – Шенкса представляет собой изменение уравнения (8) с помощью уравнений [ 2]

x = i * m - j,    m = abs(sqrt(p)) + 1,  1 <= i <= m, 1<= j <= m     (9)

после чего получается из (8):

a^(i*m) = h * g^j (mod p)                                                             (10)

При этом сравниваются величины правой и левой части уравнения (10), и если эти величины совпадают при определённых значениях i и j, то можно определить величину x в формуле (9), зная полученные величины i и j.

Алгоритм Гельфонда – Шенкса можно отобразить на последовательность Pn, при этом получаются две сетки чисел: большая сетка чисел по i с большим шагом, равным m, и малая сетка чисел по j с малым шагом, равным 1. Каждая из этих сеток чисел будет длиной m.

При поиске единиц уравнения (9) и (10) выглядеть следующим образом:

x = i * m - j,    m = abs(sqrt(N)) + 1, 1 <= i <= m, 1<= j <= m     (11)

и:

2^(i*m) = 2^j (mod N),                                                                  (12)

Но в последовательности Pn несколько единиц, а нужно определить ту единицу, для которой выполняется уравнение (7).

Анализ чисел N с двумя сомножителями, которые имеют одинаковую длину по количеству десятичных знаков, показал, что К - порядковый номер единицы в последовательности Pn, для которой выполняется уравнение (7), будет удовлетворять следующему неравенству:

N – 2 * m  >  K >  N – 4 * m,        где m = abs(sqrt(N))                    (13)

Если сомножители числа N имеют различие по количеству десятичных знаков, то второе значение в (13) будет ещё меньше.

С учетом (13) уравнение (12) можно представить следующим образом:

2^(N – i * m) = 2^j (mod N)                                                            (14)

То есть, для определения единицы в случае, когда сомножители имеют одинаковое количество десятичных знаков,  достаточно иметь только 2 ячейки сетки по m.

Для того, чтобы определить положение единицы в последовательности чисел Pn, необходимо построить более мелкую (среднюю) сетку чисел, которая охватывает 2 ячейки большой сетки чисел (13).

Аналогично уравнениям (9) и (10) и с учётом уравнений (13) и (14) можно будет записать уравнения для средней и малой сеток чисел:

x = N – 2 * m - i * m1 - j, m1 = abs(sqrt(m))*2 + 1, 1 <= i <= m1,  1<= j <= m1    (15)

поэтому получаем:

2^( N – 2 * m - i * m1) = 2^j (mod N)                                               (16)

При выстраивании средней сетки определяются m1 чисел из последовательности Pn, с которыми будут сравниваться первые m1 чисел (малая сетка) из последовательности Pn.

При совпадении правой и левой части уравнения (16) число x определяется согласно (15).

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

Как известно, начало последовательностей Qn и Rn состоит из чисел степени 2:  1, 2, 4, 8, 16, 32, 64, и т.д., причем их количество зависит от величины числа N. Если количество бит в двоичном представлении числа N будет bn, то и количество степеней числа 2 в начале последовательностей Qn и Rn будет bn, а для последовательности Rn число bn не должно превышать rn.

Степени числа 2 отличаются от остальных чисел тем, что в их бинарном представлении есть только одна 1, причём – в самом начале представления.

Проверяя очередное число из средней сетки на количество бинарных единиц, можно определить совпадение этого числа с числом последовательности степеней числа 2. Единица в числах последовательности степеней числа 2 имеет расположение относительно начала числа, равное bn .

Следовательно, если при построении средней сетки с номером i будет найдено число из последовательности чисел степени 2, то положение единицы в последовательности чисел Pn определяется следующим уравнением:

K = N – 2 * m - i * m1 – bn +1

Таким образом, уже при построении средней сетки можно определить единицу, и тогда не нужно строить малую сетку.

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

Например, имеется простое число x = 199, а y – простое число и принимает значения от 3 до 500. При факторизации числа N = x * y с применением последовательности чисел степени 2 единица определяется с первого шага для чисел 109 <= y <= 317. Исключение составляет случай 199 * 199, но это решается с помощью проверки числа sqrt(N): является ли это число – целым числом.

Таким образом, с помощью первого обращения к алгоритму определения единиц определяются два простых сомножителей x и y числа N, расположенных достаточно близко друг к другу, а также для таких чисел N, у которых для сомножителей x и y выполняется условие:

2 * (N – 2 * m - i * m1) = (x + y) - a,     0 <=a < bn,     m1 = sqrt(m)*2+1

 

Если будет получен способ относительно быстрого определения значений qn и rn, то метод определения единиц может быть применён в криптоаналитике, где исследуются произведения двух больших простых чисел.

Например, в качестве дополнения, в Википедии есть информация о множестве «RSA – чисел»[2].

Это множество больших полупростых чисел, используемых в конкурсе RSA Factoring Chellenge. Конкурс заключался в нахождении простых множителей предложенных чисел с длиной от 100 до 2048 десятичных знаков. Часть чисел уже разгаданы и были показаны сомножители этих чисел.

Была составлена программа на Python для чисел x и y, которые известны как сомножители RSA – чисел, и оказалось, что если их сумма равна переменной xy:

xy = x + y,

а их произведение равно переменной N:

N = x * y,

то имеет место равенство:

2^(N – xy + 1) ( mod N) = 1.

 

Выводы.

На основании данной статьи была составлена программа на ПК.

Пример:  х = 97114202179933682930539 и y = 199111213487175732269363.

N = 19336526642885522428621175568741719114766776657

Программа нашла делители N на ПК менее, чем за  1 сек.

Научная новизна.

Изложенный в статье алгоритм факторизации натуральных чисел основан на совершенно новом направлении факторизации – на определении единиц при анализе формулы малой теоремы Ферма.

Данный алгоритм определён для чисел, которые имеют только два простых сомножителя.

Задача дискретного логарифмирования при поиске единиц решается с помощью алгоритма Гельфонда-Шенкса. При этом в алгоритм Гельфонда-Шенкса к большому и малому шагам добавлен средний шаг для определения средней сетки чисел.

Получена окрестность чисел средней сетки для определения единиц без применения малого шага.

Библиографический список:

1. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие / Ш.Т. Ишмухаметов.– Казань: Казан. ун. 2011.– 190 с.
2. Панкратова И.А. Теоретико-числовые методы в криптографии: Учебное пособие. — Томск: ТГУ, 2009. —120 с.
3. RSA – числа. URL: https://ru.wikipedia.org/wiki/RSA- %D1%87%D0%B8%D1%81%D0%BB%D0%B0 (дата обращения: 13.02.2020)




Рецензии:

24.04.2020, 23:28 Белых Сергей Анемподистович
Рецензия: Статья может быть рекомендована, но требует доработки. В конце статьи надо вставить ВЫВОД. В выводе привести пример числового расчета определения двух простых сомножителей. В тексте исправить условия задачи, примерно так, x и y - простые числа, N>x*y и следующее нечетное число за этим произведением. Ваша формула верна только при х=2,y>x, а при х>2,y>x надо добавить формулу 2^(N-xy+1) (modN) = 3. Статья может быть размещена после доработки.

25.04.2020 10:10 Ответ на рецензию автора Усов Геннадий Григорьевич:
Уважаемый Сергей Анемподистович! Благодарю Вас за рецензию к моей статье! Добавил выводы с примером поиска сомножителей. Вместе с тем прошу Вас уточнить замечания к статье: 1. У меня N = x*y, поэтому не может быть N>x*y. 2. х = 2 не может быть, так как я рассматриваю только нечётные числа. 3. Прошу указать какой-нибудь указатель для формулы, так как не могу понять: к какой формуле относится х=2. С уважением, Усов Геннадий Григорьевич



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

25.04.2020, 22:34 Белых Сергей Анемподистович
Отзыв: Принимаю Ваш ответ, согласен с Вами, но добавьте только одно слово в следующий текст в конце статьи " .. RSA – чисел: x и y, и оказалось, что если их сумма равна: ПЕРЕМЕННОЙ ху = х + у, ...". Это я и имел под словами "В тексте исправить условия задачи". х=2 относится уже не к Вашей формуле, а к моей.


26.04.2020, 10:06 Усов Геннадий Григорьевич
Отзыв: Уважаемый Сергей Анемподистович! Спасибо за замечание к статье! Концовку статьи уточнил. С уважением, Усов Геннадий Григорьевич


19.05.2020, 22:42 Мельник Сергей Иванович
Отзыв: Я не специалист в математических методах факторизации. Поэтому у меня вопрос общего плана: в чем преимущества вашего алгоритма по сравнению с существующими? Выводы к статье не выдерживают никакой критики. Во первых, это не выводы, а пример реализации. Во вторых, без указания на параметры используемого оборудования и сравнения с другими алгоритмами результат 1 секунда вообще ни о чем не говорит. Актуальность статьи вообще не аргументирована, так как не указан НИ ОДИН из недостатков существующих алгоритмов.


20.05.2020, 6:13 Усов Геннадий Григорьевич
Отзыв: Уважаемый Сергей Иванович! Часть ответа на Ваш вопрос уже есть в Вашем первом предложении. Как известно, существует много методов факторизации чисел, разных по сложности, по быстроте определения сомножителей. Автор не рассматривал недостатки этих методов, а просто предложил нескольно иной подход при построении нового метода - искать "единицы". Ведь никто не искал единицы? Правда? При этом высказана идея о дальнейшем развитии алгоритма Гельфонда-Шенкса: появляется средний шаг, и ищется не сама "единица", а окрестность этой "единицы". Всё это увеличивает скорость определения сомножителей. И будет ещё один метод факторизации. О его отличии от других методов сказано в разделе "научная новизна". А выводы - это результат работы над методом: составлена программа на домашнем компьютере. С уважением, Усов Геннадий Григорьевич.


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


 
 

Вверх