Прискорення методу квадратичного решета на основі пошуку додаткових В-гладких чисел

Автор(и)

  • Vitalii Misko Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164, Україна https://orcid.org/0000-0001-5952-1140

DOI:

https://doi.org/10.15587/2313-8416.2017.118298

Ключові слова:

метод квадратичного решета, додаткові В-гладкі числа, факторна база, інтервал просіювання

Анотація

Метод квадратичного решета є найкращим відомим методом факторизації чисел, розміром менше 100 десяткових знаків. Швидкість методу та розмір необхідної пам’яті у багатьох випадках залежить від вдало обраного розміру факторної бази та інтервалу просіювання. У даному дослідженні зображено метод, який дозволяє зменшити розмір факторної бази та інтервалу просіювання без зменшення кількості В-гладких чисел

Біографія автора

Vitalii Misko, Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164

Аспірант

Відділ автоматизації проектування енергетичних установок

Посилання

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##

Опубліковано

2017-12-30

Номер

Розділ

Технічні науки