Вычислительная сложность математических операций

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: «Вычислительная сложность математических операций» - новости · газеты · книги · ученый · JSTOR ( апрель 2015 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Графики функций, обычно используемых при анализе алгоритмов, показывающие количество операций в зависимости от размера ввода для каждой функции

N

n

В следующих таблицах приведена вычислительная сложность различных алгоритмов для общих математических операций .

Здесь под сложностью понимается временная сложность выполнения вычислений на многоленточной машине Тьюринга . ^[1] См. Большую нотацию O для объяснения используемых обозначений.

Примечание. Из-за разнообразия алгоритмов умножения ниже обозначена сложность выбранного алгоритма умножения. $M(n)$

Арифметические функции [ править ]

Операция	Вход	Выход	Алгоритм	Сложность
Добавление	Два -разрядного числа, и $n$ $N$ $N$	Один -значный номер $n+1$	Дополнение к учебнику с переноской	$\Theta (n),\Theta (\log(N))$
Вычитание	Два -разрядного числа, и $n$ $N$ $N$	Один -значный номер $n+1$	Вычитание из учебника с заимствованием	$\Theta (n),\Theta (\log(N))$
Умножение	Два -разрядный номер $n$	Один -значный номер $2n$	Учебник длинного умножения	$O(n^{2})$
			Алгоритм Карацубы	$O(n^{1.585})$
			3-полосная Тоом-Кук умножение	$O(n^{1.465})$
			$k$ умножение Тоома – Кука	$O(n^{\frac {\log 2k-1}{\log k}})$
			Смешанный уровень Тоома – Кука (Knuth 4.3.3-T) ^[2]	$O(n\,2^{\sqrt {2\log n}}\,\log n)$
			Алгоритм Шёнхаге – Штрассена	$O(n\log n\log \log n)$
			Алгоритм Фюрера ^[3]	$O(n\log n\,2^{2\log ^{*}n})$
			Алгоритм Харви-Хувена ^[4]^[5]	$O(n\log n)$
Разделение	Два -разрядный номер $n$	Один -значный номер $n$	Учебник с длинным делением	$O(n^{2})$
			Дивизион Бурникеля-Циглера «Разделяй и властвуй» ^[6]	$O(M(n)\log n)$
			Деление Ньютона – Рафсона	$O(M(n))$
Квадратный корень	Один -значный номер $n$	Один -значный номер $n$	Метод Ньютона	$O(M(n))$
Модульное возведение в степень	Два -разрядного число и -битовый показатель $n$ $k$	Один -значное целое $n$	Повторное умножение и сокращение	$O(M(n)\,2^{k})$
			Возведение в степень возведением в квадрат	$O(M(n)\,k)$
			Возведение в степень с редукцией по Монтгомери	$O(M(n)\,k)$

Алгебраические функции [ править ]

Операция	Вход	Выход	Алгоритм	Сложность
Полиномиальная оценка	Один многочлен степени с коэффициентами фиксированного размера $n$	Одно число фиксированного размера	Прямая оценка	$\Theta (n)$
Полиномиальная оценка		Одно число фиксированного размера	Метод Хорнера	$\Theta (n)$
Полиномиальный gcd (больше или ) $\mathbb {Z} [x]$ $F[x]$	Два полинома степени с целочисленными коэффициентами фиксированного размера $n$	Один многочлен степени не выше $n$	Евклидов алгоритм	$O(n^{2})$
Полиномиальный gcd (больше или ) $\mathbb {Z} [x]$ $F[x]$		Один многочлен степени не выше $n$	Быстрый алгоритм Евклида (Лемер) ^[7]	$O(M(n)\log n)$

Специальные функции [ править ]

Многие методы в этом разделе приведены в Borwein & Borwein. ^[8]

Элементарные функции [ править ]

Эти элементарные функции строятся путем составления арифметических операций, то экспоненциальная функция ( ), то натуральный логарифм ( ), тригонометрические функции ( ), и их обратные. Сложность элементарной функции эквивалентна сложности ее обратной, поскольку все элементарные функции аналитичны и, следовательно, обратимы с помощью метода Ньютона. В частности, если любая или в комплексной области может быть вычислена с некоторой сложностью, то эта сложность достижима для всех других элементарных функций. $\exp$ $\log$ $\sin ,\cos$ $\exp$ $\log$

Ниже размер относится к количеству цифр точности, с которой должна оцениваться функция. $n$

Алгоритм	Применимость	Сложность
Серия Тейлора ; повторное сокращение аргументов (например ) и прямое суммирование $\exp(2x)=[\exp(x)]^{2}$	$\exp ,\log ,\sin ,\cos ,\arctan$	$O(M(n)n^{1/2})$
Серия Тейлора; Ускорение на основе БПФ	$\exp ,\log ,\sin ,\cos ,\arctan$	$O(M(n)n^{1/3}(\log n)^{2})$
Серия Тейлора; двоичное разделение + алгоритм битового пакета ^[9]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O(M(n)(\log n)^{2})$
Арифметика-геометрическое среднее итерации ^[10]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O(M(n)\log n)$

Неизвестно, является ли оптимальная сложность для элементарных функций. Самая известная нижняя оценка - тривиальная оценка . $O(M(n)\log n)$ $Ω {\displaystyle \Omega }$ $(M(n))$

Неэлементарные функции [ править ]

Функция	Вход	Алгоритм	Сложность
Гамма-функция	$n$ -цифровой номер	Аппроксимация неполной гамма-функции рядами	$O(M(n)n^{1/2}(\log n)^{2})$
	Фиксированное рациональное число	Гипергеометрический ряд	$O(M(n)(\log n)^{2})$
	$m/24$ , для целого числа. $m$	Арифметика-геометрическое среднее итерация	$O(M(n)\log n)$
Гипергеометрическая функция ${}_{p}\!F_{q}$	$n$ -цифровой номер	(Как описано в Borwein & Borwein)	$O(M(n)n^{1/2}(\log n)^{2})$
Гипергеометрическая функция ${}_{p}\!F_{q}$	Фиксированное рациональное число	Гипергеометрический ряд	$O(M(n)(\log n)^{2})$

Математические константы [ править ]

В этой таблице указана сложность вычисления приближений к заданным константам для правильных цифр. $n$

Постоянный	Алгоритм	Сложность
Золотое сечение , $\phi$	Метод Ньютона	$O(M(n))$
Корень квадратный из 2 , ${\sqrt {2}}$	Метод Ньютона	$O(M(n))$
Число Эйлера , $e$	Бинарное расщепление ряда Тейлора для экспоненциальной функции	$O(M(n)\log n)$
Число Эйлера , $e$	Обращение Ньютона натурального логарифма	$O(M(n)\log n)$
Пи , $\pi$	Бинарное расщепление арктанового ряда в формуле Мачина	$O(M(n)(\log n)^{2})$ ^[11]
Пи , $\pi$	Алгоритм Гаусса – Лежандра	$O(M(n)\log n)$ ^[11]
Постоянная Эйлера , $\gamma$	Метод Суини (приближение через экспоненциальный интеграл )	$O(M(n)(\log n)^{2})$

Теория чисел [ править ]

Алгоритмы теоретико-числовых вычислений изучаются в вычислительной теории чисел .

Операция	Вход	Выход	Алгоритм	Сложность
Наибольший общий делитель	Два -разрядного числа $n$	Одно целое число, состоящее не более чем из цифр $n$	Евклидов алгоритм	$O(n^{2})$
			Бинарный алгоритм GCD	$O(n^{2})$
			Левый / правый k- мерный двоичный алгоритм НОД ^[12]	$O(n^{2}\log n)$
			Алгоритм Стеле – Циммермана ^[13]	$O(M(n)\log n)$
			Управляемый Шёнхаге алгоритм евклидова спуска ^[14]	$O(M(n)\log n)$
Символ Якоби	Два -разрядного числа $n$	$0$ , или $-1$ $1$	Управляемый Шёнхаге алгоритм евклидова спуска ^[15]	$O(M(n)\log n)$
Символ Якоби	Два -разрядного числа $n$	$0$ , или $-1$ $1$	Алгоритм Стеле – Циммермана ^[16]	$O(M(n)\log n)$
Факториал	Положительное целое число меньше, чем $m$	Один -значное целое $O(m\log m)$	Умножение снизу вверх	$O(M(m^{2})\log m)$
			Двоичное расщепление	$O(M(m\log m)\log m)$
			Возведение в степень простых факторов $m$	$O(M(m\log m)\log \log m)$ , ^[17]^[1] $O(M(m\log m))$
Тест на первичность	A -значное целое число $n$	Правда или ложь	Тест на простоту AKS	$O(n^{6})$ ^[18]^[19] или,^[20]^[21] , в предположении гипотезы Агравала $O(n^{6+\varepsilon })$ $O(n^{3})$
			Доказательство простоты эллиптической кривой	$O(n^{4+\varepsilon })$ эвристически ^[22]
			Тест на простоту Baillie-PSW	$O(n^{2+\varepsilon })$ ^[23]^[24]
			Тест на простоту Миллера – Рабина	$O(kn^{2+\varepsilon })$ ^[25]
			Тест на простоту Соловея – Штрассена.	$O(kn^{2+\varepsilon })$ ^[25]
Целочисленная факторизация	Входное целое число A- бит $b$	Набор факторов	Общее числовое поле сито	$O((1+\varepsilon )^{b})$ ^{[nb 1]}
Целочисленная факторизация	Входное целое число A- бит $b$	Набор факторов	Алгоритм Шора	$O(b^{3})$ , на квантовом компьютере

Матричная алгебра [ править ]

На следующих рисунках сложности предполагается, что арифметика с отдельными элементами имеет сложность O (1), как и в случае с арифметикой с плавающей запятой фиксированной точности или операциями с конечным полем .

Операция	Вход	Выход	Алгоритм	Сложность
Умножение матриц	Две матрицы $n\times n$	Одна матрица $n\times n$	Умножение матриц учебника	$O(n^{3})$
			Алгоритм Штрассена	$O(n^{2.807})$
			Алгоритм Копперсмита – Винограда	$O(n^{2.376})$
			Оптимизированные CW-подобные алгоритмы ^[26]^[27]^[28]	$O(n^{2.373})$
Умножение матриц	Одна матрица и $n\times m$ одна матрица $m\times p$	Одна матрица $n\times p$	Умножение матриц учебника	$O(nmp)$
Умножение матриц	Одна матрица и $n\times \lceil n^{k}\rceil$ одна матрица, для некоторых $\lceil n^{k}\rceil \times n$ $k\geq 0$	Одна матрица $n\times n$	Алгоритмы, приведенные в ^[29]	$O(n^{\omega (k)+\epsilon })$ , где оценки сверху приведены в ^[29] $\omega (k)$
Обращение матрицы ^*	Одна матрица $n\times n$	Одна матрица $n\times n$	Исключение Гаусса – Жордана	$O(n^{3})$
			Алгоритм Штрассена	$O(n^{2.807})$
			Алгоритм Копперсмита – Винограда	$O(n^{2.376})$
			Оптимизированные CW-подобные алгоритмы	$O(n^{2.373})$
Разложение по сингулярным числам	Одна матрица $m\times n$	Одна матрица, одна матрица и одна матрица $m\times m$ $m\times n$ $n\times n$	Бидиагонализация и QR-алгоритм	$O(mn^{2}+m^{2}n)$ ( ) $m\geq n$
Разложение по сингулярным числам	Одна матрица $m\times n$	Одна матрица, одна матрица и одна матрица $m\times n$ $n\times n$ $n\times n$	Бидиагонализация и QR-алгоритм	$O(mn^{2})$ ( ) $m\geq n$
Детерминант	Одна матрица $n\times n$	Один номер	Разложение Лапласа	$O(n!)$
			Алгоритм без деления ^[30]	$O(n^{4})$
			LU разложение	$O(n^{3})$
			Алгоритм Барейса	$O(n^{3})$
			Быстрое матричное умножение ^[31]	$O(n^{2.373})$
Обратная подстановка	Треугольная матрица	$n$ решения	Обратная подстановка ^[32]	$O(n^{2})$

В 2005 году Генри Кон , Роберт Кляйнберг , Балаж Сегеди и Крис Уманс показали, что любая из двух различных гипотез подразумевает, что показатель умножения матриц равен 2. ^[33]

^ * Из-за возможностипоблочного инвертирования матрицы, когда инверсияматрицы требует инверсии двух матриц половинного размера и шести умножений между двумя матрицами половинного размера, а также поскольку умножение матриц имеет нижнюю границу операций(),^{[ 34]} можно показать, чтоалгоритм «разделяй и властвуй»,который использует поблочное обращение для инвертирования матрицы, работает с той же временной сложностью, что и алгоритм умножения матриц, который используется внутренне. ^[35] $n\times n$ $Ω {\displaystyle \Omega }$ $n^{2}\log n$

Преобразует [ править ]

Алгоритмы вычисления преобразований функций (особенно интегральных преобразований ) широко используются во всех областях математики, особенно в анализе и обработке сигналов .

Операция	Вход	Выход	Алгоритм	Сложность
Дискретное преобразование Фурье	Конечная последовательность данных размера $n$	Набор комплексных чисел	Быстрое преобразование Фурье	$O(n\log n)$

Заметки [ править ]

^ Эта форма субэкспоненциального времени действительна для всех. Более точная форма сложности может быть дана как $\varepsilon >0$ $O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)$

