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

Представление (p – 1) – метода Полларда факторизации натуральных чисел на основании множества вычетов

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

к.т.н.

МГУ, 1972

пенсионер

УДК 511

Введение

(Р – 1) – метод Полларда, который применяется при факторизации натуральных чисел, заключается в следующем [1][3]:

пусть n - факторизуемое число, и необходимо определить его простой делитель р,   1 < p < n.

Число (р – 1) можно разложить на простые сомножители:

     (p – 1) = q1^r1 * q2^r2 * q3^r3 *…. * qt^rt .                       (1)

Идея (p – 1) – метода Полларда состоит в том, чтобы собрать в виде произведения М как можно большего числа степеней простых сомножителей dj^rj различных чисел (d – 1), где d – простое число, так, чтобы М делилось на каждый сомножитель qi^ri, входящий в разложение (1), а именно:

     M = M(B1) = d1^r1 * d2^r2 *  d3^r3 * … *  dk^rk.           (2)

Тогда искомый делитель p определяется по следующей формуле:

     p = н.о.д. (n, a^M - 1)                                                             (3)

У метода есть две стадии.

На первой стадии (p- 1) – метода Полларда [2] определяется граница B1, которая ограничивает величину сомножителей:

     qi^ri <  B1.

При большом значении B1 число M(B1) может оказаться чрезвычайно большим (сравнимо с B1!). Поэтому лучше разбить полное произведение M(B1) на k блоков, состоящих из примерно одинакового числа сомножителей. Далее вычисляется число Mi как произведение простых чисел блока i, где 1 <= i <= k.

После этого определяется:

     M(B1) = M1 * M2 * ... * Mk,                                                 (4)

и  вычисляется a^M(B1) как предел последовательности { ai }, где a1 = a^M1 (mod n), а последующие ai вычисляются по формуле:

     a(i+1) = ai^M(i+1)  mod n, 1 <= i < k.                                    (5)    

В статье рассматриваются несколько задач, необходимых для представления (р – 1) – метода Полларда на основании множества вычетов.

Актуальность

В настоящее время (p – 1) – метод Полларда не является распространённым при факторизации больших чисел.

В основном этот метод применяется для определения малых (гладких) делителей числа n в криптографии [6].

Поэтому дальнейшее развитие (p – 1) – метода Полларда позволит быстрее проводить в криптографии анализ простых чисел с точки зрения того, чтобы ответить на вопрос: является ли проверяемое число сильным простым числом.

В существующих публикациях (p – 1) – метод Полларда показан практически в одном и том же виде. При этом не определены основные параметры метода:

- граница В1;

- степени сомножителей;

- соотношение сомножителей произведения М и делителей числа n (а не наоборот).

И самое главное, в публикациях (p – 1) – метода Полларда не рассматривается:

- определение числа p при наличии в произведении M не всех сомножителей числа (p – 1);

- наличие в произведении M всех сомножителей чисел (p – 1) и (q – 1), где p и q – делители числа n.

Кроме того, метод рассматривает только выражение (a^M – 1), а не рассматривает другие выражения, например, (a^M – 2).

Решение данных вопросов в рамках (p – 1) – метода Полларда позволит несколько упростить поиск малых делителей.

Цели и задачи

Целью данной работы является решение нескольких задач по определению основных параметров (p – 1) – метод Полларда.

Задача 1. Выбор сомножителей числа М с помощью множества вычетов.

Поскольку в методе основной упор делается на выражение (a^M – 1), которое определяет наличие делителей, то появляется необходимость рассмотреть все числа (a^M – 1), делители которых являются делителями числа n.

Допустим, что имеется нечётное число n = x * y, где x и y – простые числа, и а = 2. Полученные в дальнейшем выводы статьи будут справедливы для любого количества простых сомножителей и для других оснований степени a.

Если рассматривать значения m в интервале 0 <= m < n, то по формуле:

     2^m (mod n),                                                                         (6)

получается множество вычетов Zn по mod n, которое содержит n элементов (вычетов), где n - порядок множества Zn.

Если рассматривать значения m в интервале 0 <= m < М по формуле (6), то получается расширенное множество вычетов ZMn по mod n, которое содержит M элементов (вычетов), где M - порядок множества ZMn.

Множество Zn включает в себя несколько одинаковых групп вычетов Un, порядок которых определим как un, при этом:

     2^un = 1 mod n.

Кроме того, множество Zn включает в себя ещё множество вычетов U1n, которое состоит из начальных элементов группы вычетов Un. Порядок множества U1n обозначим как s, который можно определить:

     s = n mod un.

Тогда количество групп Un во множестве Zn будет равно w = (n – s) / un.

Такие же множества вычетов можно определить для любых натуральных чисел. Для простых чисел s = 1.

В статье будут рассматриваться как порядковые номера вычетов во множестве вычетов Zn и в расширенном множестве вычетов ZMn, так и значения этих вычетов. Кроме того, будут рассматриваться вычеты в группе Un и величина un.

 

Если анализировать вычеты множества Zn, то оказывается, что во множестве Zn есть несколько вычетов qi и qj, для которых справедливо деление нацело:

     a = (qi -1)/x   и   b = (qj – 1)/y.

Данные вычеты имеют некоторую последовательность в рамках расширенного множества ZMn.

Например, для множества вычетов Z35 (35 = 5 * 7) разности вычетов и 1:

     (q0-1), (q3-1), (q6-1), (q9-1), (q12-1), …

делятся на 7 (шаг 3 = u7), а разности вычетов и 1:

     (q0-1), (q4-1), (q8-1), (q12-1),…

делятся на 5 (шаг 4=u5).

