Прискорення методу квадратичного решета на основі пошуку додаткових В-гладких чисел
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.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2017 Vitalii Misko
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Наше издание использует положения об авторских правах Creative Commons CC BY для журналов открытого доступа.
Авторы, которые публикуются в этом журнале, соглашаются со следующими условиями:
1. Авторы оставляют за собой право на авторство своей работы и передают журналу право первой публикации этой работы на условиях лицензии Creative Commons CC BY, которая позволяет другим лицам свободно распространять опубликованную работу с обязательной ссылкой на авторов оригинальной работы и первую публикацию работы в этом журнале.
2. Авторы имеют право заключать самостоятельные дополнительные соглашения, которые касаются неэксклюзивного распространения работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном хранилище учреждения или публиковать в составе монографии), при условии сохранения ссылки на первую публикацию работы в этом журнале .
