Elliptic Curve Factorization

Данный модуль предназначен для нахождения всех делителей числа (факторизация, разложение на простые множители). В качестве метода факторизации используется алгоритм, предложенный Хендриком Ленстрой в 1987 году.

Установка

PyPI

Установите пакет используя pip (или любой другой менеджер зависимостей)

# pip
pip install pyecf

# poetry
poetry add pyecf

Установка из исходников

Склонируйте репозиторий, и установите зависимости:

git clone https://github.com/NikitaYurasov/ECF.git
cd ECF
# [poetry](https://python-poetry.org/docs/#installation)
poetry install

# или [pip](https://pip.pypa.io/en/stable/installation/)
pip install -r requirements.txt

Использование

from pyecf import LenstraAlgorithm

n = 9671406556917033397649407
algo = LenstraAlgorithm(n)
factors = algo.factorize() # factors - отсортированный список делителей

Или через cli:

pyecf 9671406556917033397649407  # или любое другое число

Описание алгоритма

Пусть требуется найти делить числа . Считаем, что у числа существует делитель (). Сгенерируем тройку чисел для случайной эллиптической кривой над , где и с условием, что кривая не сингулярна (). Случайной точкой на кривой выберем .

Пусть также задано число , обозначающее степень, в которое будем возводить начальную точку : , где и -- некоторые целые положительные числа.

Следующим шагом выполняется возведение в степень на выбранной кривой:

, где операция + определена по следующему алгоритму:

Алгоритм сложения

Требуется сложить две точки и :

1. Если , то ; если , то .

2. Иначе, пусть

   a. Найти . Если , то -- делитель . Конец алгоритма.

   b. Если , то НОД дает Конец алгоритма.

   c. Если , тогда . Требуется найти .

   • Если , -- делитель, конец алгоритма.
   • В противном случае, если , считаем, что , конец алгоритма.
   • Если , то и .

Стоит заметить, что если в ходе алгоритма получается сингулярная кривая, выбор кривой необходимо повторить. Если в ходе алгоритма делитель не нашелся, алгоритм стоит запустить еще раз.

Нахождение всех делителей числа

1. Пусть заданы два массива: пустой массив для простых делителей и массив с составными делителями. На первом шаге, во втором массиве находится число .

2. По всем числам из массива составных делителей пока он не пустой:

   • Берем первое число;
   • Проверяем на простоту (тест Миллера-Рабина): если число простое, заносим его в массив простых чисел, и удаляем первое число из массива составных чисел;
   • Если не простое, проверяем на четность: если число четное, в список простых делителей заносим 2, в список составных - в конец;
   • Если не четное, аналогично проверяем делимость на 3;
   • В противном случае используем алгоритм Ленстры для поиска делителя, пока он не будет найден. Когда делитель найден, добавляем его и в список составных делителей в конец.

3. Результатом алгоритма будут все числа из списка простых делителей.

Скорость работы

Время работы данного алгоритма зависит не от самого факторизуемого числа, а то размера наименьшего делителя.

Время работы: