# Факторизация NFS: новые надежды

Описан новый алгоритм факторизации целых чисел специального вида методом решета числового поля.

Скачать электронную версию публикации

Загружен, раз: 23

## Ключевые слова

number field sieve, integer factorization, решето числового поля, факторизация целых чисел## Авторы

ФИО | Организация | Дополнительно | |

Кирхнер Пауль | Французский институт исследований в области компьютерных наук и автоматизации | студент | pkirchne@clipper.ens.fr |

## Ссылки

Kluners J. and Pauli S. Computing residue class rings and Picard groups of orders. J. Algebra, 2005, vol. 292, no. 1, pp. 47-64.

Buchmann J. A. and Lenstra H. W. Approximating rings of integers in number fields. J. de theorie des nombres de Bordeaux, 1994, vol. 6, no. 2, pp. 221-260.

Cox D.A. Primes of the Form x2 + ny2: Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, 2011, vol.34.

Adleman L. M. Factoring numbers using singular integers. Proc. 23th Ann. ACM Symp. Theory of Computing, ACM, 1991, pp. 64-71.

Pollard J. M. Theorems on factorization and primality testing. Math. Proc. of the Cambridge Philosophical Soc., Cambridge Univ. Press, 1974, vol.76, no.3, pp. 521-528.

Williams H. C. A p + 1 method of factoring. Math. Computation, 1982, vol.39, no. 159, pp. 225-234.

Bach E. and Shallit J. Factoring with cyclotomic polynomials. Math. Computation, 1989, vol. 52, no. 185, pp. 201-219.

Kirchner P. Algorithms on Ideal over Complex Multiplication Order. arXiv preprint arXiv:1602.09037, 2016.

Schoof R. Computing Arakelov class groups. arXiv preprint arXiv:0801.3835, 2008.

Coppersmith D. Modifications to the number field sieve. J. Cryptology, 1993, vol.6, no.3, pp. 169-180.

Seysen M. A probabilistic factorization algorithm with quadratic forms of negative discriminant. Mathematics of Computation, 1987, vol.48, no. 178, pp. 757-780.

Lenstra H. W. and Pomerance C. A rigorous time bound for factoring integers. J. Amer. Math. Soc., 1992, vol.5, no. 3, pp. 483-516.

Cohen H. A Course in Computational Algebraic Number Theory. Springer Science & Business Media, 2013.

Lemmermeyer F. The Ambiguous Class Number Formula Revisited. arXiv preprint arXiv:1309.1071,2013.

Buhler J. P., Lenstra H. W., and Pomerance C. Factoring integers with the number field sieve. The Development of the Number Field Sieve, Springer, 1993, pp. 50-94.

## Факторизация NFS: новые надежды | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/8