О методе факторизации чисел Мерсенна

Размещено на http://www.allbest.ru/

О методе факторизации чисел Мерсенна

В.И. Гончаров

В данной статье описан метод факторизации чисел Мерсенна Mp= 2p - 1 (где индекс p - нечетное простое число), разработанный на основе утверждения о делителях числа Mp: все простые делители числа Mp имеют вид 2p·k + 1. В статье использованы следующие условные обозначения: N - натуральный ряд; N0 = N ? 0 - расширенный натуральный ряд; P - множество простых чисел. В статье использованы ссылки на следующие определения, леммы и теоремы теории чисел.

Определение 1. Пусть a и b (b ? 0) - целые числа. Число b называется делителем a, если существует целое число q, такое, что a = b·q. В этом случае a называется кратным b; а q - частным от деления a на b. Соотношение “b делитель a” мы будем записывать для краткости в виде b | a [2, 19].

Определение 2. Целое число p называют простым, если p ? 0, p ? 1 и единственными его делителями являются числа 1, p [1, 16].

Определение 3. Целое число p называют составным, если p ? 0, p ? 1 и не является простым [1, 16].

Определение 4. Простым числом Софи Жермен называется такое простое число p, для которого 2p + 1 также является простым.

Определение 5. Нечетные простые числа имеют вид 4n + 1 или 4n + 3 [4, 14].

Определение 6. Каждое натуральное число a имеет тривиальные делители: единицу и само число [3, 9]. Лемма 1. Каждое натуральное число a ? 1 обладает, по меньшей мере, одним простым делителем p (т. е. простым числом p с p | a), и, в частности, наименьший натуральный делитель p ?1 числа a является простым [3, 10].

Теорема 1. (Дирихле). В каждой арифметической прогрессии r + k·m (r - целое число, m - натуральное число, k = 0, 1, 2, …), у которой первый член r взаимно прост с разностью m, содержится бесконечно много простых чисел [3, 189].

Теорема 2 (Метод Ферма). Пусть p ? 2 - простое число и q - простой делитель числа Мерсенна Mp. Тогда найдется такое натуральное число r, что q = 1 + 2r·p [1, 77]. Теорема 3. Если дано целое число a и натуральное число m, то существует одна и только одна пара целых чисел q, r, таких, что a = q·m + r с 0 ? r < m; q - называется частным, r - остатком от деления a на m [3, 30].

Дополнение. m | a тогда и только тогда, когда при делении с остатком числа a на m получается остаток r = 0 [3, 30]. Теорема 4. (Ейлер) Если числа p = 4n + 3 и q = 2p +1 = 8k + 7 - оба простые, то Mp ? 0(mod q) [4, 46]. Для исследования каждому фиксированному числу Mp сопоставим множество Bp = {a| a ? N ? a = 2p·n + 1, n = 0, 1, 2, 3, …}. Множество Bp может быть взаимно однозначно отображено на множество N. По определению множество Bp, равномощное множеству N, называется счетным. В дальнейшем для элемента bm множества Bp с индексом m будет использовано обозначение bm = 2p·m + 1, m ? N0. Заметим, что элементы множества Bp образуют арифметическую прогрессию 1+ 2p·0, 1+ 2p·1, 1+ 2p·2, 1+ 2p·3, … Согласно теореме 1 множество Bp содержит бесконечное множество простых чисел. Лемма 2. Приведем определение и законы алгебраической операции умножения на множестве Bp. Элемент b0 множества Bp содержит единицу b0 = 2p·0 + 1 = 1, где 0 - индекс элемента множества. Единица не есть произведение каких-либо элементов множества Bp, отличных от элемента b0 . Для произведения любых элементов bk и bm множества Bp существует и только один элемент bn множества Bp с условием, что bk· bm = bn, k ? N0, m ? N0, n ? N0.

Определим значение индекса n элемента

bn (2p·k + 1)(2p·m + 1) = 2p·n + 1;

4p2k·m + 2p·k + 2p·m + 1 = 2p·n + 1; 2p(2p·k·m + k + m) = 2p·n;

2p·k·m + k + m = n, k ? N0, m ? N0, n ? N0. (1)

факторизация число мерсенн