Ссылки [ править ]

^ a b A. Schönhage, AFW Grotefeld, E. Vetter: Fast Algorithms - A Multitape Machine Implementation , BI Wissenschafts-Verlag, Mannheim, 1994
^ Д. Кнут. Искусство программирования , Том 2. Третье издание, Addison-Wesley 1997.
^ Мартин Фюрер. Более быстрое целочисленное умножение [https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Архивировано 25 апреля 2013 г. в Wayback Machine . Материалы 39-го ежегодного симпозиума ACM по теории вычислений , Сан-Диего, Калифорния, США, 11–13 июня 2007 г., стр. 55–67.
^ Дэвид Харви, Джорис ван дер Хувен Целочисленное умножение за время O (n log n) . (2019).
^ Эрика Кларрайх. 2019. Умножение достигает предела скорости. Commun. ACM 63, 1 (декабрь 2019 г.), 11–13. DOI : 10,1145 / 3371387
^ Christoph Burnikel и Иоахим Циглер Fast Рекурсивный Division Im Stadtwald, D- Саарбрюккен 1998.
^ http://planetmath.org/fasteuclideanalgorithm
↑ J. Borwein и P. Borwein. Пи и AGM: исследование аналитической теории чисел и вычислительной сложности . Джон Вили 1987.
↑ Дэвид и Григорий Чудновские. Приближения и комплексное умножение по Рамануджану. Возвращение к Рамануджану , Academic Press, 1988, стр. 375–472.
^ Ричард П. Брент, Методы определения нуля с высокой точностью и сложность вычисления элементарных функций , в: Analytic Computational Complexity (JF Traub, ed.), Academic Press, New York, 1975, 151–176.
^ Б Ричард П. Брент (2020), The Borwein Brothers, Pi и AGM , Springer Труды по математике и статистике, 313 , Arxiv : 1802,07558 , DOI : 10.1007 / 978-3-030-36568-4 , ISBN 978-3-030-36567-7, S2CID 214742997
^ Дж. Соренсон. (1994). «Два быстрых алгоритма НОД». Журнал алгоритмов . 16 (1): 110–144. DOI : 10.1006 / jagm.1994.1006 .
^ Р. Крэндалл и К. Померанс. Простые числа - вычислительная перспектива . Второе издание, Springer 2005.
Перейти ↑ Möller N (2008). «Об алгоритме Шёнхаге и вычислении субквадратичного целочисленного НОД» (PDF) . Математика вычислений . 77 (261): 589–607. Bibcode : 2008MaCom..77..589M . DOI : 10.1090 / S0025-5718-07-02017-0 .
^ Бернштейн Д. Дж. "Более быстрые алгоритмы для поиска неквадратов по модулю наихудшего случая целых чисел" .
^ Ричард П. Брент; Пол Циммерманн (2010). « Алгоритм для символа Якоби». arXiv : 1004.2091 [ cs.DS ]. $O(M(n)\log n)$
^ Borwein, P. (1985). «О сложности вычисления факториалов». Журнал алгоритмов . 6 (3): 376–380. DOI : 10.1016 / 0196-6774 (85) 90006-9 .
↑ HW Lenstra Jr. и Карл Померанс, « Тестирование первичности с гауссовскими периодами », предварительная версия от 20 июля 2005 г.
^ HW Lenstra мл. и Померанс, « проверки простоты чисел с периодами гауссовых Архивные 2012-02-25 в Wayback Machine », версия от 12 апреля 2011 года.
^ Тао, Теренс (2010). «1.11 Тест на простоту AKS» . Эпсилон комнаты, II: страницы третьего года математического блога . Аспирантура по математике. 117 . Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. DOI : 10,1090 / г / м2 / 117 . ISBN 978-0-8218-5280-4. Руководство по ремонту 2780010 .
^ Ленстра младший, HW ; Померанс, Карл (11 декабря 2016 г.). «Проверка на простоту с гауссовскими периодами» (PDF) . Cite journal requires |journal= (help)
^ Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений . 76 (257): 493–505. arXiv : math / 0502097 . Bibcode : 2007MaCom..76..493M . DOI : 10.1090 / S0025-5718-06-01890-4 . Руководство по ремонту 2261033 . S2CID 133193 .
^ Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 . JSTOR 2006 210 .
^ Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). "Лукас Псевдопреступления" (PDF) . Математика вычислений . 35 (152): 1391–1417. DOI : 10.1090 / S0025-5718-1980-0583518-6 . JSTOR 2006 406 . Руководство по ремонту 0583518 .
^ a b Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты». Теоретическая информатика . 12 (1): 97–108. DOI : 10.1016 / 0304-3975 (80) 90007-9 . Руководство по ремонту 0582244 .
^ Дэви, AM; Stothers, AJ (2013), "Улучшенная оценка сложности умножения матриц", Труды Королевского общества Эдинбурга , 143а (2): 351-370, DOI : 10,1017 / S0308210511001648
^ Vassilevska Williams, Virginia (2011), Разорвать барьер Медник-Винограда (PDF)
^ Ле Галл, Франсуа (2014), «Силы тензоров и быстрое умножение матриц», Труды 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014) , arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L
^ а б Ле Галль, Франсуа; Уррутия, Флорен (2018). "Улучшенное умножение прямоугольной матрицы с использованием тензора Медника-Винограда". В Czumaj, Артур (ред.). Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики (SIAM). DOI : 10.1137 / 1.9781611975031.67 . ISBN 978-1-61197-503-1. S2CID 33396059 .
^ http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf
^ Ахо, Альфред В .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1974), Разработка и анализ компьютерных алгоритмов , Аддисон-Уэсли, теорема 6.6, с. 241
^ JB Fraleigh и RA Beauregard, "Linear Algebra", Addison-Wesley Publishing Company, 1987, p 95.
↑ Генри Кон, Роберт Кляйнберг, Балаш Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. arXiv : math.GR/0511460 . Материалы 46-го ежегодного симпозиума по основам компьютерных наук , 23–25 октября 2005 г., Питтсбург, Пенсильвания, IEEE Computer Society, стр. 379–388.
↑ Ran Raz . О сложности матричного произведения. В материалах тридцать четвертого ежегодного симпозиума ACM по теории вычислений. ACM Press, 2002. DOI : 10,1145 / 509907,509932 .
^ TH Cormen, CE Leiserson, RL Rivest, C. Stein, Введение в алгоритмы , 3-е изд., MIT Press, Кембридж, Массачусетс, 2009, § 28.2.

