TUB SON NOMZODLARINI DASTLABKI FILTRLASHDA PRIMORIAL SEGMENTLAŞ STRATEGIYALARI VA GEOMETRIK PARAMETRLARNI OPTIMALLAŞTIRIŞ
DOI:
https://doi.org/10.5281/zenodo.23952857Abstract
Mavjud eksperimental ma’lumotlar asosida kiçik tub bölüvçilar böyiça dastlabki filtrlash jarayonida köpаytuvçilar soni, bit uzunligi va geometrik ösiş asosidagi segmentlaş strategiyalari taqqoslandi. Ularning bajariliş vaqtlari mos ravişda 0,091628, 0,100015 va 0,059853 s ni taşkil etdi. Geometrik segmentlaş usuli bajariliş vaqtini mos ravişda 34,68 va 40,16 foizga qisqartirdi. Eng katta umumiy bölüvçini (greatest common divisor, GCD) hisoblaş amallarining örtаça soni mos ravişda 2,9163, 1,9063 va 2,2825 ni taşkil etib, amallar sonining özi bajariliş vaqtini belgilovçi yagona omil emasligini körsatdi. Parametrlarni alohida qidiriş jarayonida boşlanğiç hajm beşga teng bölganda eng kiçik bajariliş vaqti – 0,055368 s qayd etildi. Segmentlaş strategiyasini qöllaş natijasida dastlabki filtrni öz içiga olgan töliq jarayonning bajariliş vaqti 0,514 foizga qisqardi. Olingan natijalar tajribada qayd etilgan konfiguratsiyalarga tegishli bölib, ularni umumlaştiriş uçun takroriy ölçovlar ötkaziş talab etiladi. Kalit sözlar: primorial segment, geometrik segmentlaş, dastlabki filtr, Miller–Rabin, operand uzunligi, erta töxtaş, parametrlarni optimallaştiriş.Keywords
primorial segment, geometrik segmentlaş, dastlabki filtr, Miller–Rabin, operand uzunligi, erta töxtaş, parametrlarni optimallaştirişReferences
Miller, G. L. (1976). Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System Sciences, 13(3), 300–317. https://doi.org/10.1016/S0022-0000(76)80043-8
Rabin, M. O. (1980). Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12(1), 128–138. https://doi.org/10.1016/0022-314X(80)90084-0
Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
Normatov, Sh. B. (2016). Zamonaviy kriptografik algoritmlar uchun katta tub sonlarni generatsiyalash masalalari. Ilim hám jámiyet (Science and Society), (3).
Ahmedova, O. P., & Mardiyev, U. R. (2023). A Method for Improving Milner-Rabin Algorithm to Reduce the Number of False Witnesses. Texas Journal of Engineering and Technology, 18, 31–38.
Mardiyev, U. R. (2025). Analysis of Probabilistic Prime Number Generation Methods and Their Efficiency. International Scientific and Current Research Conferences, 1(01), 192–199.
Solovay, R., & Strassen, V. (1977). A Fast Monte-Carlo Test for Primality. SIAM Journal on Computing, 6(1), 84–85. https://doi.org/10.1137/0206006
Agrawal, M., Kayal, N., Saxena, N., & PRIMES, Is. (2004). in P. Annals of Mathematics, 160(2), 781–793.
Damgård, I., Landrock, P., & Pomerance, C. (1993). Average Case Error Estimates for the Strong Probable Prime Test. Mathematics of Computation, 61(203), 177–194. https://doi.org/10.1090/S0025-5718-1993-1189518-9
Jaeschke, G. (1993). On Strong Pseudoprimes to Several Bases. Mathematics of Computation, 61(204), 915–926. https://doi.org/10.1090/S0025-5718-1993-1192971-8
Maurer, U. M. (1995). Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters. Journal of Cryptology, 8(3), 123–155.
Brandt, J., Damgård, I. B., Landrock, P., & Speeding, Up. (1993). Prime Number Generation. Advances in Cryptology, 739, 440–449.
Brandt, J., & Damgård, I. B. (1993). On Generation of Probable Primes by Incremental Search. Advances in Cryptology, 740, 358–370.
Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective. Springer. https://doi.org/10.1007/0-387-28979-8
Cohen, H. (1993). A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics. Springer. https://doi.org/10.1007/978-3-662-02945-9
Bach, E., & Shallit, J. (1996). Algorithmic Number Theory. Vol. 1: Efficient Algorithms. MIT Press.
Brent, R. P., & Zimmermann, P. (2010). Modern Computer Arithmetic. Cambridge University Press. https://doi.org/10.1017/CBO9780511921698
von zur Gathen J., Gerhard J. Modern Computer Algebra. – 3rd ed. – Cambridge: Cambridge University Press, 2013. – DOI: 10.1017/CBO9781139856065.
Albrecht, M. R., Massimo, J., Paterson, K. G., & Somorovsky, J. (2018). Prime and Prejudice: Primality Testing Under Adversarial Conditions. Proceedings of the, 281–298. https://doi.org/10.1145/3243734.3243787
Kalibera, T., & Jones, R. (2013). Rigorous Benchmarking in Reasonable Time. Proceedings of the, 63–74.
Bellman, R. (1952). On the Theory of Dynamic Programming. Proceedings of the National Academy of Sciences of the United States of America, 38(8), 716–719. https://doi.org/10.1073/pnas.38.8.716
Montgomery, P. L. (1985). Modular Multiplication without Trial Division. Mathematics of Computation, 44(170), 519–521. https://doi.org/10.1090/S0025-5718-1985-0777282-X
Koç, Ç. K., Acar, T., & Kaliski, B. S. Jr. (1996). Analyzing and Comparing Montgomery Multiplication Algorithms. IEEE Micro, 16(3), 26–33. https://doi.org/10.1109/40.502403
Downloads
Published
Issue
Section
License
Copyright (c) 2026 MUHANDISLIK VA IQTISODIYOT
This work is licensed under a Creative Commons Attribution 4.0 International License.