Равенство (1) устанавливает зависимость значения индекса n элемента, который содержит произведение, от значений индексов k и m элементов, содержавших множители. Каково бы ни были элементы bk и bm множества Bp для операции умножения этих элементов задан коммутативный закон bk· bm = bm· bk. Каково бы ни были элементы bk, bm и bn множества Bp для операции умножения этих элементов задан ассоциативный закон (bk· bm ) bn = bk (bm· bn). В частности, справедливы равенства b0 = b0· b0; bk = b0· bk; bk = bk· b0, где k - индекс произвольно выбранного элемента множества Bp. Лемма 3. Приведем определение и законы алгебраической операции деления на множестве Bp. Элемент b0 множества Bp содержит единицу b0 = 2p·0 + 1 = 1, где 0 - индекс элемента множества. Единица не есть произведение каких-либо элементов множества Bp, отличных от элемента b0 . Приведем определение делимости на множестве Bp на основе определения 1: элемент bk множества Bp называется делителем элемента bn (делимого) множества Bp , если

bn = bk· bm, m ? N0, n ? N0, k ? N0. (2)

При этом следует подчеркнуть, что элемент bm (частное), входящий в последнее соотношение, принадлежит множеству Bp. Определим значение индекса m элемента

bm 2p·n + 1= (2p·k + 1) (2p·m + 1);

2p·n + 1= 4p2k·m + 2p·k + 2p·m + 1;

2p·n = 2p (2p·k·m + k + m);

n = 2p·k·m + k + m; n - k = (2p·k + 1) m;

m = (n - k) / (2p·k + 1), m ? N0, n ? N0, k ? N0. (3)

Равенство (3) устанавливает зависимость значения индекса m элемента bm, который содержит частное, от значения индекса n элемента bn, содержащего делимое, и значения индекса k элемента bk, содержащего делитель. При этом если m не принадлежит множеству N0, то операция деления не имеет смысла, и значение индекса m не определено. Исходя из соотношения делимости (2), приведем следующие свойства операции деления на множестве Bp. bn | bn для каждого bn ? Bp; b0 | bn для каждого bn ? Bp; bn | b0 только для каждого bn = b0; из bk | bn, bn | bm следует bk | bm; из bk | bn следует bmbk | bmbn для каждого bm ? Bp; из bmbk | bmbn, где bm ? Bp, следует bk | bn; из bk | bn, bm | bt следует bk bm | bn bt; из bk | bn следует bk | bmbn для каждого bm ? Bp. Эти свойства следуют из определения делимости.

Доказательство их здесь не приводится. В теореме 2 доказано, что простой делитель числа Мерсенна Mp, где простое число p ? 2, имеет вид 1 + 2p·r. Основываясь на свойства операции умножения на множестве Bp теорему 2 можно привести в следующей формулировке. Теорема 5. Натуральные делители числа Мерсенна Mp, где простое число p ? 2, принадлежат множеству Bp. Доказательство. В общем случае в составе натуральных делителей числа Mp различают: - тривиальные делители; - простые делители; - составные делители. По определению 6 число Мерсенна Mp как натуральное число имеет два тривиальных делителя: единицу и само число. Единица как тривиальный делитель Mp безусловно принадлежит множеству Bp: элемент b0 множества содержит 1. Само число как тривиальный В общем случае делитель Mp может быть простым или составным. Если число Мерсенна Mp простое, то по теореме 2 оно имеет вид 1 + 2p·n, где n ? N0.

Определим значение индекса n элемента bn множества Bp, содержащего число

Mp bn = Mp = 1 + 2p·n; n = (Mp - 1) / 2p. (4)

Если число Мерсенна Mp составное, то оно может быть представлено как произведение простых делителей и по лемме 2 имеет вид 1 + 2p·n, где n ? N0. Предположим, что элемент bn множества Bp содержит число Mp. Тогда значение индекса n элемента bn определяется по формуле (4). Если делитель числа Мерсенна Mp простой, то по теореме 2 он имеет вид 1 + 2p·n, где n ? N0. В этом случае n рассматривается как индекс элемента bn множества Bp, содержащего простой делитель. Тогда значение индекса n элемента bn определяется по формуле n = (bn - 1) / 2p. Если делитель числа Мерсенна Mp составной, то он может быть представлен как произведение простых делителей и по лемме 2 имеет вид 1 + 2p·k, где k ? N0. В этом случае k рассматривается как индекс элемента bk множества Bp, содержащего составной делитель. Тогда значение индекса k определяется по формуле k = (bk - 1) / 2p. Теорема доказана. Метод факторизации числа Мерсенна Mp Для исследования зафиксируем число Мерсенна Mp.

