METHOD OF TESTING LARGE NUMBERS FOR PRIMALITY
Article Sidebar
Main Article Content
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.
Article Details
References
Miller, C. and Valasek, C. (2015), Remote Exploitation of an Unaltered Passenger Vehicle, available at: https://illmatics.com/Remote%20Car%20Hacking.pdf
Tweney, D. (2015), FBI says this hacker took over a plane through its in-flight entertainment system, VentureBeat, available at: https://venturebeat.com/security/fbi-says-this-hacker-took-over-a-plane-through-its-in-flight-entertainment-system
Herping, S. (2019), “Securing Artificial Intelligence”, Stiftung Neue Verantwortung, available at: https://www.stiftung-nv.de/de/publikation/securing-artificial-intelligence
Mozhaev, O., Kuchuk, H., Kuchuk, N., Mykhailo, M. and Lohvynenko, M. (2017), “Multiservice network security metric”, 2nd International Conference on Advanced Information and Communication Technologies, AICT 2017 – Proceedings, pp. 133–136, doi: https://doi.org/10.1109/AIACT.2017.8020083
Pupillo, L., Fantin, S., Ferreira, A. and Polito, C. (2021), Artificial Intelligence and Cybersecurity, CEPS Task Force Report, available at: https://www.ceps.eu/wp-content/uploads/2021/05/CEPS-TFR-Artificial-Intelligence-and-Cybersecurity.pdf
Yaloveha, V., Podorozhniak, A. and Kuchuk, H. (2022), “Convolutional neural network hyperparameter optimization applied to land cover classification”, Radioelectronic and Computer Systems, No. 1(2022), pp. 115–128, DOI: https://doi.org/10.32620/reks.2022.1.09
Cao, Weiling, Кosenko, V. and Semenov, S. (2022), “Study of the efficiency of the software security improving method and substantiation of practical recommendations for its use”, Innovative Technologies and Scientific Solutions for Industries, No. 1(19), pp. 55–64, doi: https://doi.org/10.30837/ITSSI.2022.19.055
Semenov, S., Sira, O. and Kuchuk, N. (2018), “Development of graphicanalytical models for the software security testing algorithm”, Eastern-European Journal of Enterprise Technologies, Vol 2, No 4 (92), pp. 39-46, doi: https://doi.org/10.15587/1729-4061.2018.127210
(2021), OSCE SMM Spot Report 8/2021: Forced emergency landing of long-range unmanned aerial vehicle due to dual GPS signal interference, Organization for Security and Co-operation in Europe, available at: https://www.osce.org/special-monitoring-mission-to-ukraine/483149
Knyazev, V., Lazurenko, B. and Serkov, A. (2022), “Methods and Tools for Assessing the Level of Noise Immunity of Wireless Communication Channels”, Innovative Technologies and Scientific Solutions for Industries, No. 1 (19), pp. 92–98, doi: https://doi.org/10.30837/ITSSI.2022.19.092
Merlac, V., Smatkov, S., Kuchuk, N. and Nechausov, A. (2018), “Resourses Distribution Method of University e-learning on the Hypercovergent platform”, Сonf. Proc. of 2018 IEEE 9th Int. Conf. on Dependable Systems, Service and Technologies. DESSERT’2018, Kyiv, May 24-27, pp. 136–140, doi: http://dx.doi.org/10.1109/DESSERT.2018.8409114
Petrovska, I., Kuchuk, H., Kuchuk, N., Mozhaiev, O., Pochebut, M. and Onishchenko, Yu. (2023), “Sequential Series-Based Prediction Model in Adaptive Cloud Resource Allocation for Data Processing and Security”, 2023 13th International Conference on Dependable Systems, Services and Technologies, DESSERT 2023, 13–15 October, Athens, Greece, code 197136, doi: http://dx.doi.org/10.1109/DESSERT61349.2023.10416496
Pevnev, V., Frolov, A., Tsuranov, M. and Zemlianko, H. (2022), “Ensuring the Data Integrity in Infocommunication Systems”, International Journal of Computing, vol. 21(2), pp. 228–233, doi: https://doi.org/10.47839/ijc.21.2.2591
Kovalenko, A. and Kuchuk, H. (2022), “Methods to Manage Data in Self-healing Systems”, Studies in Systems, Decision and Control, Vol. 425, pp. 113–171, doi: https://doi.org/10.1007/978-3-030-96546-4_3
Trubchaninova, K., Serkov, A., Tkachenko, V., Kharchenko, V., Pevnev, V. and Doukas, N. (2020), “Method of Increasing Security of Spatial Intelligence in the Industrial Internet of Things Systems”, 24th International Conference on Circuits, Systems, Communications and Computers (CSCC’2020), Platanias Chania Grete Island, Greece, July 19-22, 2020. рр. 283–289, doi: https://doi.org/10.1109/CSCC49995.2020.00058
Kovalenko, A. and Kuchuk, H. (2022), “Methods to Manage Data in Self-healing Systems”, Studies in Systems, Decision and Control, vol. 425, pp. 113–171, doi: https://doi.org/10.1007/978-3-030-96546-4_3
Diffie, W. and Hellman, M. E. (1976), “New Directions in Cryptography”, IEEE Transactions On Information Theory, vol. 22(6), pp. 644–654, doi: https://doi.org/10.1109/TIT.1976.1055638
Rivest, R.L., Shamir, A. and Adleman, L. (1978), “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, Vol. 21(2), pp. 120–126, doi: https://doi.org/10.1145/359340.359342
Dixon, J. D. (1984), “Factorization and Primality Tests”, The American Mathematical Monthly, 3vol. 91, no. 6 , pp. 333–352, doi: https://doi.org/10.1080/00029890.1984.11971425
Couvreur, C. and Quisquater, J. J. (1982), “An Introduction to Fast Generation of Large Primes Numbes”, Philips Journal of Research, vol. 37, pp. 231–264.
Brillhart, J., Lehmer, D. H. and Selfridge, J. L. (1975), “New Primality Criteria and Factorizations of 2m±1”,Mathematics of Computation, vol. 29, no. 130, pp. 620–647, doi: https://doi.org/10.2307/2005583
Plaisted, D. A. (1979), “Fast Verification, Testing and Generation of Large Primes”, Theoretical Computer Science, vol. 9, pp. 1–16, doi: https://doi.org/10.1016/0304-3975(79)90002-1
(2018), Largest Known Prime Number Has Almost 25 Million Digits, SCI News, News Staff, available at: https://www.sci.news/othersciences/mathematics/largest-prime-number-06751.html
Crandall, R. and Pomerance, C. (2005), Prime Numbers. A computational perspective, Springer, New York, 598 р., available at: http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf
Mimoso, M. (2015), Prime Diffie-Hellman Weakness May Be Key to Breaking Crypto, Threat post, available at: https://threatpost.com/prime-diffie-hellman-weakness-may-be-key-to-breaking-crypto/115069
Agrawal, M., Kayal, N. and Saxena, N. (2004), “PRIMES is in P”, Annals of Mathematics, vol. 160, no. 2, pp. 781–793, doi: https://doi.org/10.4007/annals.2004.160.781
Lenstra, Jr. H. W. and Pomerance, C. (2019), “Primality testing with Gaussian periods”, Journal of the European Mathematical Society, vol. 21, no. 4, pp. 1229–1269, doi: https://doi.org/10.4171/jems/861
Pevnev, V. (2017), “Pseudoprime Numbers: Basic Concepts and the Problem of Security”, ICT in Education, Research and Industrial Applications: Integration, Harmonization and Knowledge Transfer, Proc. of 13th Int. Conf. Kyiv, Ukraine, May 15 18. 2017. Kyiv. 2017. pp. 583 593, available at: https://ceur-ws.org/Vol-1844/10000583.pdf
Pevnev, V. (2018), “Investigation of the algorithm for the numbers primality determining”, Dependable Systems, Services and Technologies: Proc. 9th IEEE Int. Conf., Kyiv, pp. 243–247, doi: https://doi.org/10.1109/DESSERT.2018.8409137