Method of testing large numbers for primality

Abstract

The current stage of scientific and technological development entails ensuring information security across all domains of human activity. Confidential data and wireless channels of remote control systems are particularly sensitive to various types of attacks. In these cases, various encryption systems are most commonly used for information protection, among which large prime numbers are widely utilized. The subject of research involves methods for generating prime numbers, which entail selecting candidates for primality and determining the primality of numbers. The subject of research involves methods for generating prime numbers, which choice selecting candidates for primality and determining the primality of numbers. The objective of the work is the development and theoretical justification of a method for determining the primality of numbers and providing the results of its testing. The aim to address the following main tasks: analyze the most commonly used and latest algorithms, methods, approaches, and tools for primality testing among large numbers; propose and theoretically justify a method for determining primality for large numbers; and conduct its testing. To achieve this aim, general scientific methods have been applied, including analysis of the subject area and mathematical apparatus, utilization of set theory, number theory, fields theory, as well as experimental design for organizing and conducting experimental research. The following results have been obtained: modern methods for selecting candidates for primality testing of large numbers have been analyzed, options for generating large prime numbers have been considered, and the main shortcomings of these methods for practical application of constructed prime numbers have been identified. Methods for determining candidates for primality testing of large numbers and a three-stage method for testing numbers for primality have been proposed and theoretically justified. The testing conducted on the proposed primality determination method has demonstrated the correctness of the theoretical conclusions regarding the feasibility of applying the proposed method to solve the stated problem. Conclusions. The use of a candidate primality testing strategy allows for a significant reduction in the number of tested numbers. For numbers of size 200 digits, the tested numbers is reduced to 8.82%. As the size of the tested numbers increases, their quantity will decrease. The proposed method for primality testing is sufficiently simple and effective. The first two stages allow for filtering out all composite numbers except for Carmichael numbers. In the first stage, using the first ten prime numbers filters out over 80 percent of the tested numbers. In the second stage, composite numbers with factors greater than 29 are sieved out. In the third stage, Carmichael numbers are sieved out. The test is polynomial, deterministic, and unconditional. Сучасний етап розвитку науки та техніки передбачає забезпечення інформаційної безпеки у всіх сферах людської діяльності. Найбільш чутливими до різноманітних атак є конфіденційні дані та бездротові канали систем дистанційного управління. Для захисту інформації у цих випадках найчастіше використовуються різноманітні системи шифрування, серед яких широко використовуються прості числа великої розмірності. Предметом досліджень є методи побудови простих чисел, які полягають у виборі кандидатів на простоту та визначенні простоти чисел. Метою роботи є розробка та теоретичне обґрунтування методу визначення простоти чисел і надання результатів його тестування. У статті передбачається вирішити такі основні завдання: проаналізувати найбільш уживані та найновіші алгоритми, методи, підходи та засоби визначення кандидатів на простоту серед чисел великої розмірності, запропонувати та теоретично обґрунтувати метод визначення простоти для великих чисел, провести його тестування. Для досягнення мети застосовано загальнонаукові методи: аналіз предметної області та математичний апарат, використано теорії множин, чисел та полів, планування експерименту для організації та проведення експериментальних досліджень. Здобуто такі результати:проаналізовано сучасні методи вибору кандидатів на перевірку великих чисел на простоту, розглянуті варіанти генерації великих простих чисел, виявлені основні недоліки цих методів для практичного застосування побудованих таким чином простих чисел. Запропоновано та теоретично обґрунтовано метод визначення кандидатів для перевірки великих чисел на простоту та триетапний метод для перевірки чисел на простоту. Проведене тестування запропонованого методу визначення простоти показало правильність теоретичних висновків про можливість застосування запропонованого методу для вирішення поставленої задачі. Висновки: Використання стратегії вибору кандидата на простоту дозволяє значно зменшити кількість перевірених чисел. На числах розміром у 200 десятинних знаків кількість чисел для перевірки зменшується до 8,82%. Зі зростанням розміру чисел для перевірки їх кількість буде зменшуватися. Запропонований метод перевірки чисел на простоту достатньо простий та ефективний. Перші два етапи дозволяють відсіяти всі складені числа, за винятком чисел Кармайкла. При цьому на першому етапі при використанні перших десяти простих чисел відсівається більше 80% чисел для перевірки. На другому етапі проводиться відсів складених чисел з складниками більше 29. На третьому етапі відсіюються числа Кармайкла. Тест є поліноміальним, детермінованим та безумовним.