Прискорення методу квадратичного решета на основі пошуку додаткових В-гладких чисел
DOI:
https://doi.org/10.15587/2313-8416.2017.118298Ключові слова:
метод квадратичного решета, додаткові В-гладкі числа, факторна база, інтервал просіюванняАнотація
Метод квадратичного решета є найкращим відомим методом факторизації чисел, розміром менше 100 десяткових знаків. Швидкість методу та розмір необхідної пам’яті у багатьох випадках залежить від вдало обраного розміру факторної бази та інтервалу просіювання. У даному дослідженні зображено метод, який дозволяє зменшити розмір факторної бази та інтервалу просіювання без зменшення кількості В-гладких чисел
Посилання
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##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2017 Vitalii Misko
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Наше видання використовує положення про авторські права Creative Commons CC BY для журналів відкритого доступу.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
