[recovery mode] Факторизация и классы чисел натурального ряда

     Примем сокращения: натуральный ряд чисел (НРЧ); задача факторизации больших чисел (ЗФБЧ).     Манипулирование с натуральными числами возможно как непосредственно со значениями, так и с характеристиками — свойствами чисел. Удобство такого манипулирования во многом определяется моделью числа. Желательно разнообразие моделей иметь ограниченным, а структурное построение простым. Описания свойств моделей натуральных чисел (впрочем, и любых других чисел) желательно иметь в количественном выражении, в формализованном виде. Зависимость значений показателей свойств от разрядности чисел необходимо устранить, либо выбирать свойства свободные от таких зависимостей. Любая классификация в своей основе имеет свойства — это элемент формализации. Основной вопрос в работе — факторизация чисел — в связи с чем ниже сформулируем вариант теоремы факторизации натурального числа.     В теореме говорится о том, что трудности факторизации возникают не для всех чисел, следовательно, сложной процедуре факторизации необходимо подвергать не все числа НРЧ, а только их некоторую (меньшую) часть. В тексте теоремы не говорится, как эту меньшую часть формализовать и сделать удобной для последующей обработки. Но в работе как раз и пойдет речь о формировании удобного для обработки представления чисел такого меньшего множества.          Теорема факторизации натуральных чисел

Произвольное составное натуральное число N путём последовательного выполнения над ним некоторых элементарных преобразований может быть представлено произведением видаN =2t2∙3t3∙5t5∙(pk+30∙t), где 0 ≤ ti, i = 2,3,5, t — натуральное, рk > 5 — простое.Теорема1. Если N — составное чётное натуральное число, то оно представимо в виде N=2t2∙n2, где n2 ≡ 1(mod 2) — составное нечётное число, t2=1(1)…, и 2 ∤ n2;2. Если N = n2 — составное нечётное число, оканчивающееся цифрой 5, то оно представимо в виде N=5t5∙n5, где n5 — составное нечётное число, t5 = 1(1)…; и 5 ∤ n5;3. Если N = n5 — составное нечётное число, не оканчивающееся цифрой 5, а его свёртка s (N) (сумма цифр) кратна числу 3, то оно представимо в виде N=3t3∙n3, где n3 — составное нечётное число, t3 = 1(1)…; и 3 ∤ n3;4. Если N = n3 — составное нечётное число, с последней цифрой (флексией) ф ϵ {1, 3, 7, 9}, то оно имеет вид N=(pk+30∙t), где t = 1(1)… — натуральное число, а pk ϵ {7,11,13,17,19,23,29,31}, и факторизацию можно выполнить, например, используя понятие предельного контура и ф-инварианта нечетного числа или одним из существующих известных методов.

     Вместо доказательства. Далее текст работы, включая таблицу 3, является по существу доказательством первой части теоремы (о представлении числа в виде модели N = 30∙t + pk). По ходу изложения возникают полные и усеченные модели НРЧ, плоские и объемные. Множество всех натуральных чисел разделяется на два подмножества.      Первое — интуитивно воспринимаемое как большее содержит натуральные числа, которые факторизуются элементарными средствами (используются простейшие признаки делимости на простые числа 2, 3, 5). Второе подмножество — меньшее, которое содержит и все нечетные простые (кроме 3 и 5), и факторизация которых представляет особенно для больших чисел непреодолимую проблему настоящего времени. Последнее известное по публикациям факторизованное число описывается 232 десятичными цифрами.     Известная аналитическая модель НРЧ в виде перечня 30k, 30k ± 1, 30k ± 3, …, 30k ± 15, k = 1(1)∞, соотношений позволяет понять, как можно описать те из чисел, которые должны содержаться в каждом из указанных подмножеств, т. е. по существу выполнить такое разбиение НРЧ.     Мультипликативное представление числа 30 имеет вид 30 = 2∙3∙5. Натуральные числа N, сравнимые с нулем по модулю делителей числа 30, N ≡ 0 (mod2),  N ≡ 0 (mod3),  N ≡ 0 (mod5) — это все четные числа, числа, делящиеся на три без остатка, и нечетные числа, оканчивающиеся цифрой 5.     Оказывается, множество натуральных чисел с нарушением подобных свойств распадается на классы эквивалентности с другими простыми, хорошо различимыми признаками. Таким образом, задача в работе состоит в разделении НРЧ на два подмножества, и получении описания меньшего в простой и удобной для дальнейшей обработки чисел форме.     Классы натуральных чисел. Положим в основу рассматриваемой классификации два очень просто определяемых показателя свойств (s, ф) чисел. Первый показатель обозначен символом s,1 ≤ s ≤ 9, назван сверткой (это сумма цифр числа, доведенная до одной цифры) числа, он характеризует свойство делимости числа на три, а второй показатель обозначен символом ф,0 ≤ ф ≤ 9, — назван флексией (окончанием, последней цифрой) числа, характеризует свойство конечного числа иметь последнюю цифру.

     Пример 1. N = 4757, s (N) = ((4 + 7 + 5 + 7 = 23) → (2 + 3)) = 5; ф (N) ≡ N (mod10) = 7.     Пара свойств чисел, характеризуемых показателями (s, ф), разбивает НРЧ на не пересекающиеся классы (эквивалентности), которые имеют одинаковые значения пары показателей.      Характеристикой класса чисел, которому принадлежит число N = 4757, является пара со значением (s, ф) = (5, 7).     Количество Т (s, ф) классов чисел, различимых по такой характеристике, определяется произведением диапазонов изменения значений каждого показателя двух свойств числаТ (S, Ф) = S×Ф = 9×10 = 90.     Объем каждого класса включает бесконечное множество натуральных чисел, среди которых есть наименьшее число в классе. Поместим наименьших представителей всех классов в левую часть таблицы 1, а справа ее продолжим, заполняя (по образцу слева) клетки таблиц подряд следующими натуральными числами.

