Статья опубликована в №79 (март) 2020
Разделы: Математика
Размещена 11.03.2020. Последняя правка: 28.04.2020.
Просмотров - 2333

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

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

к.т.н.

МГУ, 1972

пенсионер

УДК 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. Статья может быть размещена после доработки.

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

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

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

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

17.08.2021, 2:17 Цорин Борис Иосифович Отзыв: Проблема 1. Проверил на примерах утверждение "Исследования показали, что имеет место формула соотношения суммы сомножителей x и y числа N, определенных в (2), и значений qn и rn при некотором натуральном числе b: x + y = rn + b * qn, где 0 <= b < a". Пример 1: N=35=5*7, qn=12, rn=11, уравнение 5+7=11+b*12 не имеет целых корней. Пример 2: N=221=13*17, qn=24, rn=5, уравнение 13+17=5+b*24 не имеет целых корней. Возможно, автор потерял где-то единицу? Аналогично единица потеряна и в "Если P(K) = 1 (mod N) для K > 1, то число N является делителем числа Мерсенна 2^K – 1". Может быть, надо нумеровать числа согласно степеням, с нуля? Ну и "исследования показали" - это еще не доказательство. Проблема 2. В выражении "A = (x + y) * 2" напрашивается умножение заменить на деление. Ну тут, возможно, просто опечатка. Во многих формулах пропущены скобки. Проблема 3, основная: предлагаемый алгоритм не имеет практической применимости, так как используемый как его часть алгоритм Гельфонда-Шенкса имеет сложность O(sqrt(N)), что превышает сложность других алгоритмов факторизации (за исключением разве что p-1 алгоритма Полларда, который из-за своей сложности используется обычно для проверки наличия малых делителей, а к RSA-числам это неприменимо). Сложность полученного алгоритма почти достигает сложности алгоритма факторизации простым перебором делителей, но требует огромной используемой памяти. Предлагаемый же автором метод сокращения времени работы алгоритма за счет "средней сетки" - просто предложение подогнать построение алгоритма под заранее известный результат. Да, если мы знаем, что оба делителя не сильно отличаются от корня, перебор можно сократить. Но откуда бы нам это знать, если мы не специально подбирали такое число? Вывод: в отличие от других статей того же автора, эта не содержит грубых ошибок в рассуждениях, но содержит мелкие устранимые ошибки в формулах и недоказанное утверждение, а также не имеет практической применимости, так как предлагаемый алгоритм по времени ненамного эффективнее перебора, а по памяти намного неэффективнее, так что алгоритм может рассматриваться исключительно как математический анекдот.

17.08.2021, 3:22 Цорин Борис Иосифович Отзыв: Я решил, что сегодня я буду щедр, и подарю автору обоснование этого его "исследования показали" и т.д. В сущности, половину статьи можно заменить на это, а вторая половина - рассказ о методе Гельфонда-Шенкса и попытка его сократить, исходя из заранее известных результатов. Итак, обоснование. N=xy, где x и y - простые. Согласно малой теореме Ферма, 2^(x-1)=1(mod x). Возведем обе части в степень (y-1). 2^(N-x-y+1)= 1 (mod x), то есть 2^(N-x-y+1)-1 делится на x. Аналогично получаем 2^(N-x-y+1)-1 делится на y. Так как x и y простые, то число, деляшееся на x и на y, делится на их произведение. 2^(N-x-y+1)=1 (mod N). Всё, мы получили задачу дискретного логарифмирования, при решении которой найдем x+y. А вот сократить решение этой задачи дискретного логарифмирования без подгонки алгоритма под заранее известный ответ можно в лучшем случае до O(N^(1/3)*log(N)): сначала перебрать числа до N^(1/3) и убедиться, что среди них нет делителей N, а затем сказать, что x+y могут быть от примерно 2sqrt(N) до примерно N^(2/3), что дает O(N^(1/3)) операций и столько же памяти. Все, вся "статья" заменена на один абзац. И я сомневаюсь, что это какой-то новый результат: просто никому не приходило в голову публиковать настолько неэффективный алгоритм с настолько примитивным математическим обоснованием.

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