Дальнейшее чтение [ править ]

Брент, Ричард П .; Циммерманн, Пол (2010). Современная компьютерная арифметика . Издательство Кембриджского университета. ISBN 978-0-521-19469-3.
Кнут, Дональд Эрвин (1997). Искусство программирования. Том 2: получисловые алгоритмы (3-е изд.). Эддисон-Уэсли. ISBN 978-0-201-89684-8.

[26] Эта форма субэкспоненциального времени действительна для всех. Более точная форма сложности может быть дана как $\varepsilon >0$ $O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)$

[Schonhage-1] A. Schönhage, AFW Grotefeld, E. Vetter: Fast Algorithms - A Multitape Machine Implementation , BI Wissenschafts-Verlag, Mannheim, 1994

[2] Д. Кнут. Искусство программирования , Том 2. Третье издание, Addison-Wesley 1997.

[3] Мартин Фюрер. Более быстрое целочисленное умножение [https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Архивировано 25 апреля 2013 г. в Wayback Machine . Материалы 39-го ежегодного симпозиума ACM по теории вычислений , Сан-Диего, Калифорния, США, 11–13 июня 2007 г., стр. 55–67.

[4] Дэвид Харви, Джорис ван дер Хувен Целочисленное умножение за время O (n log n) . (2019).

[5] Эрика Кларрайх. 2019. Умножение достигает предела скорости. Commun. ACM 63, 1 (декабрь 2019 г.), 11–13. DOI : 10,1145 / 3371387

[6] Christoph Burnikel и Иоахим Циглер Fast Рекурсивный Division Im Stadtwald, D- Саарбрюккен 1998.

[7] ttp://planetmath.org/fasteuclideanalgorithm

[8] J. Borwein и P. Borwein. Пи и AGM: исследование аналитической теории чисел и вычислительной сложности . Джон Вили 1987.

[9] Дэвид и Григорий Чудновские. Приближения и комплексное умножение по Рамануджану. Возвращение к Рамануджану , Academic Press, 1988, стр. 375–472.

[10] Ричард П. Брент, Методы определения нуля с высокой точностью и сложность вычисления элементарных функций , в: Analytic Computational Complexity (JF Traub, ed.), Academic Press, New York, 1975, 151–176.

[brent-11] Б Ричард П. Брент (2020), The Borwein Brothers, Pi и AGM , Springer Труды по математике и статистике, 313 , Arxiv : 1802,07558 , DOI : 10.1007 / 978-3-030-36568-4 , ISBN 978-3-030-36567-7, S2CID 214742997

[12] Дж. Соренсон. (1994). «Два быстрых алгоритма НОД». Журнал алгоритмов . 16 (1): 110–144. DOI : 10.1006 / jagm.1994.1006 .

[13] Р. Крэндалл и К. Померанс. Простые числа - вычислительная перспектива . Второе издание, Springer 2005.

[14] Перейти ↑ Möller N (2008). «Об алгоритме Шёнхаге и вычислении субквадратичного целочисленного НОД» (PDF) . Математика вычислений . 77 (261): 589–607. Bibcode : 2008MaCom..77..589M . DOI : 10.1090 / S0025-5718-07-02017-0 .

[15] Бернштейн Д. Дж. "Более быстрые алгоритмы для поиска неквадратов по модулю наихудшего случая целых чисел" .

[16] Ричард П. Брент; Пол Циммерманн (2010). « Алгоритм для символа Якоби». arXiv : 1004.2091 [ cs.DS ]. $O(M(n)\log n)$

[17] Borwein, P. (1985). «О сложности вычисления факториалов». Журнал алгоритмов . 6 (3): 376–380. DOI : 10.1016 / 0196-6774 (85) 90006-9 .

[lenstra_pomerance_2005-18] HW Lenstra Jr. и Карл Померанс, « Тестирование первичности с гауссовскими периодами », предварительная версия от 20 июля 2005 г.

[lenstra_pomerance_2011-19] HW Lenstra мл. и Померанс, « проверки простоты чисел с периодами гауссовых Архивные 2012-02-25 в Wayback Machine », версия от 12 апреля 2011 года.

[tao-aks-20] Тао, Теренс (2010). «1.11 Тест на простоту AKS» . Эпсилон комнаты, II: страницы третьего года математического блога . Аспирантура по математике. 117 . Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. DOI : 10,1090 / г / м2 / 117 . ISBN 978-0-8218-5280-4. Руководство по ремонту 2780010 .

[21] Ленстра младший, HW ; Померанс, Карл (11 декабря 2016 г.). «Проверка на простоту с гауссовскими периодами» (PDF) . Cite journal requires |journal= (help)

[morain-22] Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений . 76 (257): 493–505. arXiv : math / 0502097 . Bibcode : 2007MaCom..76..493M . DOI : 10.1090 / S0025-5718-06-01890-4 . Руководство по ремонту 2261033 . S2CID 133193 .

[PSW-23] Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 . JSTOR 2006 210 .

[lpsp-24] Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). "Лукас Псевдопреступления" (PDF) . Математика вычислений . 35 (152): 1391–1417. DOI : 10.1090 / S0025-5718-1980-0583518-6 . JSTOR 2006 406 . Руководство по ремонту 0583518 .

