Презентация 5 (2)

1. Алгоритм Диксона (метод факторизации Диксона)

2. Определение

Алгоритм Диксона (или метод факторизации Диксона) — это метод факторизации целых
чисел, предложенный в 1981 году Джоном Диксоном. Он основан на идее нахождения
двух квадратов, сравнимых по модулю факторизуемого нечетного числа N, т.е. найти
такие x и y, что:
• x^2 ≡ y^2(mod n), но x !≡ ±y(mod n)
• x^2 − y^2 ≡ 0(mod n)⇒(x − y)(x + y) ≡ 0(mod n)

3.

В алгоритме факторизации Диксона для поиска нетривиальных
соотношений используется заранее выбранная совокупность простых
чисел, множество таких чисел (p) называется факторной базой. Такие
числа находятся в промежутке ааа
• L – функция L-типа(функция медленного роста),граница гладкости.
• P - простое число
• a - некоторая постоянная, 0 < a < 1
Факторная база обозначается B. B={p ∈ P ∣ 2 ≤ p ≤ L(n)^a}
• Часто в факторную базу вводят число –1

4.

Символом Q(m) мы будем обозначать наименьший неотрицательный вычет в классе m^2
(mod n). Такие значения Q(m) называются B-гладкими.