РОЗПАРАЛЕЛЕННЯ ОБЧИСЛЕННЯ КАНОНІЧНОГО РОЗКЛАДУ ЧИСЛА НА МНОЖНИКИ

  • Ігор Омелянович Процько НУ “Львівська політехніка”
  • Олександр Васильович Грищук ТзОВ “Логіка”
Ключові слова: канонічний розклад, прості множники, залишки, вагові коефіцієнти, потоки, паралельне обчислення

Анотація

В статті розглянуто обчислення канонічного розкладу числа на множники з використанням модифікованого методу пробних ділень. Виконання операцій ділення числа розкладу на прості числа для перевірки на кратність вимагає відповідних часових затрат в сучасних комп’ютерних системах.  Для їх зменшення використовується бінарне подання числа розкладу в процесі його аналізу на кратність. Для кожного розряду бінарного числа розкладу, що дорівнює одиниці, визначаються залишки його вагового коефіцієнта за модулем відповідного простого числа. Отримані значення залишків акумулюються і потім виконується перевірка накопленого значення на рівність з відповідним значенням з множини простих чисел. У випадку рівності отримуємо елемент канонічного розкладу і знову перевіряємо степені цього елемента розкладу на кратність. В протилежному випадку переходимо на наступне більше просте число для подальшої перевірки на кратність, обмежуючись значенням кореня квадратного числа розкладу. Незалежність підзавдань виконання перевірки бінарного подання числа на подільність простими числами дає можливість розпаралелювати виконання розкладу числа в багатоядерних мыкропроцесорах комп’ютерних систем. Серед рівнів паралельності можна послідовно виділити: визначення залишків вагових коефіцієнтів, акумулювання залишків для одиничних розрядів бінарного подання числа розкладу, перевірки на кратність сукупністю простих чисел. Паралельне обчислення розкладу числа досягається виконання алгоритму в багатьох потоках. Програмна реалізація на мові С++, відповідно алгоритму, розподіляє обчислення між потоками, використовуючи пул потоків. В алгоритмі розпаралелення обчислень канонічного розкладу, в залежності від введеного значення числа розкладу, визначається відповідне значення кількості простих чисел та їхніх степенів і рівномірно розподіляється між потоками для виконання аналізу на подільність. В результаті визначено залежність часу обчислення канонічного розкладу числа від кількості потоків в багатоядерних мікропроцесорах лінійки Intel Core i3/i5/i7. Для кожної комп’ютерної системи, що має певну кількість обчислювальних ядер в мікропроцесорах, існує оптимальна кількість потоків, яка забезпечує мінімальний час канонічного розкладу числа на множники.

Біографія автора

Ігор Омелянович Процько, НУ “Львівська політехніка”

к.т.н., доцент, НУ “Львівська політехніка”, кафедра автоматизованих систем управління

Посилання

Y. M. Vynohradov, Osnovy teoryy chysel, yzd. 9-e, pererab. – M.: Nauka, 1981. – 167 s.

V. A. Orlov, N. V. Medvedev, N. A. Shymko, A. B. Domracheva, Teoryia chysel v kryptohrafyy : ucheb. posobye. – M. : Yzd-vo MHTU ym. N. Eh. Baumana, 2011. – 223 s.

The Alternative History of Public-Key Cryptography [Elektronnyi resurs] – Rezhym dostupu: http://cryptome.org/ukpk-alt.htm

Sh. T. Yshmukhametov, Metody faktoryzatsyy naturalnykh chysel: uchebnoe posobye. – Kazan: Ka-zan. un. 2011. – 190 s.

Parallelnaia realyzatsyia y sravnytelnyi analyz alhorytmov faktoryzatsyy s raspredelennoi pamiatiu / Makarenko A.V. Pykhteev A.V. Efymov S.S. [Elektronnyi resurs] – Rezhym dostupu: http://cyberleninka.ru/article/n/parallelnaya-realizatsiya-i-sravnitelnyy-analiz-algoritmov-faktorizatsii-v-sistemah-s-raspredelyonnoy-pamyatyu

Patent 116912 Ukraina, G06F7/04(2006.01), G06F17/10(2006.01). Prystrii kanonichnoho rozkladu chys-la na mnozhnyky / I.O. Protsko, V.M. Tesliuk; Opubl. 25.05.2018, Biul. №10.

Biblioteka CTPL [Elektronnyi resurs ] – Rezhym dostupu: https://github.com/vit-vit/CTPL.

Опубліковано
2019-05-15
Як цитувати
[1]
І. Процько і О. Грищук, РОЗПАРАЛЕЛЕННЯ ОБЧИСЛЕННЯ КАНОНІЧНОГО РОЗКЛАДУ ЧИСЛА НА МНОЖНИКИ, ІТКІ, vol 44, № 1, с. 46-51, Трав 2019.
Розділ
Математичне моделювання та обчислювальні методи