Прискорення методу квадратичного решета на основі пошуку додаткових В-гладких чисел
DOI:
https://doi.org/10.15587/2313-8416.2017.118298Słowa kluczowe:
метод квадратичного решета, додаткові В-гладкі числа, факторна база, інтервал просіюванняAbstrakt
Метод квадратичного решета є найкращим відомим методом факторизації чисел, розміром менше 100 десяткових знаків. Швидкість методу та розмір необхідної пам’яті у багатьох випадках залежить від вдало обраного розміру факторної бази та інтервалу просіювання. У даному дослідженні зображено метод, який дозволяє зменшити розмір факторної бази та інтервалу просіювання без зменшення кількості В-гладких чисел
Bibliografia
Gorbenko, I. D., Dolgov, V. I., Potiy, A. V., Fedorchenko, V. N. (1995). Analiz kanalov uyazvimosti sistemy RSA. Bezopasnost' informatsii, 2, 22–26.
Brown, D. R. L. (2005). Breaking RSA May Be As Difficult As Factoring. Cryptology ePrint Archive. Available at: https://eprint.iacr.org/2005/380
Pomerance, C. (1985). The quadratic sieve factoring algorithm. Lecture Notes in Computer Science, 169–182. doi: 10.1007/3-540-39757-4_17
Lindquist, E. (2001). The Quadratic Sieve Factoring Algorithm. Math 488: Cryptographic Algorithms, Diciembre.
Song, Y. (2009). Quadratic Sieve. Primality Testing and Integer Factorization in Public-Key Cryptography. New York: Springer, 234–239.
Diffie, W., Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22 (6), 644–654. doi: 10.1109/tit.1976.1055638
Shenkhage, A., Shtrassen, V. (1973). Bystroe umnozhenie bol'shikh chisel. Kiberneticheskiy sbornik, 2, 87–98.
Pomerance, C. (1982). Analysis and comparison of some integer factoring algorithms. Mathematisch Centrum Computational Methods in Number Theory, 1, 89–139.
Pomerance, C. (2008). Smooth numbers and the quadratic sieve. Proc. of an MSRI workshop, 69–81.
Crandall, R., Pomerance, C. (2005). Smooth numbers and the quadratic sieve. Prime Numbers A Computational Perspective. New York: Springer, 261–315.
##submission.downloads##
Opublikowane
Numer
Dział
Licencja
Copyright (c) 2017 Vitalii Misko
Utwór dostępny jest na licencji Creative Commons Uznanie autorstwa 4.0 Międzynarodowe.
Our journal abides by the Creative Commons CC BY copyright rights and permissions for open access journals.
Authors, who are published in this journal, agree to the following conditions:
1. The authors reserve the right to authorship of the work and pass the first publication right of this work to the journal under the terms of a Creative Commons CC BY, which allows others to freely distribute the published research with the obligatory reference to the authors of the original work and the first publication of the work in this journal.
2. The authors have the right to conclude separate supplement agreements that relate to non-exclusive work distribution in the form in which it has been published by the journal (for example, to upload the work to the online storage of the journal or publish it as part of a monograph), provided that the reference to the first publication of the work in this journal is included.
