Детермінований метод факторизації чисел, заснований на використанні mod 6 і mod 4

О! Скільки нам відкриттів дивних
Готує просвіти дух,
І досвід, син помилок важких,
І геній, парадоксів друг,

І випадок, бог винахідник…
А. С. Пушкін

Замість вступу
Сподіваюся представити рішення проблеми факторизації чисел, заснованого на використанні mod 6 і mod 4, що дозволило знайти закономірності перекладу квадратичних залежностей в лінійні.

На підставі знайденої закономірності була написана методика, яка, на думку автора, при написанні програми, відкриває можливість значно знизити тимчасові витрати при факторизації чисел при використанні не детермінованих імовірнісних методів математики.

За даною методикою була написана програма програмістом — самоучкою Білих Сергієм Олексійовичем, яка показала її ефективність. На жаль, вона не адаптована до великих чисел. Методика написана як алгоритм для складання програми, з роз'ясненнями. Алгоритм представлений у табличному варіанті.

Кожна таблиця складена для одного з 16 можливих варіантів. Чому з 16? Для відповіді на дане запитання і отримати додаткові пояснення за методикою пройдіть під кат.

Звернемося до таблиці, що містить числа першого числового ряду, номери яких приймають вигляд: N= 6*xy+x+y:

Таблиця 1 (А)

y\x 1 2 3 4
1 8 15 22 29
2 15 22 41 54
3 22 41 54 79
4 29 54 79 104
Таким чином можемо заповнити будь-які клітини таблиці. Отже, число L 1, номер якого N1 знаходиться в таблиці 1(А), можна представити у вигляді:

L1 = 6 ( 6xy + x + y) + 1,

де N1 = 6 xy + ( x + y ).

При цьому обидві координати числа даної таблиці позитивні, але можуть бути як парні, так і непарні. Звертаємо на це увагу, так як четнось координат, як і знак перед ними, впливає на алгоритм розрахунку кореляційних залежностей між координатами системи координат, складеної за mod 6, і координатами системи координат, складеної за mod 4. А в наслідок цього і на розрахунок кореляційної залежності між номери чисел, розрахованих за цим модулів. Це і є головними ознаками, що викликають відмінності при факторизації розглянутих варіантів.

Отже, номери рядків таблиці – координати, знак яких залежить від номера розглянутої таблиці, як і номери стовпців. Різниця між номерами сусідніх чисел за рядками константа. Різниця між приростами за рядками також. Для таблиць, складених за mod 6, ця величина дорівнює 6. Для таблиць, складених за mod 4, ця величина дорівнює 4.

Якщо при складанні таблиці 1(А) значення перших величин для розрахунку: 1,2, 3,4, 5,6..., то при складанні таблиці для чисел першого допоміжного числового ряду, номер якого виражається як: N sub>3=6xy-x-y: -1,-2,-3,-4,-5,-6…

Таблиця 3 ©

y\x 1 2 3 4
-1 4 9 14 19
-2 9 20 31 42
-3 14 31 48 65
-4 19 42 65 88
Для чисел другого допоміжного ряду отримуємо:

Таблиця 2 (B)

y\x 1 2 3 4
1 6 11 16 21
2 13 24 35 46
3 20 37 54 71
4 27 50 73 96

Таблиця 4 (D)

y\x 1 2 3 4
-1 6 13 20 27
-2 11 24 37 50
-3 16 35 54 73
-4 21 46 71 96
За аналогією розраховуються і таблиці для другого числового допоміжного ряду по mod 4.

Переходимо до розгляду конкретного прикладу.

Номери числа, розраховані по використовуваних модулів, можуть належати як одному і тому ж квадранту з використовуваної системі координат, так і до різних квадрантам. Але при цьому завжди знаходяться в строгій кореляційно залежністю між собою.

Також в суворій кореляційної залежності знаходиться і твір координат, їх суми, і їх різниці, розраховані за даними модулів.

Розглянемо закономірності методики на прикладі L=10525. Визначаємо, до якого допоміжного числового ряду належить дане число. Умовою, що визначає приналежність до числа першого або другого числового допоміжному ряду, є належність до +1 класу вирахувань даного числа по mod 6, або до -1 класу вирахувань по mod 6.

N6 = (10525-1)/6=1754;

Число відноситься до першого допоміжного класу чисел, значити може належати або першої (А), третя © таблиць.

