Алгоритмы факторизации

1. Прямой перебор. В трудах Эрмита, Сильвестера и Чебышева была получена оценка для кол-ва простых чисел, предшествующих числу Х: .

2. Алгоритм Евклида. Все алгоритмы, которые мы будем рассматривать, исп-ют алгоритм нахождения НОД. Наиб. эффективным для нахожд-я НОД явл. алгоритм Евклида:

ЕСЛИа₁=а₂,ТОНОД:=а₁,КОНЕЦ

ИНАЧЕа₁:=max(a₁,a₂), a₂:=min(a₁,a₂)

a₁ целочисленно делится наa₂, остаток заносится вa₃

ЕСЛИа₃=0,ТОНОД:=а₂,КОНЕЦ

а₁:=а₂, а₂:=а₃,ИДТИ НА2

3. Алгоритм Полларда. Пусть p – наим. простой сомножитель факторизуемого числаn, и пусть в рез-те случ. генерирования чисел удалось получить 2 числа а иb, причем а≡b mod p. Тогда (a-b)/p иp=НОД(a-b, n), т.е. факторизациюn можно свести к получ-ю 2-х чисел а иb, дающих при делении наpодинаковые остатки. Однако с большой вер-ю можно получить а иb, не выполняя полного перебора.

Пусть задано число r<p. Оценим вероятность того, что случайно создавr разных чисел, мы получим их все с разными остатками при делении наp. Эта вероятность будет зависеть отr иp: .

(при этом использовалось: ). При ростеr вер-тьV(r,p) падает очень быстро. Если .

Рассмотрим алгоритм порождения псевдослучайных чисел по модулю n:

Инициализация x₀[1,n-1]

(общий шаг). Наk-том шаге, гдеk=1,2,… порождается числоx_k=P(x_k-1), гдеP – полином. В кач-веP можно выбрать разл. ф-ции, напр.,f(x)=x²+1. Используя описанный датчик, порождаем случ. посл-тьx₁,x₂,…,x_k. Последнее числоx_kx_j mod p (гдеj изм-ся отk (?????)). Для осущ-я проверки необх-мо исп-ть след. теорему: Пустьx_k иx_j порождены полиномиальными датчиками, где . x_k (?????????). Тогда дляа>0 верноx_j+ax_k+a mod p

(?????????)

Идея алг-ма Полларда. Из теоремы следует, что для факторизации числа x_k

(???????????)

Инициализация. x₀, k:=0

k:=k+1

Получаем x_k:=P(x_k-1)

Если k – нечёт., то идти к 2

j:=k/2. Найти НОД(n, |x_k-x_j|)

Если НОД=1, идти к 2.

Если НОД<n, тоp:=НОД, Конец

Если НОД делится не только на р, но и на n(????????) идти к 1.

В пп. 4 и 5 алгоритма х₂сравнивается с х₁, разность равна 1. (?????????) Для ускорения работы алгоритма вместо того, чтобы для каждой разн-ти считать НОД, форм-ся произвед-еd=d₁d₂…d_r. После того, как наберетсяrсомножителей, считается НОД(d,n). Обычным рез-том будет НОД=1 и приходится начинать заново. Если же НОД=n, то необх-мо проанализировать все сомнож-лиd, т.к. может оказаться, что один из множителей делится наp, а другой наq (???????????)

Алгоритм факторизации, основанный на сравнимости квадратов

Предположим, что нам удается найти 2 разных по модулю nчислаxиyтаких, чтоx²y² mod n (x>y), тогда мы можем разложитьx²-y²=(x-y)(x+y). n  x²-y², тогдаx²-y² делится наn и еслиn=pq, то может иметь место: 1)pq x-y ; 2) pq x+y; 3) p x-y и q x+y; 4) p x+yи q x-y. Если мы рассматриваем 3) и 4), то находя соответствующий НОД можно факторизоватьn. Рассмотрим подход для факторизации. Базой В назовем мн-во чисел р₀, р₁, р₂,..., р_b, где р₀=-1, а р₁, р₂,..., р_b - этоbштук простых чисел, начиная с 2 в порядке возрастания, т.е. -1, 2, 3, 5, 7, 11, 13, 17,... ПустьL=[n]. Для каждого числаa_i=L+i, гдеi=1, 2,...., вычислимq_i, которое явл-ся наименьшим по абсолютной величине остатком по модулюnчислаа_i².Рассмотрим простой пример: пусть необходимо разложитьn=221, L=14, a₁=L+1=15, q₁=4, q₁=p₁². Степень 2 заносят в соответствующий столбец таблицы и начинаем обрабатыватьа₂=16. Необходимо продолжить таблицу, пока в последнем столбце не окажетсяb+2 прочерков (в нашем примере 6 прочерков).

Таблица.

Степени при множителях из базы (4 столбец) записаны в 4-ом столбце, а также нули в незаполненных клетках, выбираются только строчки, где в последней строке прочерки, образуют матрицу Д размера 5 на 6:

Д=.

Из матрицы Д надо выделить подматрицу Д’из всех столбцов и части строк, чтобы сумма эл-тов в каждом столбце была четной. Это простая задача линейной алгебры. Необходимо заменить в Д все четные числа - 0, а нечетные - 1 и ввести сложение по модулю 2. Все св-ва сохраняются и необходимо найти линейно зависимые строки. Найдем матрицу Д’.F.e. выделим нижние строки, они соответствуют 6, 7 и 8 строке таблицы. 20²(-1237)mod n; 21²-1mod n; 22²(237)mod n. Перемножаем эти сравнения след-щим образом: (202122)²(237)² mod 221; (-43)²43 mod 221. Чтобы найти более удобный вариант ищется другая подматрица Д’,f.e. ее можно составить из строк 3 и 5 матрицы Д, в таблице это будет 5 и 7 строка. 19²(-1)3⁴mod 221; 21²(-1)mod 221. Перемножая эти сравнения: (1921)²9²mod 221; (-43)²9²mod 221, -43=1921-221-221=-43. Теперь необходимо найти НОД: НОД(221, 43-9)=НОД (221, 34)=17; НОД(221, 43+9)=НОД(221, 52)=13. Вывод: 221=1317.