Таблица 1 — Классы Т (s, ф) чисел с периодом 90. Плоская модель НРЧd22e396e78204c18a4a006202d430649.png

     Анализ содержимого таблицы (множество чисел Т-90) показывает, что в левой части таблицы 10×9 все числа наименьшие в своем классе и имеют разные значения характеристики (s, ф). Правая часть таблицы 10×9 аналогично левой части заполнена представителями разных классов с такой же характеристикой (s, ф), но с очередным увеличенным на 90 единиц значением (периодом) элемента. Подобные таблицы можно продолжить до бесконечности и сдвигать их влево с наложением на 1-ю (левую) таблицу. В итоге получим трехмерный параллелепипед, в котором над каждой клеткой нижней таблицы выписаны все числа, образующие класс натуральных чисел с фиксированным значением пары (s, ф).

          Объемная модель НРЧ

     По существу нами получена еще одна уже объемная модель НРЧ. Ее преимущества проявляются в возможности существенно урезать НРЧ без потери важных позиций, например, позиций, содержащих простые числа. Покажем, как это можно сделать.     Во-первых, вычеркнем строки таблицы 1, содержащие четные числа и нечетные, оканчивающиеся пятеркой, во-вторых, удалим классы чисел, кратные тройке. Клетки таблицы таких классов принадлежат диагоналям параллельным побочной диагонали таблицы. В таблице 1 удаляемые ячейки (классы) выделены заливкой.     Сохранились не закрашенные клетки-классы Т (s, ф), число которых 24 (оставшиеся после вычеркивания числа назовем множеством Т-24), им соответствуют ячейки таблицы без заливки. Возможными флексиями в оставшихся классах будут только ф = 1,3,7,9 и с каждой флексией по 6 значений свертки, т. е. 24 класса. Вполне очевидно, что простые числа могут появляться в пределах только этих классов. Действительно, в левой таблице из 24 наименьших представителей всех классов 22 являются простыми числами. Лишь две ячейки (из 24) заполнены составными числами 7×7 = 49 и 7×11 = 77, полученными умножением наименьшего остающегося простого числа 7 на себя и на следующее за ним простое число 11.

        Алгебраическая группа вычетов генераторов классов

     Будем продолжать реформирование НРЧ, вернемся к числу 30 = 2∙3∙5. Вспомним, что восьмерка простых чисел р (i) = {7,11,13,17,19,23,29,31} образует мультипликативную группу Э (группу Эйлера) вычетов восьмого порядка по этому модулю. Единичный элемент отождествляется с простым числом 31, р (i) ≡ 31(mod30) = 1. По теореме Лагранжа (о порядках групп) группа Э может иметь собственные подгруппы, 2-го и 4-го порядков. Элементы группы 8-го порядка (11,19 и 29) имеют 2-й порядок; (7,13, 17, 23) 4-й порядок и единица. Подгрупп 4-го порядка имеется три: одна (1,11,19,29) — включает только инволюции, и две подгруппы циклические:7 × 7 ≡ 49 (mod30) = 19; 19 × 7 ≡ 133(mod30) = 13; 13 × 7 ≡ 91 (mod30) = 1;11× 19 ≡ 209 (mod30) = 29; 11 ×29 ≡ 319(mod30) = 19; 19 ×29 ≡ 551 (mod30) = 1;17× 17 ≡ 289 (mod30) = 19; 19 ×17 ≡ 323(mod30) = 23; 23 × 17≡ 391 (mod30) =1;

     Как ни удивительно, но все числа 24 классов |Т (S, Ф) | = 3×8 преобразуются в семейство классов, состоящее всего из 8 классов, порождаемых каждым представителем множества р (i). В новых классах числа — элементы следуют с периодом уже не 90, а в три раза меньшим, всего лишь 30.