Согласно теореме 5 вычислим значение индекса n элемента bn множества Bp, содержащего число Мерсенна Mp n = (Mp - 1) / 2p, n ? N0 и составим диофантово уравнение с двумя целочисленными неизвестными k и m

n = 2p·k·m + k + m, k ? N0, m ? N0, (5)

где k - индекс элемента bk множества Bp, содержащего делитель числа Мерсенна; m - индекс элемента bm множества Bp, содержащего частное от деления числа Мерсенна на делитель. Решением уравнения (5) называется кортеж <k, m ?, удовлетворяющий этому уравнению. Уравнение (5) может не иметь решений, если число Мерсенна простое, либо иметь несколько решений в зависимости от числа простых делителей числа Мерсенна. Для нахождения решения численным методом уравнения (5) преобразуем его к виду

m = (n - k) / (2p·k + 1), k ? N0, m ? N0. (6)

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

Результативность решения задачи обусловлена тем, что число Мерсенна как натуральное число по лемме 1 обладает наименьшим простым делителем. В основу алгоритма положен итерационный процесс последовательного вычисления неполного частного m при изменении k на каждом шаге процесса на 1, начиная с начального значения, равного 1. Для вычисления неполного частного используется операция деления с остатком. Выход из бесконечного итерационного процесса выполняется в двух независимых случаях. Если на каком-то шаге процесса остаток при вычислении неполного частного равен 0, то процесс прерывается и делается вывод: число Мерсенна составное. Значение делителя bk вычисляется по формуле bk = 2p·k + 1. Значение частного bm вычисляется по формуле bm = 2p·m + 1. Если при вычислении неполного частного m остаток не равен 0 при изменении k от 1 до k ? m, то процесс прерывается и делается вывод: число Мерсенна простое. Переход к следующему этапу факторизации выполняется в том случае, если на предыдущем этапе факторизации найден очередной простой делитель числа Мерсенна.

Тогда для исследования используется частное m, полученное на предыдущем этапе факторизации. Начальное значение делителя k в новом итерационном процессе принимается равным делителю предыдущего этапа факторизации. Если при вычислении неполного частного m остаток не равен 0 при изменении делителя до k ? m, то итерационный процесс прерывается и делается вывод: исследуемое частное является последним простым делителем числа Мерсенна. В этом случае процесс факторизации числа Мерсенна считается законченным. Уточним формулировку теоремы 4.

Для этого выполним формализацию определения простого числа Софи Жермен, введя множество простых чисел Софи Жермен Z = {p| p ? P ? 2p + 1 ? P}. В статье [5] приведены результаты исследований числовых характеристик и свойств простых чисел p ? Z; решена задача о распределении простых чисел p ? Z в натуральном ряду; даны обоснование и формулировка теоремы, утверждающей, что простые числа p ? Z составляют бесконечное множество. Для справки приведем следующие данные о простых числах Мерсенна Mp: в списке 51765911 простых чисел содержится 3365405 простых чисел Софи Жермен, в том числе: 1683816 простых чисел вида 4n + 3 и 1681589 простых чисел вида 4n + 1. Приведем списки: первых 10 простых чисел Софи Жермен вида 4n + 3: 3, 11, 23, 83, 131, 179, 191, 239, 251, 359; 6 простых чисел Софи Жермен вида 4n + 3 в конце списка, содержащего 1683816 простых чисел: 1019034539, 1019035211, 1019035499, 1019035679, 1019035943, 1019036303. Используя определение 4, приведем другую формулировку теоремы 4, основанную на понятии множества простых чисел Софи Жермен Z = {p| p ? P ? 2p + 1 ? P}. Теорема 6. Если индекс p числа Мерсенна Mp принадлежит множеству Z и имеет вид 4n + 3, то число Мерсенна составное. Наименьший простой делитель этого числа Мерсенна имеет вид 2p + 1. Доказательство теоремы приведено в [4, 46]. Примеры:

23|M11

47|M23

167|M83

263|M131

359|M179

383|M191

479|M239

503|M251

2038069079|M1019034539

2038070423|M1019035211

2038070999|M1019035499

238071359|M1019035679

2038071887|M1019035943

2038072607|M1019036303.

На основании свойства множества простых чисел Софи Жермен можно сделать вывод: числа Мерсенн Mp, где p ? Z ? p = 4n + 3, составляют бесконечное множество. Теорема 7. Числа Мерсенна Mp, где p - нечетное простое число, свободны от квадратов. Доказательство. Для доказательства произвольно выберем число Мерсенна

Mp = 2p·n + 1, где n = (Mp - 1)/2p

Если число Мерсенна Mp простое, то по определению простого числа оно свободно от квадратов. Если число Мерсенна Mp имеет в каноническом разложении только два простых делителя, то оно свободно от квадратов. Предположим, что каноническое разложение числа Мерсенна содержит квадрат простого делителя

bk Mp = bk·bk = (2p·k + 1) (2p·k + 1) = 4p2k2 + 2p·k + 2p·k + 1 = 4p2k2 + 4p·k + 1; 2p·n + 1 = 4p2k2 + 4p·k + 1; 2p·n = 4p2k2 + 4p·k; n = 2p·k2 + 2k; 2p·k2 + 2k - n = 0, (7)

где n - индекс элемента bn множества Bp, содержащего число Mp; k - индекс элемента bk множества Bp, содержащего предполагаемый простой делитель числа Mp. Решение квадратного уравнения (7) имеет вид

Подкоренное выражение представляет собой число Мерсенна Mp. Корень квадратный из числа Мерсенна не выражается целым числом. Решение квадратного уравнения не имеет смысла. Предположение, что число Мерсенна Mp содержит квадрат простого делителя, привело нас к противоречию. Следовательно, выбранное число Мерсенна Mp свободно от квадратов. Если число Мерсенна Mp имеет в каноническом разложении только три делителя, то оно свободно от квадратов. В общем случае такое число Mp представляет собой произведение трех делителей, из которых два делителя можно всегда выбрать простыми числами, а третий делитель будет либо простым числом, либо составным числом в зависимости от общего числа простых делителей числа Mp. Предположим, что число Мерсенна представимо в виде выражения

Mp = bk·bk·bm = (2p·k + 1)(2p·k + 1)(2p·m + 1) = (4p2k2 + 4p·k + 1)(2p·m + 1) = 8p3k2m + 4p2k2 + 8p2k·m + 4p·k + 2p·m + 1; 2p·n + 1 = 8p3k2m + 4p2k2 + 8p2k·m + 4p·k + 2p·m + 1; 2p·n = 8p3k2m + 4p2k2 + 8p2k·m + 4p·k + 2p·m; 2p·n = 2p (4p2k2·m + 2pk2 + 4p·k·m + 2k + m); n = 4p2k2·m + 2pk2 + 4p·k·m + 2k + m; (8)

Диофантово уравнение (8) содержит два целочисленных неизвестных k и m. Для решения методом итераций выполним тождественное преобразование уравнения (8) к виду m = (n - 2p·k2 - 2k) / (4p2k2 + 4p·k +1), m ? N0, n ? N0, k ? N0, где n - индекс элемента bn множества Bp, содержащего число Mp; k - индекс элемента bk множества Bp, содержащего простой делитель числа Mp. Предполагается, что число Mp содержит квадрат этого делителя; m - индекс элемента bm множества Bp, содержащего делитель числа Mp (простой или составной). Если в результате выполнения итерационного процесса будет установлено, что уравнение не имеет решения, то выбранное число Мерсенна Mp свободно от квадратов.

Литература

1. И.Н. Попов. Совершенные и дружественные числа. Учебное пособие. - Архангельск: Поморский государственный университет имени М.В. Ломоносова, 2005. -С. 153

2. А.А. Бухштаб. Теория чисел. - М.: Просвещение, 1966. -С. 384

3. Г. Хассе. Лекции по теории чисел. - М.: Издательство иностранной литературы, 1953. -С. 528

4. Эрнст Трост. Простые числа. - М.: Государственное издательство физико-математической литературы, 1959. -С. 136

5. http://new-idea.kulichki.net/ О распределении простых чисел p, удовлетворяющих условию p' = 2p + 1, в натуральном ряду

Размещено на Allbest.ru