Факторизация методом непрерывных дробей
В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого m m .
Метод непрерывных дробей разработан на основе алгоритма Крайчика и использует непрерывную дробь, сходящуюся к k m {displaystyle {sqrt {km}}} для некоторого целого положительного числа k k . На основе метода непрерывных дробей был построен алгоритм Диксона, по схеме которого, затем, был разработан метод квадратичного решета.
Алгоритм имеет сложность O ( e 2 log m log log m ) = L m [ 1 2 , 2 ] {displaystyle Oleft(e^{sqrt {2log mlog log m}} ight)=L_{m}left[{frac {1}{2}},{sqrt {2}} ight]} , в O и L нотациях.
История
Метод непрерывных дробей был предложен Д. Г. Лемером и Р. Е. Поверсом в 1931 году. Этот метод основывался на идеях Лежандра и Крайчика и предназначался для разложения больших чисел, содержащих 30 и более десятичных разрядов. Однако, полученный метод не применялся из-за трудностей, связанных с его реализацией на настольных арифмометрах.
В конце 1960-х годов Джон Бриллхарт обнаружил, что этот метод хорошо подходит для компьютерного программирования, и совместно с Михаэлем А. Моррисоном, переработал этот алгоритм для ЭВМ в 1975 году.
В 1970-е годы алгоритм факторизации методом непрерывных дробей стал лучшим средством разложения на простые множители с использованием формата многократной точности. Программа, написанная Моррисоном и Бриллхартом, на компьютере IBM 360/91 обрабатывала произвольные 25-значные числа за 30 секунд, а 40-значные числа — за 50 минут. В 1970 году с помощью именно этого алгоритма была произведена факторизация седьмого числа Ферма:
2 2 7 + 1 = 59649589127497217 ⋅ 5704689200685129054721. {displaystyle 2^{2^{7}}+1=59649589127497217cdot 5704689200685129054721.}Метод оставался популярным вплоть до начала 1980-х годов, когда появился метод квадратичного решета. После этого метод факторизации непрерывных дробей оказался неконкурентоспособным.
Описание алгоритма
Метод Лемера и Пауэрса
В 1643 году Пьер Ферма предложил алгоритм разложения на множители нечетного целого числа m m . Кратко этот алгоритм можно описать так: пусть m = a b {displaystyle m=ab} . Тогда, можно записать
a b = ( a + b 2 ) 2 − ( a − b 2 ) 2 = x 2 − y 2 = m {displaystyle ab=left({frac {a+b}{2}} ight)^{2}-left({frac {a-b}{2}} ight)^{2}=x^{2}-y^{2}=m} ,где x = a + b 2 , y = a − b 2 {displaystyle x={frac {a+b}{2}},quad y={frac {a-b}{2}}} .
Отсюда видно, что x 2 − m = y 2 {displaystyle x^{2}-m=y^{2}} . Значит, если последовательно перебирать квадраты целых чисел x x , начиная с ближайшего сверху к m m квадрата, то на некоторой итерации разность x 2 − m {displaystyle x^{2}-m} окажется равна квадрату некоторого числа y y . Найденная пара чисел ( x , y ) (x,y) позволит найти пару множителей ( a , b ) (a,b) числа m m : a = x + y 2 , b = x − y 2 {displaystyle a={frac {x+y}{2}},quad b={frac {x-y}{2}}} .
Таким образом, метод Ферма сводит задачу факторизации числа к поиску целых чисел, разность которых равна исходному числу m m . Метод Ферма быстро находит множители числа m m в том случае, когда его делители близки к m {sqrt {m}} , т.е. для максимально негладких чисел. Если же число m m является гладким, то метод Ферма может работать даже медленней метода пробных делений.
В 1926 году Морис Крайчик в монографии представил свой метод факторизации целых чисел, который представлял собой «усиление» метода Ферма.
Крайчик предложил вместо пар чисел ( x , y ) (x,y) , удовлетворяющих соотношению x 2 − y 2 = m {displaystyle x^{2}-y^{2}=m} , искать пары ( x , y ) (x,y) , удовлетворяющие сравнению x 2 − y 2 ≡ 0 ( mod m ) {displaystyle x^{2}-y^{2}equiv 0{pmod {m}}} , т.е. x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} . Если, при этом, x ≡ ± y ( mod m ) {displaystyle xequiv pm y{pmod {m}}} , то мы получим лишь тривиальное решение. Однако, если x ≢ ± y ( mod m ) {displaystyle x ot equiv pm y{pmod {m}}} , то из указанного сравнения получается x 2 − y 2 = ( x − y ) ( x + y ) = k m {displaystyle x^{2}-y^{2}=(x-y)(x+y)=km} , где k ∈ Z {displaystyle kin mathbb {Z} } . Отсюда тоже следует разложение: m m делится на ( x − y ) ( x + y ) (x-y)(x+y) , но не делится ни на x − y x-y , ни на x + y x+y , следовательно gcd ( x − y , m ) {displaystyle gcd(x-y,m)} — нетривиальный делитель m m (см. #обоснование1).
После нововведения Крайчика алгоритм нахождения делителей числа m m значительно изменялся: теперь по-прежнему нужно вычислять x 2 − m {displaystyle x^{2}-m} для разных x x , однако теперь не требуется «ждать» другой квадрат, а нужно пытаться его построить, перемножая полученные числа m m .
Действительно, рассмотрим последовательность чисел вида υ ( u ) = u 2 − m {displaystyle upsilon (u)=u^{2}-m} (очевидно, υ ≡ u 2 ( mod m ) {displaystyle upsilon equiv u^{2}{pmod {m}}} ). Тогда, если υ ( u 1 ) υ ( u 2 ) … υ ( u k ) = y 2 {displaystyle upsilon (u_{1})upsilon (u_{2})dots upsilon (u_{k})=y^{2}} , т.е. ( u 1 2 − m ) ( u 2 2 − m ) … ( u k 2 − m ) = y 2 {displaystyle (u_{1}^{2}-m)(u_{2}^{2}-m)dots (u_{k}^{2}-m)=y^{2}} , то отсюда следует, что x 2 = u 1 2 u 2 2 … u k 2 ≡ y 2 ( mod m ) {displaystyle x^{2}=u_{1}^{2}u_{2}^{2}dots u_{k}^{2}equiv y^{2}{pmod {m}}} . Для того, чтобы определить, какие именно соотношения нужно перемножить, необходимо раскладывать числа υ upsilon на множители и перемножать соотношения так, чтобы в произведениях υ 1 υ 2 … υ k {displaystyle upsilon _{1}upsilon _{2}dots upsilon _{k}} присутствовали простые множители в четных степенях, позволяющие получить сравнение x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} .
Метод Крайчика сводит задачу разложения числа m m на множители к построению некоторого количества сравнений u 2 ≡ υ ( mod m ) {displaystyle u^{2}equiv upsilon {pmod {m}}} и разложению на множители чисел υ upsilon . Однако Крайчик не предъявил конкретный алгоритм поиска пар чисел u , υ {displaystyle u,upsilon } и алгоритмический способ составления из найденных соотношений сравнения вида x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} .
В 1931 году в работе Лемер и Пауэрс предложили два варианта генерации указанных сравнений. Оба варианта основывались на соотношениях, возникающих при разложении квадратичных иррациональностей в непрерывные дроби, и обладали тем свойством, что величины υ upsilon не превосходили 2 m {displaystyle 2{sqrt {m}}} . Последнее неравенство гарантирует, что числа υ upsilon будут маленькими, что облегчит разложение этих чисел на простые множители(см. #обоснование2).
При этом, оба варианта оказываются эквивалентными: если один вариант алгоритма найдет решение, то и второй вариант также найдет решение.
Однако, у обоих вариантов алгоритма был недостаток — разложение квадратичной иррациональности в непрерывную дробь периодично (теорема Лагранжа). Поэтому количество соотношений, которые можно получить с помощью данного метода, ограниченно, и их может оказаться недостаточно для набора соотношений и построения сравнения x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} . При этом, как показывают практические эксперименты, при больших значениях m m длина периода разложения в непрерывную дробь оказывается достаточно большой (порядка m {sqrt {m}} ) для составления требуемого числа сравнений. В результате при больших m m оба варианта алгоритма всегда находят разложение числа m m на множители.
Первый вариант
Напомним, что каждому действительному числу ξ xi может быть поставлена в соответствие последовательность целых чисел [ b 0 , b 1 , b 2 , . . . ] {displaystyle [b_{0},b_{1},b_{2},...]} , называемая его непрерывной дробью. Это сопоставление строится следующим образом
x 0 = ξ , b i = [ x i ] , x i + 1 = 1 x i − b i , i = 0 , 1 , 2 , … . {displaystyle x_{0}=xi ,quad b_{i}=[x_{i}],quad x_{i+1}={frac {1}{x_{i}-b_{i}}},quad i=0,1,2,dots .}При этом ξ = b 0 + 1 b 1 + 1 b 2 + 1 ⋯ + 1 x n = [ b 0 , b 1 , b 2 , … , b n − 1 , x n ] . {displaystyle xi =b_{0}+{frac {1}{b_{1}+{frac {1}{b_{2}+{frac {1}{dots +{frac {1}{x_{n}}}}}}}}}=[b_{0},b_{1},b_{2},dots ,b_{n-1},x_{n}].}
Если раскладывать в непрерывную дробь число ξ = m {displaystyle xi ={sqrt {m}}} , то возникающие в процессе разложения числа x n x_{n} имеют вид x n = m + A n B n {displaystyle x_{n}={frac {{sqrt {m}}+A_{n}}{B_{n}}}} с целыми A n , B n {displaystyle A_{n},B_{n}} , причем выполняется A n < m {displaystyle A_{n}<{sqrt {m}}} , 0 < B n < 2 m {displaystyle 0<B_{n}<2{sqrt {m}}} .
Для коэффициентов A n , B n {displaystyle A_{n},B_{n}} выполняется равенство:
A n 2 + B n B n − 1 = m . {displaystyle A_{n}^{2}+B_{n}B_{n-1}=m.}Отсюда следует
− B n B n − 1 ≡ A n 2 ( mod m ) , n = 0 , 1 , … . ( 1 ) {displaystyle -B_{n}B_{n-1}equiv A_{n}^{2}{pmod {m}},quad n=0,1,dots .quad quad quad quad (1)}Полученное равенство имеет вид u 2 ≡ υ ( mod m ) {displaystyle u^{2}equiv upsilon {pmod {m}}} , предложенный Крайчиком, и может быть применено для факторизации числа m m .
Вычисляя последовательно частные A 0 , B 0 , A 1 , B 1 , … {displaystyle A_{0},B_{0},A_{1},B_{1},dots } , будем получать выражения вида ( 1 ) (1) для различных n n . Раскладывая величины B n B_{n} на простые множители и комбинируя полученные равенства, можно получить сравнения вида x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} (см. #пример1).
Второй вариант
С каждой непрерывной дробью свяжем последовательность рациональных чисел, состоящую из подходящих дробей P n Q n = [ b 0 , b 1 , … , b n − 1 , b n ] , n > 0 {displaystyle {frac {P_{n}}{Q_{n}}}=[b_{0},b_{1},dots ,b_{n-1},b_{n}],n>0} , вычисляемых по формулам:
P n + 1 = b n + 1 P n + P n − 1 , Q n + 1 = b n + 1 Q n + Q n − 1 , n ⩾ 0 , {displaystyle P_{n+1}=b_{n+1}P_{n}+P_{n-1},quad Q_{n+1}=b_{n+1}Q_{n}+Q_{n-1},quad ngeqslant 0,} P 0 = b 0 , Q 0 = P − 1 = 1 , Q − 1 = 0 {displaystyle P_{0}=b_{0},quad Q_{0}=P_{-1}=1,quad Q_{-1}=0}и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число ξ = m {displaystyle xi ={sqrt {m}}} , то справедливо соотношение:
P n − 1 2 − m Q n − 1 = ( − 1 ) n B n {displaystyle P_{n-1}^{2}-mQ_{n-1}=(-1)^{n}B_{n}} ,из которого следует
P n − 1 2 ≡ ( − 1 ) n B n ( mod m ) , n = 1 , 2 , … . ( 2 ) {displaystyle P_{n-1}^{2}equiv (-1)^{n}B_{n}{pmod {m}},n=1,2,dots .quad quad quad quad (2)}Полученное равенство имеет вид u 2 ≡ υ ( mod m ) {displaystyle u^{2}equiv upsilon {pmod {m}}} и может быть использовано для факторизации числа m m так же, как и в первом варианте.
Алгоритм
Таким образом, исправленный Лемером и Пауэрсом метод Крайчика имеет следующий вид.
Вход. Составное число m m .
Выход. Нетривиальный делитель p p числа m m .
Лемер и Пауэрс в своей работе указали, как можно генерировать соотношения вида u 2 ≡ υ ( mod m ) {displaystyle u^{2}equiv upsilon {pmod {m}}} , однако они, также как и Крайчик, не дали алгоритмического способа составления из найденных соотношений сравнения x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} . Эту проблему решил метод Моррисона и Бриллхарта.
Метод Моррисона и Бриллхарта
В начале 1970-х годов в статье Майкл Моррисон и Джон Бриллхарт предложили свой алгоритм, являющийся модификацией второго варианта алгоритма Лемера и Пауэрса. В настоящее время под методом непрерывных дробей понимают именно алгоритм Моррисона и Бриллхарта.
Основное отличие реализованного Моррисоном и Бриллхартом алгоритма от первоначального варианта заключалось в введении процедуры алгоритмического построения сравнения x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} по заданному множеству сравнений вида u 2 ≡ υ ( mod m ) {displaystyle u^{2}equiv upsilon {pmod {m}}} . Для реализации этой процедуры использовалось понятие «факторной базы».
Будем искать x x как произведение таких чисел u i u_{i} , что наименьший по абсолютной величине вычет числа u i 2 {displaystyle u_{i}^{2}} по модулю m m является произведением простых чисел. Тогда из тех же простых чисел можно построить и y y .
Базой факторизации (или факторной базой) натурального числа m m называется множество B = { p 0 , p 1 , … , p h } {displaystyle B={p_{0},p_{1},dots ,p_{h}}} различных простых чисел p i p_{i} , за возможным исключением p 0 p_{0} , которое может быть равным − 1 {displaystyle -1} . При этом число b b , для которого b 2 mod m {displaystyle b^{2}{mod {m}}} является произведением степеней чисел из множества B B , называется B-гладким числом. Пусть теперь u i u_{i} — B-гладкие числа, υ i = u i 2 mod m = ∏ j = 0 h p j α i j {displaystyle upsilon _{i}=u_{i}^{2}{mod {m}}=prod _{j=0}^{h}p_{j}^{alpha _{ij}}} — разложения их наименьшие по абсолютной величине вычетов по модулю m m . Положим
e i = ( e i 0 , e i 1 , … , e i h ) ∈ F 2 h {displaystyle mathbf {e} _{i}=(e_{i0},e_{i1},dots ,e_{ih})in mathbb {F} _{2}^{h}} ,где e i j ≡ α i j mod 2 {displaystyle e_{ij}equiv alpha _{ij}mod 2} , F 2 h {displaystyle mathbb {F} _{2}^{h}} — векторное пространство над полем GF(2), которое состоит из наборов нулей и единиц размерности h h .
Подберем числа u i u_{i} так, чтобы сумма векторов e i mathbf {e} _{i} была равна нулю. Определим
x = ( ∏ i u i ) mod m , y = ∏ j = 0 h p j γ j {displaystyle x=left(prod _{i}u_{i} ight){mod {m}},quad y=prod _{j=0}^{h}p_{j}^{gamma _{j}}} ,где γ j = 1 2 ∑ i α i j {displaystyle gamma _{j}={frac {1}{2}}sum _{i}alpha _{ij}} . Тогда x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} .
Осталось добавить, что факторная база в алгоритме Моррисона и Бриллхарта состоит из тех простых чисел p i p_{i} , по модулю которых m m является квадратичным вычетом.
Алгоритм
Алгоритм Моррисона и Бриллхарта выглядит следующим образом.
Вход. Составное число m m .
Выход. Нетривиальный делитель p p числа m m .
1. Построить базу разложения B = { p 0 , p 1 , … , p h } {displaystyle B={p_{0},p_{1},dots ,p_{h}}} , где p 0 = − 1 {displaystyle p_{0}=-1} и p 1 , … , p h {displaystyle p_{1},dots ,p_{h}} — попарно различные простые числа, по модулю которых m m является квадратичным вычетом.
2. Берутся целые числа u i u_{i} , являющиеся числителями подходящих дробей к обыкновенной непрерывной дроби, выражающей число m {sqrt {m}} . Из этих числителей выбираются h + 2 {displaystyle h+2} чисел, для которых абсолютно наименьшие вычеты u i 2 {displaystyle u_{i}^{2}} по модулю m m являются B-гладкими:
u i 2 mod m = ∏ j = 0 h p j α i j = υ i {displaystyle u_{i}^{2}{mod {m}}=prod _{j=0}^{h}p_{j}^{alpha _{ij}}=upsilon _{i}} ,где α i j ⩾ 0 {displaystyle alpha _{ij}geqslant 0} . Также каждому числу u i u_{i} сопоставляется вектор показателей ( α i 0 , α i 1 , … , α i h ) {displaystyle (alpha _{i0},alpha _{i1},dots ,alpha _{ih})} .
3. Найти (например, методом Гаусса) такое непустое множество K ⫅ { 1 , 2 , … , h + 1 } {displaystyle Ksubseteqq {1,2,dots ,h+1}} , что ⊕ i ∈ K e i = 0 {displaystyle oplus _{iin K}mathbf {e} _{i}=0} , где ⊕ oplus — операция исключающее ИЛИ, e i = ( e i 1 , e i 2 , … , e i h ) , e i j ≡ α i j ( mod 2 ) {displaystyle mathbf {e} _{i}=(e_{i1},e_{i2},dots ,e_{ih}),e_{ij}equiv alpha _{ij}{pmod {2}}} , 0 ⩽ j ⩽ h {displaystyle 0leqslant jleqslant h} .
4. Положить x ← ∏ i ∈ K u i mod m , y ← ∏ j = 1 h p j 1 2 ∑ i ∈ K α i j mod m {displaystyle xleftarrow prod _{iin K}u_{i}{mod {m}},quad yleftarrow prod _{j=1}^{h}p_{j}^{{frac {1}{2}}sum _{iin K}alpha _{ij}}{mod {m}}} . Тогда x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} .
5. Если x ≢ y ( mod m ) {displaystyle x ot equiv y{pmod {m}}} , то положить p ← gcd ( x − y , m ) {displaystyle pleftarrow gcd(x-y,m)} и выдать результат: p p .
В противном случае вернуться на шаг 3 и поменять множество K K . (Обычно есть несколько вариантов выбора множества K K для одной и той же факторной базы B B . Если все возможности исчерпаны, то следует увеличить размер факторной базы).Из полученного алгоритма впоследствии был разработан алгоритм Диксона, из которого был удален аппарат цепных дробей. После создания алгоритма Диксона, метод непрерывных дробей, по сути, представлял собой алгоритм Диксона, в котором был уточнен выбор абсолютно наименьшего вычета u i u_{i} .
Некоторые улучшения
Пусть m = p ⋅ q {displaystyle m=pcdot q} . Выше в непрерывную дробь раскладывалось число m {sqrt {m}} . Такой вариант эффективен, когда p p и q q близки друг к другу. Однако, чем больше разность между числами p p и q q , тем более трудоемким становится алгоритм. В этом случае вместо m {sqrt {m}} можно раскладывать в непрерывную дробь число k m {displaystyle {sqrt {km}}} , где маленький множитель k k подбирается так, чтобы в базу множителей вошли все малые простые.
Кроме того, так как метод непрерывных дробей построен по схеме алгоритма Диксона, то для него применимы дополнительные стратегии алгоритма Диксона.
Обоснование
Следующая лемма показывает, что если выполнено сравнение x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} и x ≢ y ( mod m ) {displaystyle x ot equiv y{pmod {m}}} , то числа x − y {displaystyle x-y} и m m имеют общие делители.
Лемма(о факторизации). Пусть m m — нечётное составное число и x , y x,y — вычеты по модулю m m такие, что x ≢ ± y ( mod m ) {displaystyle x ot equiv pm y{pmod {m}}} и x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} . Тогда выполняется неравенство 1 < gcd ( x − y , m ) < m {displaystyle 1<gcd(x-y,m)<m} .
Следующие два утверждения — ключевые для алгоритма факторизации методом непрерывных дробей. Они показывают, что можно найти последовательность чисел u i u_{i} , квадраты которых имеют малые вычеты по модулю m m .
Теорема. Если P n Q n {displaystyle {frac {P_{n}}{Q_{n}}}} , где n = 1 , 2 , … {displaystyle n=1,2,dots } , — подходящие дроби к числу α > 1 alpha >1 , которое задано обыкновенной непрерывной дробью, то для всех n n справедлива оценка | P n 2 − α 2 Q n 2 | < 2 α {displaystyle |P_{n}^{2}-alpha ^{2}Q_{n}^{2}|<2alpha } .
Следствие. Пусть положительное число m m не является полным квадратом и P n Q n {displaystyle {frac {P_{n}}{Q_{n}}}} , где n = 1 , 2 , … {displaystyle n=1,2,dots } , — подходящие дроби к числу m {sqrt {m}} . Тогда для абсолютно наименьшего вычета P n 2 mod m {displaystyle P_{n}^{2}{mod {m}}} (т.е. для вычета, расположенного между − m 2 {displaystyle -{frac {m}{2}}} и m 2 {displaystyle {frac {m}{2}}} ) справедливо неравенство | P n 2 mod m | < 2 m {displaystyle |P_{n}^{2}{mod {m}}|<2{sqrt {m}}} , причем P n 2 mod m = P n 2 − m Q n 2 {displaystyle P_{n}^{2}{mod {m}}=P_{n}^{2}-mQ_{n}^{2}} .
Примеры
Пример 1Разложим на множители первым алгоримом Лемера и Пауэрса число m = 1081 {displaystyle m=1081} .
1. Будем раскладывать число ξ = m = 1081 {displaystyle xi ={sqrt {m}}={sqrt {1081}}} в непрерывную дробь и записывать числа A n , B n {displaystyle A_{n},B_{n}} в таблицу для получения уравнений вида u 2 ≡ υ ( mod m ) {displaystyle u^{2}equiv upsilon {pmod {m}}} .
2. Теперь запишем сравнения − B n B n − 1 ≡ A n 2 ( mod m ) {displaystyle -B_{n}B_{n-1}equiv A_{n}^{2}{pmod {m}}} для n = 2 , 3 , 4 , 5 , 6 {displaystyle n=2,3,4,5,6} :
− 2 3 ⋅ 3 ⋅ 19 ≡ 25 2 ( mod 1081 ) , {displaystyle -2^{3}cdot 3cdot 19equiv 25^{2}{pmod {1081}},} − 2 3 ⋅ 3 ⋅ 5 ≡ 31 2 ( mod 1081 ) , {displaystyle -2^{3}cdot 3cdot 5equiv 31^{2}{pmod {1081}},} − 2 4 ⋅ 3 ⋅ 5 ≡ 29 2 ( mod 1081 ) , {displaystyle -2^{4}cdot 3cdot 5equiv 29^{2}{pmod {1081}},} − 2 4 ⋅ 3 2 ⋅ 5 ≡ 19 2 ( mod 1081 ) , {displaystyle -2^{4}cdot 3^{2}cdot 5equiv 19^{2}{pmod {1081}},} − 3 4 ⋅ 5 ≡ 26 2 ( mod 1081 ) . {displaystyle -3^{4}cdot 5equiv 26^{2}{pmod {1081}}.}3. Перемножая четвертое и пятое сравнения, получим:
( − 1 ) 2 ⋅ 2 4 ⋅ 3 2 ⋅ 5 ⋅ 3 4 ⋅ 5 ≡ 19 2 ⋅ 26 2 ( mod 1081 ) , {displaystyle (-1)^{2}cdot 2^{4}cdot 3^{2}cdot 5cdot 3^{4}cdot 5equiv 19^{2}cdot 26^{2}{pmod {1081}},}и, приводя подобные множители и сокращая на 3 2 {displaystyle 3^{2}} :
2 4 ⋅ 3 6 ⋅ 5 2 ≡ 19 2 ⋅ 26 2 ( mod 1081 ) {displaystyle 2^{4}cdot 3^{6}cdot 5^{2}equiv 19^{2}cdot 26^{2}{pmod {1081}}} или 540 2 ≡ 494 2 ( mod 1081 ) . {displaystyle 540^{2}equiv 494^{2}{pmod {1081}}.}4. Получили сравнение вида x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} , используя которое можно найти делитель числа 1081. Действительно, gcd ( 540 − 494 , 1081 ) = 23 {displaystyle gcd(540-494,1081)=23} . Тогда, второй делитель числа 1081 равен 47.
Пример 2Разложим на множители методом Морриса и Брилхарта число m = 21299881 {displaystyle m=21299881} .
1. Строим базу разложения из маленьких простых чисел, выбирая числа, по модулю которых m m является квадратичным вычетом, что проверяется вычислением символов Лежандра:
( m 3 ) = ( m 5 ) = ( m 7 ) = ( m 11 ) = ( m 19 ) = 1. {displaystyle left({frac {m}{3}} ight)=left({frac {m}{5}} ight)=left({frac {m}{7}} ight)=left({frac {m}{11}} ight)=left({frac {m}{19}} ight)=1.}Отсюда, факторная база будет равна B = { − 1 , 2 , 3 , 5 , 7 , 11 , 19 } {displaystyle B={-1,2,3,5,7,11,19}} , h = 6 {displaystyle h=6} .
2. Ищем числители P i P_{i} подходящих дробей к числу m {sqrt {m}} :
m = [ 4615 ; 5 , 1 , 1 , 2 , 1 , 7 , 1 , 27 , 1 , 6 , 1 , 2 , 12 , 23 , 1 , 8 , 2 , 3 , 6 , 1 , 1 , 1 , … ] . {displaystyle {sqrt {m}}=[4615;{5,1,1,2,1,7,1,27,1,6,1,2,12,23,1,8,2,3,6,1,1,1,dots }].}Выбираем те из них, для которых значения P i 2 mod m {displaystyle P_{i}^{2}{mod {m}}} являются B-гладкими. Результаты вычислений записываем в таблицу:
3. Поскольку e 1 ⊕ e 3 ⊕ e 6 ⊕ e 8 = 0 {displaystyle e_{1}oplus e_{3}oplus e_{6}oplus e_{8}=0} , то получаем
4. x = P 2 ⋅ P 6 ⋅ P 18 ⋅ P 24 ≡ 12487442 ( mod m ) {displaystyle x=P_{2}cdot P_{6}cdot P_{18}cdot P_{24}equiv 12487442{pmod {m}}} ,
y = 2 4 ⋅ 3 1 ⋅ 5 1 ⋅ 7 1 ⋅ 11 3 ⋅ 19 0 = 2236080 {displaystyle y=2^{4}cdot 3^{1}cdot 5^{1}cdot 7^{1}cdot 11^{3}cdot 19^{0}=2236080} , x 2 ≡ y 2 ≡ 13201055 ( mod m ) {displaystyle x^{2}equiv y^{2}equiv 13201055{pmod {m}}} .5. Условие x ≢ ± y ( mod m ) {displaystyle x ot equiv pm y{pmod {m}}} выполнено, поэтому вычисляем p = gcd ( x − y , m ) = gcd ( 10251362 , 21299881 ) = 3851 {displaystyle p=gcd(x-y,m)=gcd(10251362,21299881)=3851} .
Поэтому, 21299881 = 3851 ⋅ 5531 {displaystyle 21299881=3851cdot 5531} .
Вычислительная сложность
С появлением криптосистемы RSA в конце 1970-х годов стала особенно важна вычислительная сложность алгоритмов факторизации.
Эвристический анализ времени выполнения алгоритма Морриса и Брилхарта был проведен Р. Шруппелем в 1975 году, хотя не был опубликован.
Более точная оценка(которая при этом все равно оставалась эвристической) была проведена в работе. Приведем результаты оценки сложности в соответствии с этой работой.
При получении оценок в этой работе делаются некоторые эвристические допущения. Например, предполагают, что если помощью алгоритма построено 1 + [ log 2 m ] {displaystyle 1+[log ^{2}m]} пар ( x , y ) (x,y) таких, что x 2 ≡ y 2 ( mod m ) {displaystyle x^{2}equiv y^{2}{pmod {m}}} , то хотя бы для одной из них выполнены неравенства
1 < gcd ( x ± y , m ) {displaystyle 1<gcd(xpm y,m)} .Утверждение. Если a = 1 2 {displaystyle a={frac {1}{sqrt {2}}}} , L = L ( m ) = exp ( ( log m log log m ) 1 / 2 ) {displaystyle L=L(m)=exp((log mlog log m)^{1/2})} и факторная база состоит из p = − 1 {displaystyle p=-1} и всех простых чисел p p таких, что:
2 ⩽ p ⩽ L a , ( m p ) = + 1 {displaystyle 2leqslant pleqslant L^{a},quad left({frac {m}{p}} ight)=+1} ,то при вычислении L b {displaystyle L^{b}} подходящих дробей, где b = a + 1 4 a {displaystyle b=a+{frac {1}{4a}}} , можно ожидать, что алгоритм разложит m m на два множителя с эвристической оценкой сложности L m [ 1 2 ; 2 ] {displaystyle L_{m}left[{frac {1}{2}};2 ight]} арифметических операций.