Таблица 2 — Мультипликативные подгруппы группы вычетов (pk)по mod30a00fc74b6be7450d89bf82d2628540e9.png

      Классы формируются с учетом флексии и свертки чисел по три пары (2,1),(5,1),(8,1); (4,1),(7,1),(1,1); (2,3),(5,3),(8,3); (4,3),(7,3),(1,3); (7,7),(1,7),(4,7); (8,7),(2,7),(5,7); (7,9),(1,9),(4,9);(8,9),(2,9),(5,9);      Ниже в таблице 3 приведем начальные фрагменты этих 8 классов. Любое нечетное число N >31 не кратное 3 или 5 имеет вид N = p (i)+ 30t и попадает в один из 8 классов, представленных в таблице 3. Назовем множество чисел из такой таблицы множеством Т — 8.

Таблица 3 — Классы чисел с периодом 30. Простые числа {pk} выделены заливкой9f361ea92efa4a1082faee3ab6d97e03.png

     Даже поверхностный анализ таблицы позволяет сделать некоторые выводы в отношении простоты-сложности и возможности факторизации чисел: — все степени всех генераторов классов, т.е. простых чисел — составные; — строки с номером кратным генератору в клетке столбца этого генератора содержат составные числа, делитель которых генератор; — числа, принадлежащие области запрета простых чисел в спирали Улама, — составные, примеры таких чисел в первой тысяче:143,161,203,217,323,451, 517,539,473, 611,637 и др.– числа, допускающие разложение в сумму- разность и вынесение за скобку общего множителя, например, 217 =210+7 =7(30 +1) =7×31; 1397 = 1270 +127 = 127(10 +1) = 127×11.     Таким образом, элементарными средствами и операциями удается селектировать множество Т-8 нечетных чисел НРЧ, которые должны и могут служить объектом последующего исследования в интересах решения как теоретических, так и прикладных практических задач. К числу таких задач в области криптологии и информационной безопасности следует отнести следующие: ЗФБЧ, задачу установления простоты числа, задачу дискретного логарифма в конечных полях и группах точек эллиптических кривых.     Множество чисел Т-8 организовано специальным образом (состоит из 8 классов), наименьшие представители классов образуют группу вычетов по модулю 30 (φ (30) = 8). Это свойство обеспечивает определение номера столбца результата произведения пары чисел, номера столбцов которых известны. Таблица Кели группы обеспечивает решение этой задачи.Назначение примеров показать, какая информация о связях значений чисел, номеров строк и номеров столбцов содержится в множестве Т- 8.Один из возможных методов факторизации чисел множества Т-8 с использованием таблицы 3.     Пример 2. Пусть задано составное нечетное натуральное число (сннч)N = 1727. Требуется факторизовать его. Найдем положение этого числа в множестве Т-8: номер строки N/ 30 = 57 (берется целая часть дроби), номер (имя) столбца N — 30∙57 = 17. В этом же столбце задаем произведение 7∙11=77, номер строки которого равен 2.     Пробуем сохранить каждый из делителей. Сохраняем d1 = 7, другой делитель N приобретает видd2 = 11 + 30∙t, где t определяется через разность номеров строк и сохраняемый делительt = (57 — 2)/7 = 7,85. Получили дробное значение, из чего следует, что 7 не является делителем заданного числа 1727. На самом деле можно сразу пробным делением выяснить является ли di делителем заданного числа.     Сохраняем d2 = 11, другой делитель приобретает вид d1 = 7 + 30∙t, где t определяется через разность номеров строк и сохраняемый делитель t = (57 — 2)/11 = 5. Тогда d1 = 7 + 30∙t = 157.Действительно, 1727/157 = 11.     Пример 3.Пусть задано составное нечетное натуральное число (сннч)N = 4294967297, вне пределов таблицы. Требуется факторизовать его. Найдем как и ранее положение этого числа в множестве Т-8: номер строки N/ 30 = 143165576, номер столбца N — 30∙143165576 = 17.В этом же столбце задаем произведение 7∙641 = 4487, номер строки которого равен 149.Пробуем сохранить каждый из делителей. Сохраняем d1 = 641, другой делитель приобретает вид7 + 30∙t, где t определяется через разность строк и сохраняемый делительt = (143165576 — 149)/641 = 143165427/641 = 223347.Значение t = 223347 — целое число, следовательно, 641 — делитель исходного числа N.Действительно, N/d1 = 4294967297:641 = 6700417 — простое число (другой делитель).

© Habrahabr.ru