Control Systems and Computers

https://doi.org/10.15407/csc.2022.02.070

Bilyk V.K. Simple and Visual Algorithm for Factorizing Integer Numbers. Control Systems and Computers. 2022. № 2. С. 70-76.

УДК 511       

В.К. Білик, кандидат технічних наук, старший науковий співробітник,
Інститут кібернетики імені В.М. Глушкова НАН України,
03187, м, Київ, просп. Академіка Глушкова, 40, Україна,
BilykVK@gmail.com

ПРОСТИЙ НАОЧНИЙ АЛГОРИТМ ФАКТОРИЗАЦІЇ ЦІЛИХ ЧИСЕЛ

Вступ. Пошук ефективних способів розкладання цілих чисел на прості множники  цікавить  спеціалістів не тільки в області теорії чисел, але й інформатики. Проблема у складності (швидкості ) обчислень.

Ціль статті. Пропонується альтернативній варіант алгоритму з покращеними характеристиками.

Методи. Замість відомих переборних алгоритмів запропоновано спосіб на іншій (ітераційній) основі.

Результати. Запропоновано простий наочний алгоритм розкладання цілих чисел на співмножники, заснований на використанні теореми Вієта для квадратних рівнянь. По-перше відомо, що якщо квадратне рівняння Х² – 2 × В × Х + С = 0 має дійсні корені, то їхня сума
Х₁ + Х₂ =2·В, а добуток Х₁ × Х₂ = С. Використаємо цей факт.

По-друге, з теорії чисел відомо, що найменший, відмінний від одиниці, дільник цілого складеного числа С не перевищує √С. Використаємо те, що √С=1/2 × (Х₁ + Х₂) + Δ, тобто. √С знаходиться між двома цілими числами.

Розглянемо запропонований алгоритм на прикладі розкладання цілого складеного числа С = 51 на його прості цілі співмножники.

1. Обчислюємо √51 = 7,14. Округлимо до найближчого більшого цілого
   = В = 8.
2. Детермінант відповідного квадратного рівняння D = √(В² – С) = √(64 – 51) =3,6 — неціле — переходимо до п.3, а якщо — ціле або нуль, то переходимо до п.4.
3. Замінюємо В на В + 1 і переходимо до п.2.
4. Перевіряємо: якщо Х₁× Х₂ = С, то друкуємо в даному випадку, X₁ = 3 и X₂ =17. Інакше — збій.

У розглядуваному випадку ітераційний процес зупиниться на третій ітерації при В = 10.

В статті розглянуто варіанти скорочення числа ітерацій, аж до однієї.

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

 Завантажити повний текст в PDF (англійською).

Ключові слова: факторизація чисел, прості та складені числа.

1. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие. Казань: Казан. університет, 2011. 200 с.
2. Виноградов І.М. Основи теорії чисел. М .: Наука.1981. 176 с.
3. Shor P. Polynomial – Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Jour. Comp., 1997. Vol. 26. N P. 1484–1509.
4. Семотюк М. В. Про аналітичному методі факторизации складених чисел. Комп’ютерні засоби, мережі та системи. 2013, No 12. С. 5-10.
5. Гусєв В. А., Мордкович А. Г. Математика: Справочные материалы. М.: Просвещение, 1988. 16 с.

Надійшла 30.03.2021