12.3.3 Алгоритм Бриллхарта -- Моррисона

Этот алгоритм впервые описан в работе [BrMor]. Современную версию с использованием параллельных вычислений см. в [WW]. Алгоритм Бриллхарта -- Моррисона работает так же, как алгоритм Диксона, только вместо случайных используются некоторые числа, вычисляемые с помощью разложения в непрерывную дробь. Кроме того, в факторную базу включаются только те простые числа , для которых является квадратичным вычетом по модулю .

К алгоритму Бриллхарта -- Моррисона применимы методы ускорения, описанные в п. 12.3.2. В работе [Pom82] приведены оценки сложности алгоритма Бриллхарта -- Моррисона (в том числе с методами ускорения), получаемые с помощью некоторых эвристических допущений.