Приймемо скорочення: натуральний ряд чисел (НРЧ); завдання факторизації великих чисел (ЗФБЧ).
Маніпулювання з натуральними числами можливе як безпосередньо зі значеннями, так і з характеристиками - властивостями чисел. Зручність такого маніпулювання багато в чому визначається моделлю числа. Бажана різноманітність моделей мати обмеженою, а структурна побудова простою. Описи властивостей моделей натуральних чисел (втім, і будь-яких інших чисел) бажано мати в кількісному вираженні, в формалізованому вигляді. Залежність значень показників властивостей від розрядності чисел необхідно усунути, або вибирати властивості вільні від таких залежностей. Будь-яка класифікація у своїй основі має властивості - це елемент формалізації. Основне питання в роботі - факторизація чисел - у зв'язку з чим нижче сформулюємо варіант теореми факторизації натурального числа.
У теоремі йдеться про те, що труднощі факторизації виникають не для всіх чисел, отже, складної процедури факторизації необхідно піддавати не всі числа НРЧ, а тільки їх деяку (меншу) частину. У тексті теореми не говориться, як цю меншу частину формалізувати і зробити зручною для подальшої обробки. Але в роботі якраз і піде мова про формування зручного для обробки уявлення чисел такої меншої безлічі.
Теорема факторизації натуральних чисел
Довільне складене натуральне число N шляхом послідовного виконання над ним деяких елементарних перетворень може бути представлено витвором виду
N = 2t2, 3t3, ^ 5t5, (pk + 30, t), де 0 - ti, i = 2,3,5, t - натуральне, pk > 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 ст.1 10 = 90.
Обсяг кожного класу включає нескінченну безліч натуральних чисел, серед яких є найменше число в класі. Помістимо найменших представників усіх класів у ліву частину таблиці 1, а праворуч її продовжимо, заповнюючи (за зразком ліворуч) клітини таблиць поспіль наступними натуральними числами.
Таблиця 1 - Класи Т (s, ф) чисел з періодом 90. Плоска модель НРЧ
Аналіз вмісту таблиці (безліч чисел Т-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 ст.17 = 49 і 7 ст.111 = 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 класів |T (S, Ф) | = 3 ст.18 перетворюються на сімейство класів, що складається всього з 8 класів, породжуваних кожним представником безлічі р (i). У нових класах числа - елементи йдуть з періодом вже не 90, а в три рази меншим, всього лише 30.
Таблиця 2 - Мультиплікативні підгрупи групи вирахувань (pk) за mod30
Класи формуються з урахуванням флексії та згортки чисел по три пари (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} виділені заливкою
Навіть поверхневий аналіз таблиці дозволяє зробити деякі висновки щодо простоти-складності і можливості факторизації чисел:
- всі ступені всіх генераторів класів, тобто простих чисел - складові;
- рядки з номером кратним генератору в клітці стовпчика цього генератора містять складові числа, ділник яких генератор;
- числа, що належать області заборони простих чисел у спіралі Улама, - складові, приклади таких чисел у першій тисячі: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 класів), найменші представники класів утворюють групу вирахувань за модулем 30 ( (30) = 8). Ця властивість забезпечує визначення номера стовпчика результату твору пари чисел, номери стовпчиків яких відомі. Таблиця Келі групи забезпечує вирішення цього завдання.
Призначення прикладів показує, яка інформація про зв'язки значень чисел, номерів рядків і номерів стовпчиків міститься в безлічі Т- 8.
Один з можливих методів факторизації чисел безлічі Т-8 з використанням таблиці 3.
Приклад 2. Нехай задано складове непарне натуральне число (снч)
N = 1727. Потрібно факторизувати його. Знайдемо розташування цього числа у багатьох Т-8: номер рядка N/30 = 57 (береться ціла частина дробу), номер (ім'я) стовпчика N - 30 ст.157 = 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 - просте число (інший ділник).