Наступним етапом є визначення: яку парність можуть мати координати даного числа? Востаннє номер числа парний, то в цьому варіанті обидві координати можуть мати однакову парність. Припускаємо, що обидві координати – парні. У цьому варіанті коефіцієнт переведення величини (x+y) (коригуюча величина), розрахованої за mod 6 значення коригуючої величини, розрахованої за mod 4 дорівнює 3/2 (k6). Цей коефіцієнт запам'ятовуємо для зіставлення числових рядів коригувальних величин, розрахованих за mod 6 і mod 4. На підставі номери числа по mod 6, розраховується числовий ряд коригуючих величин за mod 6, з інтервалом, рівним 6-ти. Першим значенням числового ряду є клас вирахувань, до якого належить номер розглянутого числа по mod 6:

1754:6=292*6+2.

На підставі отриманого залишку, з урахуванням знака, складаємо числовий ряд коригуючих величин за mod 6, з інтервалом 6:

2 8 14 20 26 32 38 44 ... (1)
 

Тепер визначаємо номер числа по mod 4 (аналогічно визначенню номери числа по mod 6):

N4=(10525-1)/4=2631;

На підставі номери числа по mod 4, розраховуємо числовий ряд коригуючих величин за mod 4 з інтервалом, рівним 4. Першим значенням числового ряду є клас вирахувань, до якого належить номер розглянутого числа по mod 4:

2631:4 =657*4+3.

На підставі отриманого залишку, з урахуванням знака, складаємо числовий ряд коригуючих величин за mod 4, з інтервалом 4:

3 11 15 19 23 27 31 35 39 43...
 

На підставі коефіцієнта кореляції 1/k6, переводимо значення числового низки коригувальних величин, розрахованих за mod 4, коригувальні величини за mod 6:

2 4,666 7,333 10 12,666 15,333 18 20,666 26 ... (2)
 

На підставі зіставлення числових рядів (1) і (2), будуємо числовий ряд коригуючих величин, розрахованих за mod 6, з інтервалом 24:

2 26 50 74 98 ... 
 

Тепер, ми маємо всі необхідні дані для побудови числового ряду Дискрименант, на підставі числового низки коригувальних величин, розрахованих по модулю, вже 24. І, якщо ми вгадали з варіантом, і розглянуте число не просте, використання одного з отриманого числового ряду обов'язково забезпечить визначення цілочисельних координат розглянутого числа.

Дійсно, на підставі номери числа і конкретної коректує величини можемо визначити передбачуване твір координат і далі за формулою:

D=(x+y)^2/(2^2)-4*xy;

В результаті, отримуємо:

-291 -119 341 1089 2125 3449 5061 6961 
 

Аналіз закономірностей привів до результатів, для розгляду яких використовуємо розгляд даних таблиці 10-1. Розглянемо дані таблиці шляхом розгляду як стовпців і рядків, так і результатів у клітинках.

У першому, другому і третьому стовпцях знаходяться змінені, покроково, коригувальні величини (aі), використовувані для розрахунку по конкретному Дискрименанту., для першого, другого і третього.

Коригування для першого стовпця здійснюється покроково, починаючи з першої коректує величини на величину, рівну -4;

Для другого стовпця, величина кроку коригування збільшена на 24. За аналогією, і для третього стовпця. Четвертий, п'ятий і шостий стовпці розраховані за формулою:

Dі-[(aі)/2]2 (і)

По кожній розглянутій рядку.

Сьомий стовпець – різниця (Р) між двома розрахованими, з урахуванням коригування коригувальних величин, сусідніми значеннями по конкретній рядку.

Восьмий стовпчик – приватне від ділення першого розрахованого скоригованого значення Дискримінанта на різницю (Р), по конкретній рядку.
При цьому, цілочисельне приватне на підставі коректує величини, яка використовується при розрахунках, і кроку, рівного 24, дозволяє визначати і коригувальну величину, рівну сумі координат, і величину y, відповідних даного числа. У наведеному прикладі 2 -3*24 = — y; 2 – (-3*24) = 74 = (x+y).

Не думайте, що я дам відповіді на всі питання. Погодимося, що відповіддю, на даний момент, є існуючі закономірності. Без додаткових розрахунків істинний відповідь утруднений. А для розрахунків потрібна програма, що дозволяє вносити зміни для відповіді на виникаючі питання

Таблиця 10-1

y\x 1 2 3 4 5 6 7 8
1 2 26 50 -292 -288 -284 4 -73
-2 22 46 -292 -240 -188 52 52 -5,615
3 -6 18 42 -300 -200 -100 100 3
4 -10 14 38 -316 -168 -20 148 -2,135
Анотація до методики
На підставі використання допоміжних числових рядів по mod 6 і по mod 4. з натурального ряду чисел, виокремити складові числа і розбиті на 16 груп (варіантів). Шляхом зіставлення паралельних розрахунків, отримана можливість визначати: належить чи ні розглянуте число до передбачуваної групі складених чисел (ймовірного варіанту).

При аналізі числа для визначення, чи просте воно чи ні, максимальна кількість розрахунків дорівнює 4-м. Варіант розрахунку розглядається нижче. Для кожної групи чисел складені алгоритми розрахунку, формалізують аналіз чисел. Для знаходження співмножників розглянутого числа, розроблений альтернативний спосіб вирішення квадратного рівняння з двома невідомими. Методика заснована на знайденої закономірності перекладу квадратичних залежностей в лінійні, що значно знижує при розрахунку тимчасові витрати.

Альтернативний спосіб вирішення квадратного рівняння полягає в тому, що на відміну від традиційного способу, де рішення шукається за допомогою підбору Дискримінанта, і послідовного вилучення коренів квадратних, в пропонованому способі, рішення шукається за допомогою цілочисельний сумірності скоригованих Дискримінант (Dі) і різниці між ними (D(i+1)-Dі), за допомогою знаходження цілочисельного приватного при поділі першої величини на другу.

Такий підхід дозволяє використовувати при аналізі значної кількості розрахунків початкові, незначні за величиною значення. По кожному з варіантів розрахунку складена програма, що використовує можливості електронних таблиць Excel. На думку автора, методика після написання програми дозволить знаходити нові закономірності в теорії чисел, що має вплинути, додатково, на зниження тимчасових витрат при факторизації чисел.

Стан питання (вступ до методики)
Проблема дійсного розкладання даного числа на прості множники одна з найважчих задач математики. У третьому сторіччі до н.е. Эрастофен запропонував метод знаходження всіх простих чисел менших даного межі А. Після деякого вдосконалення у початку 20 століття Бруном, цей спосіб досі є єдиним способом вирішення даної задачі без використання обчислювальних пристроїв. Інші спроби знайти закони розподілу простих чисел не дали значних результатів.

Пропонована робота є викладом рішення цієї задачі, на підставі законів розподілу складових чисел. Робота полягає в пошуку ознак відмінності простих чисел від непростих, і використання цих ознак для визначення: просте розглянуте число чи ні. Рішення цієї задачі зведено нами до вирішення квадратного рівняння з 2 – я невідомими. Зазвичай такі рівняння вирішуються шляхом підбору одного з невідомих, в нашому випадку k, але цей спосіб, незважаючи на те, що крок прорахунку нами збільшено до 24 – х, достатньо трудомісткий для великих чисел.

Недолік методу

Затруднительность і трудомісткість без використання програмного забезпечення ПК.

Достоїнство методу

Можливість використання ПК і програмного забезпечення, незалежно від кількості знаків у розглянутому числі. У пропонованій роботі створена, на нашу думку, хороша лабораторна база, придатна для вирішення різних завдань з області теорії чисел, наприклад, вирази куба цілого числа, як суми доданків першого та другого ступенів. Нам відомо, що при перемножении чисел зі значною кількістю розрядів допомогою групи ПК, можуть пропадати розряди. Розроблена методика не вимагає використання групи ПК, так як для обчислень використовуються числа з незначною кількістю розрядів. Єдине тривалий обчислення, в якому залишається необхідність – це ділення числа.

Проблеми з написанням програми по розглянутій методиці привели автора до думки, що не погано б спробувати пояснити у більш скороченому викладі принципи, закладені в методиці. Адже ця спроба, можливо, зацікавить не тільки програмістів, але і математиків, не знайомих з знайденої закономірністю.

Тому, спроба такого викладу грунтується і на тому, що розгляд одного з варіантів методики має забезпечити пояснення всієї роботи, і, також, знайденої закономірності, яка може стати в нагоді і не програмістам. При з'ясуванні змісту роботи всі частини методики порівнянні для розуміння.

Мета написання методики
Основна задача пропонованої роботи зводиться до того, щоб визначити, просте дане число L, або воно є витвором хоча б 2-х простих співмножників, не рівних 1. Надалі під словом «кількість» завжди розуміємо ціле невід'ємне число, якщо не обумовлено протилежне. На першому етапі ми застосували метод порівняння за модулем.*

