Факторизация методом непрерывных дробей

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм факторизации целых чисел. Это алгоритм общего вида, пригодный для факторизации произвольного целого n.

Метод непрерывных дробей основывается на алгоритме Диксона и использует непрерывную дробь, сходящуюся к \sqrt{kn} для некоторого целого положительного числа k. Поскольку \sqrt{kn} является квадратичной иррациональностью, его непрерывная дробь является периодичной (если n не квадрат, но в этом случае разложение очевидно).

Алгоритм имеет сложность O\left(e^{\sqrt{2\log n \log\log n}}\right)=L_n\left[1/2,\sqrt{2}\right], в O и L нотациях.[1]

История[править | править вики-текст]

Метод непрерывных дробей был предложен Д. Г. Лемером и Р. Е. Поверсом в 1931 году,[2] и переработан в алгоритм для компьютера Михаэлем А. Моррисоном и Джоном Бриллхартом в 1975 году.[3]


Примечания[править | править вики-текст]

  1. Pomerance, Carl. A Tale of Two Sieves (December 1996), стр. 1473–1485.
  2. Lehmer, D.H.; Powers, R. E. (1931). «On Factoring Large Numbers». Bulletin of the American Mathematical Society 37 (10): 770–776. DOI:10.1090/S0002-9904-1931-05271-X.
  3. Morrison, Michael A.; Brillhart, John (January 1975). «A Method of Factoring and the Factorization of F7». Mathematics of Computation (American Mathematical Society) 29 (129): 183–205. DOI:10.2307/2005475. Проверено 2007-05-13.