А для множества вычетов Z91 (91 = 7 * 13) разности вычетов и 1:

     (q0-1), (q3-1), (q6-1), (q9-1), (q12-1), …

делятся на 7 (шаг 3=u7), а разности вычетов и 1:

     (q0-1), (q12-1),…

делятся на 13 (шаг 12=u13).

При построении данных последовательностей учитывалось то, что если 0 разделить на целое число (кроме 0), то получается целое число 0.

Если номера вычетов в последовательностях для разных делителей совпадают, то qi = 1. То есть, для множества Z35 q0 = q12 = 1, а для множества Z91 q0=q12=1. Тогда для группы U35 величина u35 = u5 * u7 = 12, а для группы U91 величина u91 = u7 * u13 = 12.

Если количество делителей числа n равно 2, и эти делители не равны друг другу, то:

     un = н.о.к (ux * uy).

Теперь необходимо определить число, которое делится хотя бы на одно из чисел 7, 5 и 13. Для этого достаточно перемножить значения шагов для последовательностей этих чисел:

     V = 3 * 4 * 12.

Но поскольку 12 = 3 * 4, то можно упростить число V:

     V = 3 * 4.

Можно добавить ещё числа. Для числа 3 шаг будет u3=2, для числа 11 шаг будет u11=10, для числа 17 шаг будет u17=8, для числа 19 шаг будет u19=18, для числа 23 шаг будет u23=11. Тогда для определения простых чисел от 3 до 23 значение V будет иметь вид:

     V = 3 * 4 * 2 * 10 * 8 * 18 * 11.

Но 10 = 2 * 5, 18 = 9 * 2, 8 = 2 * 4.

Упрощаем:

     V = 3 * 4 * 2 * 5 * 9 * 11.

Поскольку делители, определяемые шагом 2, будут определены шагом 4, а определяемые шагом 3 будут определены шагом 9, то окончательное значение числа V будет:

     V = 2^2, 3^2, 5, 11.

Здесь есть очень важный момент: шаг 4 справедлив для делителей, которые определяют шаг 2, а шаг 9 справедлив для делителей, которые определяют шаг 3.

Поэтому шаг a^k определяет делители для всех шагов:

     a^r, где 1 <= r < k

Можно продолжить процесс формирования числа V для определения различных простых делителей до некоторой границы В1. В результате получаем произведение простых чисел в разной степени. Что совпадает с формулой (3), и V = M.

Таким образом, с помощью теории вычетов подтверждена формула определения произведения М для первой стадии (р – 1) - метода Полларда.

Исследования показали, что если ux != uy, то:

     un = ux * uy,

а иначе un = ux = uy.

Кроме того, если после определения произведения М получается:

     2^M mod n = 1,                                                                      (7)

то получается, что в составе произведения М есть сомножители, определяющие шаги для делителей числа n. Поэтому нужно уменьшать количество сомножителей произведения М до тех пор, пока выражение (7) будет отлично от 1. В качестве примера: для множества Z35:

     q12 = 2^12 mod n = 1.

 

Задача 2. Сомножители и делители.

Для каждого делителя p числа n есть некоторая последовательность вычетов с определённым шагом по номеру вычета. Каждый элемент этой последовательности qi равен:

     qi = k * p +1, где k >= 0.

Все эти последовательности начинаются с некоторого начального вычета, который назовём шагом для конкретного делителя p. Дальнейшие вычеты последовательности определяются с помощью шага по номеру вычетов.

Можно рассмотреть обратную задачу, которая заключается в определении делителей для конкретного шага. Например:

- при шаге 2 определяется делитель 3;

- при шаге 3 определяется делитель 7;

- при шаге 4 определяется делитель 5, а также делитель 3;

- при шаге 5 определяется делитель 31;

- при шаге 6 не определяются новые делители, а определяются делители 3 и 7;

- при шаге 7 определяется делитель 127;

- при шаге 8 определяется делитель 17, а также делители 3 и 5;

- при шаге 9 определяется делитель 73, а также делитель 7;

- при шаге 10 определяется делитель 11, а также делители 3 и 31;

- при шаге 11 определяются делители 23 и 89;

- при шаге 12 определяется делитель 13, а также делители 3, 5, 7;

- при шаге 13 определяется делитель 8191;

- при шаге 14 определяется делитель 43, а также делители 3 и 127;

- при шаге 15 определяется делитель 151, а также делители 7 и 31;

- при шаге 16 определяется делитель 257, а также делители 3, 5. 17;

- при шаге 17 определяется делитель 131071;

- при шаге 18 определяется делитель 19, а также делители 3, 7, 73;

- при шаге 19 определяется делитель 524287;

- при шаге 20 определяется делитель 41,  также делители 3, 5, 11, 31;

- при шаге 21 определяется делитель 337, а также делители 7 и 127;

- при шаге 22 определяется делитель 683, а также делители 3, 23, 89;

- при шаге 23 определяются делители 47 и 178481;

- при шаге 24 определяется делитель 241, а также делители 3 5, 7, 13, 17;

- при шаге 25 определяются делители 601 и 1801, а также делитель 31;

- при шаге 32 определяется делитель 65537, а также делители 3, 5. 17, 257;

- при шаге 64 определяются делители 641 и 6700417, а также делители 3, 5. 17, 257, 65537;

- при шаге 128 определяются делители 274177 и 67280421310721, а также делители 3, 5. 17, 257, 65537, 641, 6700417;

и т.д.

Если необходимо найти делители, меньших 23, то достаточно только 8 шагов (2, 3, 4, 8, 10, 11, 12, 18). Или 2^3, 3^2, 5, 11, то есть половина всех простых чисел до 23.

Однако в (р – 1) - методе Полларда предполагается включить все простые числа в виде сомножителей. В результате половина сомножителей, формирующих произведения М для поиска делителя в рамках (р – 1) - методе Полларда, не определяют  этого делителя.

Если анализировать шаги 2, 4, 8, 16, 32, 64, 128, то можно сказать, что сомножитель qi^ri определяет делители чисел (2^( qi^rt) – 1), где 1 <= t <= i.

 

Задача 3. Определение границы В1.

В (р – 1) - методе Полларда при факторизации чисел необходимо определять границу В1[4][5].

Граница В1 необходима для того, чтобы собрать в рамках произведения М все возможные сомножители, которые могут встретиться среди сомножителей числа (p – 1). А возможные сомножители определяют возможные шаги последовательностей вычетов для различных делителей, среди которых будет делитель p.  

Один из двух простых делителей меньше Q:

     p < Q = sqrt(n).

Из примера задачи 2 видно, что шаги для делителя p всегда меньше р. Поэтому:

      В1 = Q – 1.

Если число Q очень большое, то В1 выбирается из возможности компьютера перемножить в разумное время множество простых чисел. Тогда:

      В1 < < Q.

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

Поэтому необходимо более строгое определение сильных простых чисел применительно к (р – 1) - методу Полларда.

Расчёты показали, что программы быстрее определяет делитель, если произведение М не превышает значение Q: чем больше произведение М превосходит значение Q, тем длительнее будет процесс определения делителей.

 

Задача 4. Определение степени сомножителя.

Возможны три варианта выбора степеней сомножителей в зависимости от возможностей компьютера:

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

- выбирается максимальное количество сомножителей;

- выбирается среднее между предыдущими вариантами.

Наиболее удобным будет первый вариант, и это будет доказано в задаче 5.

Поскольку необходимо в произведении М собрать, по возможности, шаги для всех простых чисел, меньших В1, то при расчёте степеней сомножителей эти сомножители в степени превышать число В1.

Если сомножители должны быть равны или больше границы В1, то необходим алгоритм выбора степеней этих сомножителей.

Для начала определим степень числа 2. Для этого необходимо определить длину числа В1 в двоичной системе. Представим, что это будет число d. Тогда первым сомножителем будет число 2^(d + 1).

Однако, если нужно получить сомножитель 2^27, то вычисление этого сомножителя на ЭВМ займёт больше времени, чем вычисление сомножителя 2^32. Поэтому в качестве степеней сомножителей лучше рассматривать числа, равные 1, 2, 4, 8, 16, 32, 64, … и т.д., то есть числа вида 2^t. И сомножитель будет иметь вид

     2^(2^t),  где 2^(2^(t – 1)) =< B1, 2^(2^(t + 1)) >= B1.

Аналогично устанавливаются степени для остальных простых чисел.

 

Задача 5. Количество определяемых шагов.

Произведение М позволяет определить множество делителей (2), поскольку это произведение включает в себя множество шагов, для которых есть соответствующие делители. Чем больше определяется множество шагов при построении произведения М, тем больше будет множество делителей.

Определим количество шагов как S.

Если имеется сомножитель a1^k1, то этот сомножитель определяет S = k1 шагов.

Если имеются два сомножителя a1^k1 и a2^k2, то эти сомножители определяют:

     S = k1 + k2 + k1 * k2 шагов.

Если имеются три сомножителя a1^k1, a2^k2 и a3^k3, то эти сомножители определяют:

     S = k1 + k2 + k3 + k1 * k3 + k2 * k3 + k1 * k2  + k1 * k2 * k3 шагов.       (8)

Аналогично можно определить количество шагов S для любого числа сомножителей произведения М.

Рассмотрим вариант из 3-х сомножителей для двух случаев:

- k1, k2, k3 – максимальны;

- k1= k2 = k3 = 1.

Ясно, что наибольшее количество шагов можно получить тогда, когда значения k1, k2, k3 – максимальны.

 

Задача 6. Уточнение второй стадии (p - 1) – алгоритма Полларда.

В (р – 1) - методе Полларда имеет место вторая стадия, однако наличие такой стадии вызывает сомнения.

Вторая стадия (p - 1) – алгоритма Поллардапредполагает, что существует только один простой множитель p числа n − 1, значение которого больше границы B1 и меньше границы В2 [1].

На этой стадии определены следующие операции:

1. Определяются несколько последовательных простых чисел в диапазоне от В1 до В2.

2. Для каждого из этих чисел определяется вычет по модулю n с учётом первой стадии.

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

Как до границы В1, так и после границы В1 имеют место почти те же простые числа, и почти те же основания степени. Поэтому непонятно: почему в одном случае перемножаются несколько сомножителей, а в другом случае – рассматривается только один сомножитель. Кроме того, в первом случае н.о.д. считается для нескольких сомножителей, а во втором случае н.о.д. считается для каждого сомножителя.

 

Задача 7. Обобщение (p – 1) – метода Полларда.

(Р – 1) – метод Полларда факторизации натуральных чисел можно обобщить.

Вариант 1. Можно построить следующую последовательность выражений:

     2^М = 1 (mod n), 2^(М + 1) = 2 (mod n),

     2^(М + 2) = 2^2 (mod n),…, 2^(М + k) = 2^k (mod n).

Получается, что для каждого вычета можно найти делитель числа n, если отнимать от этого вычета (по mod n) значения, равные 2^k. Для этого необходимо к произведению М прибавить число k.

Поскольку у числа n два делителя, то при отнимании от произвольного вычета значения вида 2^k можно определить один из делителей.

Вариант 2. Если для одного из делителей x величина ux – четная, то получаем:

     m = ux/ 2,           (2^m +1) = t (mod n),             н.о.д.(n, t + 1) = x.

То есть, прибавляя 1 к вычету, можно получить число, кратное делителю.

Такие вычеты образуют последовательность с шагом, равным величине ux.

Аналогично предыдущему варианту, можно определить делители, если прибавлять к этим вычетам числа 2^k по mod n.

Задача 8. Изменение формул (р – 1) - метода Полларда.

Основной формулой (р – 1) - метода Полларда является формула произведения сомножителей (2).

Допустим, что для некоторого числа n определено произведение сомножителей М, которое позволяет определить делители с помощью формулы (3).

Согласно задаче 5 полученные сомножители определяют определённое множество шагов, которые, в свою очередь, определяют последовательности вычетов, которые, за минусом 1, кратны различным делителям. Среди этих делителей есть делитель (или оба делителя) числа n.

Если теперь произведение М умножить на различные сомножители, то всё равно в произведении М будет уже определён шаг для последовательности вычетов, связанной с одним из делителей числа n. Что позволяет определить делителя по формуле (3).

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

     M = M(B1) = П(рi^r1 ∈ P) qi^r1, где r1 – степень числа 2. 

Или:                                        

     M = M(B1) = (П(рi ∈ P) qi) ^r1. 

Если обозначить М1 = (П(рi ∈ P) qi), то:

     M = M(B1) = М1 ^ r1. 

То есть, имеется произведение r1 произведений простых чисел от 2 до В1, и можно применить формулу (4) для нескольких блоков, каждый из которых будет произведение М1.

Таким образом, формулы (1) и (2) (р – 1) - метода Полларда можно изменить следующим образом:

     М1 = (П(рi ∈ P) qi)

     M = M(B1) = М1 ^ r1,     где 2 ^ r1 > B1

     a1 = a ^ M1 (mod n)                                                                      (9)

     a ^ M = a ^ (М1 ^ r1) = (a ^ М1) ^ r1 = a1 ^ r1 (mod n)   

     p = н.о.д. (n, a ^ M - 1) = н.о.д. (n, a1 ^ r1 - 1)

С помощью новых формул (9) значительно уменьшается время определения делителей числа n с помощью (р – 1) - метода Полларда.

 

Задача 9. Шаги двух делителей в произведении М.

В задаче 1 было показано, что, если в произведение М включены шаги для двух делителей (или нескольких делителей) числа n, то получим:

      a^M = 1 (mod n).

То есть, делители определить в данном случае невозможно.

Причём, это можно определить не перемножая всех простых чисел до В1. Как известно, для каждого блока вычисляется значение для нового основания степени по формулам (5) или (9). И если это значение равно 1, то вычисление по методу останавливается.

Здесь необходимо рассмотреть 2 варианта:

Вариант 1. Определять делители необязательно, так как (р – 1) - метод Полларда применяется для числа n только для того, чтобы определить: у числа n сильные простые делители или нет.

Поскольку 1 определена при небольшой границе В1 (или В2), то у числа n есть несильные простые делители, поэтому число n в дальнейшем не рассматривается.

Вариант 2. Необходимо определить делители.

Значение основания степени, равное 1, получается после вычисления в одном из блоков. Поэтому либо на один шаг ранее по формированию произведения М, либо в предыдущем блоке останавливается вычисление произведения М и определяется один из делителей.

При этом будет вариант, когда этих делителей нельзя будет определить по (р – 1) - методу Полларда. Это не получится в том случае, если у этих делителей один и тот же шаг по формированию последовательностей вычетов.

Например, один и тот же шаг, равный 2^8, есть у последовательностей вычетов для двух  простых чисел:  274177 и 67280421310721.

Задача 10. Определение сильных простых чисел применительно к (р – 1) - методу Полларда.

Существует определение сильного простого числа: простое число p будет сильным простым числом, если число (p – 1) имеет достаточно большие сомножители. Данное определение является основным для (p – 1) – метода Полларда.

В задаче 3 было показано, что при небольших сомножителях определяются очень большие делители. Рассмотрим пример 1:

есть простое число p = 67280421310721;

сомножители числа (p – 1): 2, 2, 2, 2, 2, 2, 2, 2, 5, 47, 373, 2998279;

сомножители числа (p + 1): 2, 3, 3, 109, 18401, 1863581.

По определению сильного простого числа данное число p является сильным простым числом по отношению к границе, например, В1 = 1000000.

Однако число р, как делитель некоторого числа n, определяется с помощью одного сомножителя: М = 2 ^ 8, не зависимо от величины 2-го делителя числа n..

Получается, что сильным простым числом применительно к (p – 1) – методу Полларда при определении границы В1 является такое простое число q, которое является делителем числа (2^ k – 1), где k – составное число, k > B1, и не существует числа k1, кратного k и k1 < k, такого, что q будет делителем числа (2^ k1 – 1).

Согласно этому простое число p = 67280421310721 из примера 1 не является сильным простым числом при определении границы, например, В1 = 1000000.

Рассмотрим пример 2: есть простое число р1 = 67280421310771 = p + 50.

Если перебирать сомножители числа (р1 – 1):

      2, 3, 5, 17, 19, 257, 27016669,

для определения произведения М, то окажется, что только при М = 67280421310770 число p1 является делителем числа (2^M – 1).

Поэтому, согласно новому определению, число p1 будет сильным простым числом при определении границы В1 = 1000000.

Таким образом, необходимо новое определение сильного простого числа для (p – 1) – метода Полларда:

сильным простым числом применительно к (p – 1) – методу Полларда при определении границы В1 является такое простое число q > B1, которое можно определить с помощью этого метода только тогда, когда в произведение М включены все сомножители числа (q – 1).

Была составлена программа на Python для определения не сильных простых чисел при определении границы В1.

Например, для границы В1 = 100000 не сильными простыми числами будут простые числа, большие 10000000:

22253377, 25781083, 97685839, 141512291, 160465489, 168410989, 199381087.

А для границы В1 = 1000000 не сильными простыми числами будут простые числа, большие 100000000:

823679683, 1021622741

Выводы

Применение множества вычетов к построению (p – 1) – метода Полларда факторизации натуральных чисел позволило несколько изменить представление о сильных простых числах.

Оказалось, что существующее определение сильных простых чисел p, для которых важно иметь большие сомножители числа (p – 1), не подходит для (p – 1) – метода Полларда.

Для (p – 1) – метода Полларда подходит другое определение сильного простого числа при определении границы В1, основанное на обязательном присутствии в произведении сомножителей М всех сомножителей сильного простого числа.

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

Получено новое определение сильного простого числа применительно к (p – 1) – методу Полларда.

Изменена формула метода с целью уменьшения времени определения делителей.

Показано соотношение сомножителей числа М и делителей числа n.

Получены алгоритм для определения числа В1 и степеней сомножителей числа М при факторизации числа n.

Получен обобщённый (p – 1) – метод Полларда факторизации натуральных чисел.

1. https://ru.wikipedia.org/wiki/ P−1-метод_Полларда
2. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие / Ш.Т. Ишмухаметов.– Казань: Казан. ун. 2011.– 190 с.
3. Pollard J. M. Theorems on factorization and primality testing (англ.) // Mathematical Proceedings of the Cambridge Philosophical Society / B. J. Green — Cambridge University Press, 1974. — Vol. 76, Iss. 3. — P. 521—528. — ISSN 0305-0041; 1469-8064 — doi:10.1017/S0305004100049252
4. Montgomery P., Silverman R. D. An FFT extension to the P-1 factoring algorithm (англ.) // Math. Comp. — AMS, 1990. — Vol. 54, Iss. 190. — P. 839—854. — ISSN 0025-5718; 1088-6842 — doi:10.1090/S0025-5718-1990-1011444-
5. Коэн А. A Course in Computational Algebraic Number Theory — 4th Print Edition — Берлин, Гейдельберг, Нью-Йорк: Springer, 2000. — 550 с. — (Graduate Texts in Mathematics) — ISBN 978-3-540-55640-4 — ISSN 0072-5285
6. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с.

Рецензии:

20.10.2020, 2:57 Мирмович Эдуард Григорьевич
Рецензия: Статья безусловно обладает признаками и актуальности, и научной новизны. Она достойна публикации. Однако библиографический список для такой работы не отвечает принципу научности. Рецензент советует учесть результаты работ [1-3] и включить их в библиографический список. Без слов о криптографии статья выглядит не очень. Например, [4]. Некоторые утверждения в статье (например, про границу В1, большие, или сильные простые делители и др.) можно подтвердить по ссылке [5]. 1.Pollard J. M. Theorems on factorization and primality testing (англ.) // Mathematical Proceedings of the Cambridge Philosophical Society / B. J. Green — Cambridge University Press, 1974. — Vol. 76, Iss. 3. — P. 521—528. — ISSN 0305-0041; 1469-8064 — doi:10.1017/S0305004100049252 2.Montgomery P., Silverman R. D. An FFT extension to the P-1 factoring algorithm (англ.) // Math. Comp. — AMS, 1990. — Vol. 54, Iss. 190. — P. 839—854. — ISSN 0025-5718; 1088-6842 — doi:10.1090/S0025-5718-1990-1011444-3 3.Коэн А. A Course in Computational Algebraic Number Theory — 4th Print Edition — Берлин, Гейдельберг, Нью-Йорк: Springer, 2000. — 550 с. — (Graduate Texts in Mathematics) — ISBN 978-3-540-55640-4 — ISSN 0072-5285 4.Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 978-5-94057-103-2 5.https://ru.wikipedia.org/wiki/P&#8722;1-метод_Полларда Кроме того, в приведенную ссылку надо добавить страницы (С. 53—55).

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

6.09.2020, 9:07 Усов Геннадий Григорьевич Отзыв: Добавлена задача 8: Изменение формул (р – 1) - метода Полларда. Изменены аннотация и новизна.

14.09.2020, 16:36 Усов Геннадий Григорьевич Отзыв: Добавлена задача 9: Шаги двух делителей в произведении М.

17.09.2020, 18:29 Усов Геннадий Григорьевич Отзыв: Добавлена задача 10: определение сильных простых чисел применительно к (р – 1) - методу Полларда. Добавлены выводы. Проведено уточнение в задаче 3 и в научной новизне.

21.10.2020, 23:39 Мирмович Эдуард Григорьевич Отзыв: Уважаемый Геннадий Григорьевич! Произошло какое-то недоразумение. Страницы указаны были для статьи, а Вы привели ссылку на учебное пособие, т.ч. стр. в скобках следует убрать. Просьба к Вам: проверить ссылку на [6], она не соответствует смыслу написанного. Ссылку [6] надо бы перевести куда-то в начало и в начале статьи сказать что-то о криптографии, или оставив её в конце, но перед заключением таже о криптографии сказать. В тексте статьи дать ссылки в квадратных скобках на приводимые источники, вставив слова об этих источниках.

22.10.2020, 17:01 Усов Геннадий Григорьевич Отзыв: Уважаемый Эдуард Григорьевич! Я убрал в библиографии указатели страниц, перенес [6] в "актуальность", где постарался сформулировать дополнительные задачи, которые решаются в настоящей статье. При этом был сделан упор на криптографию. С уважением, Усов Геннадий Григорьевич.

23.10.2020, 12:50 Мирмович Эдуард Григорьевич Отзыв: Рецензент подтверждает рекомендацию к публикации статью Г.Г. Усова и завидует его работоспособности и математическому образу мышления.

23.10.2020, 14:01 Усов Геннадий Григорьевич Отзыв: Уважаемый Эдуард Григорьевич! Спасибо за рекомендацию!

16.08.2021, 11:40 Цорин Борис Иосифович Отзыв: Проблема 1. Автор демонстрирует незнание математической терминологии, путая последовательность с множеством, а мощность с порядком (составляет множество, включающее в себя одинаковые элементы, и называет количество элементов множества порядком множества). Также автор регулярно путает НОК с произведением чисел. Проблема 2. В "задаче 1" автор при помощи избыточно сложных рассуждений (например, он тратит полстраницы на то, чтобы объявить, что 0 делится на любое натуральное число), получает выражение, внешне похожее на формулу из метода Полларда, из чего делает вывод, что "подтвердил формулу для метода Полларда", что не имеет отношения к поставленной "задаче". Таким образом, "задача 1" - просто текст, впустую удлиняющий статью. Проблема 3. В "задаче 2" автор критикует метод Полларда, утверждая, что "половина сомножителей не определяет делителя". Однако он забывает о том, что искомый делитель заранее не известен, а следовательно, исключение части сомножителей приведет к уменьшению шанса на успех применения метода. Проблема 4. В "задаче 3" автор делает "интереснейшее" наблюдение о том, что чем меньше показатель степени, тем быстрее в степень можно возвести. К сожалению, это не является сколь-либо новым или неочевидным результатом. Проблема 5. В "задаче 4" автор для ускорения работы алгоритма предлагает увеличить степени сомножителей числа М(В). То, что при этом вероятность успеха первой стадии метода Полларда станет крайне низкой, автора не интересует. Проблема 5. Вся "задача 6" коротко сводится к тому, что автор не понимает, почему метод Полларда работает, и поэтому предлагает его считать неработающим. Проблема 6. В "задаче 7, вариант 1" автор предлагает заменить вторую стадию метода Полларда на нахождение числа, кратного факторизуемому. Почему автор считает, что кратное и делитель - это одно и то же, непонятно. В "задаче 7, вариант 2" автор, видимо, предлагает сначала найти делитель числа, затем применить некий алгоритм, и благодаря этому найти число, кратное уже найденному делителю, что позволит найти тот же самый делитель еще раз. Ну либо он предлагает искать делитель при помощи перебора по "+1", автор не завершил свою мысль. Проблема 7. В "задаче 8" автор мало того, что опирается на "задачу 4", которая предлагала испортить метод Полларда, так еще и считает, что a ^ (М1 ^ r1) = (a ^ М1) ^ r1. Проблема 8. В "задаче 9" автор утверждает, что при a^M = 1 (mod n) метод Полларда не работает, и предлагает начать искать делители числа a^M-1, тогда как метод Полларда в этом случае просто требует взять другое значение a. Вывод: данная статья является, как и другие статьи данного автора, набором из бесполезного перечня примеров, иллюстрирующих чужие результаты, и личных математических ошибок автора. Очень жаль, что данная статья была опубликована. Рекомендую исключить из перечня рецензентов гр. Мирмовича Э.Г. как недобросовестного рецензента, явно не читающего работы, зато рекомендующего к публикации сотни статей из самых разных областей знаний и излагающего поправки почти исключительно к библиографическим спискам.

17.08.2021, 18:43 Мирмович Эдуард Григорьевич Отзыв: По существу математической корректности статьи. Рецензентом не анализируются все детали каждой статьи, а рассматриваются необходимые и достаточные условия снятия или нет её с дальнейшего рассмотрения и дискуссий. Невозможность представления числа в сокращённом формате в формуле (9), отмеченная нашим новым рецензентом, действительно, непростительный "ляп" автора, ставящий под угрозы отдельные выводы статьи, там вообще выделить автономное число в мультистепенной формуле нельзя. Это ли не позволяет сделать вывод об уменьшении времени поиска числа внутри факториала? Но на то и эта электронная площадка, созданная для возможности представления не "нобелевских" трудов на обсуждение авторами, в т.ч. и не профессиональными: пенсионерами, учителями, магистрантами и студентами; этот журнал не входит в Перечень ВАК, статус Scopus, WoS и др. Являясь профессиональным научным редактором, создателем, членом редколлегий и рецензентом целого ряда научных журналов, как рецензент я отправляю здесь в основном эту функцию. Более трети моих рецензий отрицательны: по родственным мне темам (космо- и геофизика, экология, безопасность жизнедеятельности) – с проникновением в суть и пр., другие – по редакторским критериям. Уважаемый Борис Иосифович, я приглашён в рецензенты при самом основании журнала, никто из "здешних" рецензентов сам не напрашивался и не держится за эту бесплатную очень времязатратную деятельность. Никакие призывы к модераторам тут не нужны, достаточно самому рецензенту удалить себя из рецензентов. Поддержав журнал на начальной стадии, я в любой момент сам откажусь, не волнуйтесь, т.к. мне уже за 80, а я ещё многое должен сделать на этом свете.. В публикации Вашей статьи про "шаром покати" и в оформлении, и в тексте также есть огрехи, более того, она не могла быть вообще опубликована по одной запутанной и некорректной рецензии из двух строк без подробного анализа некоторых декларативных Ваших утверждений и с пустословием об актуальности, противореча авторскому утверждению об её не актуальности. А эта Ваша рецензия не вполне корректна, т.к. отметив некоторые недостатки и ошибки, Вы обязаны были опротестовать положения из выводов и других заключительных умозаключений. Вдруг, например, эти замеченные ошибки настолько локальны, что окончательные выводы не затрагивают, вдруг. А, призывая к репрессиям одного из рецензентов, надо было опровергнуть его обширные замечания, что автор, признав эти замечания и трижды переделывая по ним статью, также не прав. Запомните и зарубите себе на носу, дорогой наш новичок, идеальные в научном отношении результаты, оформленные не по ГОСТу, небрежно, с описками и ошибками, без корректных ссылок и библиографического списка и т.д. опубликованы здесь быть не могут, в т.ч. и потому, что модераторы-тьюторы научной редакцией не занимаются. А дискуссионные, гипотетические соображения, научные рассуждения и т.д., но оформленные идеально, в т.ч. и с помощью рецензентов, подтверждённые корректными и адекватными ссылками могут и будут представляться на повторные рецензии и дискуссии. Журнал принимает статьи, представляющие собой критику, дискуссии, даже опровержения опубликованных другими авторами статей. Кто не знает, что в научной публицистике уже 500 лет опубликовано более половины и более результатов, трудов, разработок и др., опровергнутых позднее. В нашем электронном журнале приняты та же научная этика и ГОСТы, как и в бумажных, в т.ч. ваковских журналах. Вот оформите свою рецензию как следует, с аннотацией, названием, библиографическим списком и т.д. и публикуйте как отдельную критическую статью, и редакция с удовольствием её примет. Ещё раз такие обороты и оскорбления от Вас здесь появятся, то будут предприняты противоположные меры по отношению к тому, кто допускает отклонения от научной этики. Наберите в любом браузере всего лишь одно слово "Э.Г. Мирмович" или «E.G. Mirmovich», а уж принесёте после этого извинения или нет - дело Вашей совести и этики.

18.08.2021, 12:44 Усов Геннадий Григорьевич Отзыв: Уважаемый Эдуард Григорьевич! Прошу прощения за то, что из-за меня Вам пришлось выслушать (в виде отзыва) ряд оскорблений. Да, я немного заторопился и хотел получить интересную формулу. Но ошибся. Просто вместо : « a ^ M = a ^ (М1 ^ r1) = (a ^ М1) ^ r1 = a1 ^ r1 (mod n) p = н.о.д. (n, a ^ M - 1) = н.о.д. (n, a1 ^ r1 - 1)» надо писать: «a ^ M = a ^ (М1 ^ r1) p = н.о.д. (n, a ^ M - 1) « Конечно, статью уже не поправить… По остальным замечаниям от того парня: 1. Элементы последовательности – это тоже множество. 2. Подтвердив метод Полларда, я показал, что мои расчёты совпадают с этим методом. 3. А я доказал, что можно исключить часть делителей. 4. Здесь чепуха. 5. Метод Полларда работает, но не определена граница. Я границу определил. 6. Не надо додумывать, нужно просто спросить. 7. Здесь мои извинения за ошибку. Но эта ошибка не влияет на конечную цель статьи. 8. Здесь этот парень ошибается – если М включает два делителя, то никакое а не поможет. Кстати, об этой единице в методе Полларда ни слова. Теперь о том, почему появилась статья. В актуальности статьи я частично об этом сказал. И главное, все говорят о делителях в числе М, а почему такие делители получаются – об этом ни слова. Всех это устраивает и быстро (относительно) идёт определение делителей. Данная статья объясняет появление делителей в числе М. Эдуард Григорьевич! Пользуясь случаем, прошу Вас дать мне ссылку на «адиковые числа». Не могу найти публикаций. Было бы интересно их рассмотреть. Ещё раз прошу прощения за досадную ошибку в формуле 9. С уважением, Усов Геннадий Григорьевич

18.08.2021, 13:44 Цорин Борис Иосифович Отзыв: 1. Вы не знаете терминологию, которую используете. Последовательность - не множество. Последовательность имеет порядок (и не в том значении, в котором Вы использовали это слово), множество нет. Последовательность допускает повторения, множество нет. 2. Вы не подтвердили метод Полларда, а проиллюстрировали его. 3. Вы не доказали, что можно исключить часть делителей, так как метод Полларда и подразумевает взятие относительно небольшого числа простых множителей при большом факторизуемом числе. "Исключив часть делителей", Вы метод портите, ограничивая поиск делителей исходного числа буквально несколькими заранее заданными возможными простыми делителями. 4. "Здесь чепуха" - в статье разве что. 5. Про "границу" Вы говорили в "задаче 3", а мой пункт 5 касается "задачи 4". 6. Вы можете, конечно, уточнить, что Вы имели в виду, но от этого больше пользы не будет. 7. Ошибка в выводе формулы делает выведенную формулу неверной. 8. Если М включает два больших простых делителя, то не "никакое а не поможет", а сложность алгоритма становится очень большой, поэтому метод Полларда применяют для поиска небольших делителей, а когда он не помогает, применяют другие алгоритмы факторизации. О единице в методе Полларда есть, откройте хотя бы Википедию, даже там есть. "Почему такие делители получаются", написал сам Поллард, в 1974 году, если не ошибаюсь. Любой метод публикуется либо доказательно, либо как гипотеза. Метод Полларда публиковался доказательно. И, пользуясь случаем, не "адиковые числа", а "p-адические числа".

18.08.2021, 14:35 Усов Геннадий Григорьевич Отзыв: 1. У меня не последовательность, а элементы последовательности. Это большая разница. И элементы последовательности составляют некоторое множество.

18.08.2021, 19:14 Цорин Борис Иосифович Отзыв: 1. Но терминологию при этом Вы неоднократно использовали неверную. "n - порядок множества", - так сказать нельзя. В данном случае n - длина последовательности, у множества не порядок, а мощность; мощность множества у Вас в рассуждениях равна не n, а un, так как в множестве un различных элементов. Существует термин "порядок группы", который для группы вычетов равносилен термину "мощность множества", существует термин "отношение порядка", но не существует термина "порядок множества". Чем больше Вы допускаете ошибок в терминологии, тем труднее понять Вашу работу (и, соответственно, тем труднее выловить все ошибки в рассуждениях). Так что или исправляйте терминологию, или укажите, где Вы взяли такой термин, как "порядок множества", или расскажите, для чего Вы используете несуществующие термины. )

19.08.2021, 8:33 Усов Геннадий Григорьевич Отзыв: Для числа n получаем группу вычетов Zn. Внутри группы вычетов Zn есть несколько групп вычетов Un. Для групп вычетов существует понятие порядок группы. И чтобы отличить Zn от Un было принято решение о названии Zn как множества. Только и всего. Надеюсь, что дальше статья будет лучше читаться?

19.08.2021, 11:15 Цорин Борис Иосифович Отзыв: Все еще неверно. Порядок группы, как и мощность множества, исчисляется "без повторов". Если важно количество элементов, включая одинаковые, и элементы упорядочены, то следует говорить о последовательности и ее длине, а не о множестве или группе. Ну и хочу отметить, что неверная терминология - это меньшая проблема по сравнению с остальными перечисленными мной проблемами статьи.

19.08.2021, 16:32 Мирмович Эдуард Григорьевич Отзыв: Безусловно, я имел в виду р-адические числа Qp в виду их прямого отношения к расширению алгоритмической и иной деятельности с простыми числами. И,вообще, МЫ (все в прошлом и нынешнем времени) так замкнулись на десятичной системе счисления, что не все наши арифметическо-алгебраические "экзерсисы" готовы к тестированию в системах счисления 10<d<10. И, кстати, истнный математический термин "p-adic", "2-adic" и пр. руссифицровав чисто "нашенским" суффиксом, мы не можем запретить употребление в каких-то случаях и другую, нормальную транслитерацию этого, как и других, термина и слова (Оскар Уайльд или Вайлд, Вильям или Уильям). Мы вообще искалечили многие понятия этим самым, затруднив понимание и развитие взаимопонимания: Бабилон или Вавилон (только у нас), названия половины стран, половины фамилий и др.

19.08.2021, 16:56 Мирмович Эдуард Григорьевич Отзыв: Полагаю, что обоим сторонам, как я и предлагал, надо "соорудить" по статье и опубликовать здесь. Одному доказать, что его спешка и ошибки, которые он признаёт, не изменяют основных выводов, или изменяют так-то и так-то, немного покаявшись в том, что из-за гипотетических 2% выигрыша во времени, возможно, и не стоило "вызывать огонь на себя" как у "Сына артиллериста". Да, и поменьше хотелось бы видеть без адекватных доказательств (как в другой статье) таких слов, как "Самый", "фундаментальный" и пр. А другому - изложить свои дискуссионные доводы, оформив их корректным образом, что явится практически первым или редким примером в этом журнале, как раз и предназначенном для научного "предбанника" перед "смертью" или рождением настоящего научного новшества. Только корректности в дискуссиях всё равно следует учиться. Например, "разгромив", как считает новый рецензент, статью (не учёного, кандидата наук, гражданина, хотя первое - это истина, а гражданин он или нет - в общем-то неизвестно без скана паспорта), кроме действительной одибки в формуле (9), в остальном запутался сам, интерпретировав по-своему разные термины, и воюяя с этими выдумками по-чукотски. Набрав, например, из некой последовательности себе для задачи элементов, автор мог их назвать хоть матрицей, хоть множестовом, хоть randоm-набором и т.д. И так в других обвинениях с истошными интонациями. А в статье его вся критика будет выглядеть по-иному, на научно-корректном языке. Успехов, вам!

20.08.2021, 9:03 Усов Геннадий Григорьевич Отзыв: Уважаемый Эдуард Григорьевич! Целиком согласен с Вашими предложениями. Прошло много времени с момента публикации статьи. Сейчас её уже менять нельзя. А с учётом того, что статья "полежала на полке" журнала, стали видны моменты, где запутался, поэтому выхожу из данной ситуации (и не только по этой статье) не меняя выводов статьи. Но такое латание статьи не приводит к хорошему результату. Тем более, что-то уже забылось (работаю над другой темой). Поэтому попробую немного по другому изложить статью в новом варианте, не меняя сути предыдущего варианта. А там уже буду ждать атак нашего рецензента и Ваших действий по примирению сторон. Попробую начать с ВТФ, статьи по которой снял с журнала. Там есть что привести в порядок. С уважением, Усов Геннадий Григорьевич! P.S. А все-таки жаль 2 %.

20.08.2021, 9:46 Цорин Борис Иосифович Отзыв: Набрав из некой последовательности себе элементов, автор мог назвать их хоть плюющейся коброй, но вводя новый термин или переопределяя известный, любой автор любой статьи должен этот термин определить. Что касается "в остальном запутался сам" - аргументируйте. Я у себя пока вижу только одно "запутался" - я действительно запутался в нумерации проблем, обозначив две проблемы подряд как "проблема 5". Неудобно все-таки писать списки в условиях невозможности разделения на абзацы. Ну и да, я не считаю указание на элементарные ошибки чем-то достойным отдельной статьи. P.S. Не любой кандидат наук - ученый, см. материалы "Диссернета".

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