Будь-яке число L може бути представлено у формі:

L = m N + r,

де:
m — заданий модуль;
N — ми назвали номером числа;
r — залишок (може бути позитивним, негативним і рівним 0), r знаходиться в межах від — (m — 1) (m — 1) (При m = 6 від — 5 до + 5).

Ми вибираємо m = 6. Це дає нам можливість виключити з нескінченного ряду чисел, що підлягають нашого аналізу, числа, в яких присутні множники 2, 3 і 6, так як наявність цих співмножників у числі легко розпізнається. Всі числа, що підлягають аналізу, нами іменуються труднораспознаваемыми.

Щодо модуля 6 всі натуральні числа розподіляються на 6 класів, в залежності від залишку:

1) r = 0. L = 6 N (тобто всі числа цього класу і складають самий модуль M)
2) r = 1; L = 6 N + 1, що рівнозначно r = -5; L = 6N – 5.
3) r = 2; L = 6 N + 2, що рівнозначно r = -4; L = 6N – 4.
4) r = 3; L = 6 N + 3, що рівнозначно r = -3; L = 6N – 3.
5) r = 4; L = 6 N + 4, що рівнозначно r = -2; L = 6N – 2.
6) r = 5; L = 6 N + 5, що рівнозначно r = -1; L = 6N – 1.
— * Модулем М називається система всіх чисел, кратних даного числа m. Число m — найменше число даного модуля М. Якщо числа a і b при діленні на m дають однакові залишки, то вони називаються порівнянними по модулю m. Це записується так:

a Ξ b .( mod m)

Таке співвідношення між a і b називається порівнянням по модулю m. Всяке число порівнянне по модулю m зі своїм залишком від ділення цього числа на m. Наприклад: якщо a при діленні на m дає залишок 1, означає:

a Ξ 1; ( mod m )

якщо до a необхідно додати 1, щоб сума ділилася на m, то

a Ξ -1; ( mod m )

У цьому випадку -1 називаємо «негативним залишком». Для нас становлять інтерес числа двох класів:

L(+1) = 6N + 1; L(+1) Ξ 1 ( mod 6) [ 1 ],

ми назвали їх числами гілки (+1);

L(-1) = 6N – 1; L(-1) Ξ -1 ( mod 6) [ 2],.

ми назвали їх числами гілки ( — 1).

Ці непарні числа, що не діляться ні на 3, ні на 6; тобто це труднораспознаваемые числа. За аналогією розглядається число і при використанні mod 4.

Складання таблиць, які включають номери всіх непростих чисел 1-го допоміжного числового ряду
Щоб систематизувати всі непрості числа натурального числового ряду, складено 4 таблиці. Для компактності в таблиці ми вносимо не самі числа L, а їх номери N. При необхідності, знаючи N, можемо за формулами [1], [ 2] обчислити L. І навпаки: по заданому L можемо обчислити його номер N. Всі таблиці складені за принципом таблиці Піфагора.

Розглянемо характеристики, загальні для всіх таблиць. В нульовий рядку кожної таблиці нумеруем стовпці: 1, 2, 3, 4,… У стовпці кожної таблиці нумеруем рядка: 1, 2, 3, 4…

Зразок таблиці:
y\x 1 2 3 4 yі
1 x
2 x
3 x
4 x
... x
xі Nі
Нульові рядок і стовпець кожної таблиці приймемо за осі координат, позначивши їх y та x. Це твердження засноване на тому, що всі складові числа розташовуються в чотирьох таблицях (квадрантах заданої системи координат). Номери рядків і стовпців, розташовані на осях координат, є координатами чисел розглянутого числового ряду з відповідним знаком (координати номерів N є і координатами чисел L).

Візьмемо в будь-якій клітині таблиці номер Nі L і. Координатами номера N і (і числа L і) є xі, y і. Число Lі є добутком X і і Y і. Запишемо це у формалізованому вигляді:

Lі = X іі, де Хі = 6 xі ± 1; У і = 6 уі ± 1 [ 3 ]
Lі = 6 Nі ± 1.

Nі i внесено в таблицю (див. зразок таблиці).

* у таблиці виділені клітини, для яких x = y. Ці клітини складають головну спадну діагональ кожної таблиці. Вона бере початок від x = y = 1 і триває до нескінченності.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.