Обчислення факторизації числа в мультипотоковому режимі на кристалі

Abstract

UK: Актуальність. Забезпечення високої швидкодії обчислення комп’ютерними системами класичної задачі факторизації цілочисельного значення на прості множники вимагає розробки ефективних алгоритмічних методів з використанням новітніх інформаційних технологій. Швидке обчислення факторизації чисел для забезпечення високої криптостійкості інформаційних даних, для переходу до багатовимірного подання одновимірних послідовностей інформаційних даних та інших застосувань є достатньо затребуваним в багатьох практичних завданнях. Мета роботи – вдосконалення методу пробних ділень для обчислення факторизації цілочисельного значення з використанням розпараралелення обчислень та ефективного використання обчислювальних ресурсів комп’ютерних систем, що забезпечить швидше обчислення значень простих множників розкладу. Метод. Запропоновано використання залишків кожного розряду бінарного представлення числа факторизації з метою перевірки на подільність в підході виконання пробних ділень на прості числа. Результати. Підсумком дослідження є розроблення програми паралельного виконання факторизації цілочисельного значення в комп’ютерних системах з багатоядерними процесорами. Висновки. У проведеному дослідженні застосовано метод проведення перевірки на подільність з використанням залишків кожного розряду бінарного представлення числа факторизації, що дозволяє в мультипотоковому режимі виконувати розклад числа на множники. Основна ідея застосування належного математичного апарату полягає у використанні залишків цілого показника степеня числа два від простих чисел. В результаті цього виконується операція накопичення значень залишків, яке перевіряється на рівність з відповідним простим числом та його степенів. Можливість мультипотокової програмної організації факторизації числа забезпечує її паралельне виконання в багатоядерних процесорах комп’ютерних систем. EN: Context. Ensuring high-speed calculation by computer systems of the classical task of factorization of integer value on simple factors requires the development of effective algorithmic methods using the latest information technologies. Fast computation of factorization of numbers to provide high cryptocapability of information data, using multidimensional representation of one-dimensional sequences of information data and other applications is sufficiently in demand in many practical tasks. Objective.The purpose of the work is to improve the method of trial divisions to compute the factorization of integer value with using parallelization of computations and efficient use of computing resources of computer systems, which ensures faster computation of the values of prime factors of the decomposition. Method. It is proposed to use the residuals of each digit of the binary representation of the factorization number in order to check for divisibility in the method performing of trial divisions into prime numbers. Results. The result of the study is to develop of a program of parallel execution of the factorization of integer value in computer systems with multi-core processors. Conclusions. In the research, a method of checking for divisibility using the residuals of each digit of the binary representation of the factorization number was applied, which allows for multi-threaded mode to execute the decomposition of the number into the factors. The basic idea of applying the corresponding mathematical apparatus is to use the residuals of the integer exponent of the number two from prime numbers. As a result, the accumulation of residuals is performed, which is checked for equality with the corresponding prime number and its degrees. The possibility of a multithreaded software organization for computing the number factorization ensures its parallel execution in multi-core processors of computer systems.