[monier-25] Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты». Теоретическая информатика . 12 (1): 97–108. DOI : 10.1016 / 0304-3975 (80) 90007-9 . Руководство по ремонту 0582244 .

[27] Дэви, AM; Stothers, AJ (2013), "Улучшенная оценка сложности умножения матриц", Труды Королевского общества Эдинбурга , 143а (2): 351-370, DOI : 10,1017 / S0308210511001648

[28] Vassilevska Williams, Virginia (2011), Разорвать барьер Медник-Винограда (PDF)

[29] Ле Галл, Франсуа (2014), «Силы тензоров и быстрое умножение матриц», Труды 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014) , arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L

[Le_Gall-30] а б Ле Галль, Франсуа; Уррутия, Флорен (2018). "Улучшенное умножение прямоугольной матрицы с использованием тензора Медника-Винограда". В Czumaj, Артур (ред.). Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики (SIAM). DOI : 10.1137 / 1.9781611975031.67 . ISBN 978-1-61197-503-1. S2CID 33396059 .

[31] ttp://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf

[32] Ахо, Альфред В .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1974), Разработка и анализ компьютерных алгоритмов , Аддисон-Уэсли, теорема 6.6, с. 241

[33] JB Fraleigh и RA Beauregard, "Linear Algebra", Addison-Wesley Publishing Company, 1987, p 95.

[34] Генри Кон, Роберт Кляйнберг, Балаш Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. arXiv : math.GR/0511460 . Материалы 46-го ежегодного симпозиума по основам компьютерных наук , 23–25 октября 2005 г., Питтсбург, Пенсильвания, IEEE Computer Society, стр. 379–388.

[35] Ran Raz . О сложности матричного произведения. В материалах тридцать четвертого ежегодного симпозиума ACM по теории вычислений. ACM Press, 2002. DOI : 10,1145 / 509907,509932 .

[36] TH Cormen, CE Leiserson, RL Rivest, C. Stein, Введение в алгоритмы , 3-е изд., MIT Press, Кембридж, Массачусетс, 2009, § 28.2.

[1]