Elliptic Curve Factorization
Project description
Elliptic Curve Factorization
Данный модуль предназначен для нахождения всех делителей числа (факторизация, разложение на простые множители). В качестве метода факторизации используется алгоритм, предложенный Хендриком Ленстрой в 1987 году.
Использование через скрипт
Склонируйте репозиторий, и установите зависимости используя:
git clone https://github.com/NikitaYurasov/ECF.git
cd ECF
poetry install
- pip
git clone https://github.com/NikitaYurasov/ECF.git
cd ECF
pip install -r requirements.txt
И выполните следующую команду:
python pyecf.py -n 9671406556917033397649407 # или любое другое число
Использование как пакет
Установите пакет используя pip (или любой другой менеджер зависимостей)
pip install pyecf
Внутри проекта использование может выглядеть так:
from pyecf import LenstraAlgorithm
n = 9671406556917033397649407
algo = LenstraAlgorithm(n)
factors = algo.factorize() # factors - отсортированный список делителей
Описание алгоритма
Пусть требуется найти делить числа . Считаем, что у числа существует делитель (). Сгенерируем тройку чисел для случайной эллиптической кривой над , где и с условием, что кривая не сингулярна (). Случайной точкой на кривой выберем .
Пусть также задано число , обозначающее степень, в которое будем возводить начальную точку : , где и -- некоторые целые положительные числа.
Следующим шагом выполняется возведение в степень на выбранной кривой:
, где операция + определена по следующему алгоритму:
Алгоритм сложения
Требуется сложить две точки и :
Стоит заметить, что если в ходе алгоритма получается сингулярная кривая, выбор кривой необходимо повторить. Если в ходе алгоритма делитель не нашелся, алгоритм стоит запустить еще раз.
Нахождение всех делителей числа
-
Пусть заданы два массива: пустой массив для простых делителей и массив с составными делителями. На первом шаге, во втором массиве находится число .
-
По всем числам из массива составных делителей пока он не пустой:
- Берем первое число;
- Проверяем на простоту (тест Миллера-Рабина): если число простое, заносим его в массив простых чисел, и удаляем первое число из массива составных чисел;
- Если не простое, проверяем на четность: если число четное, в список простых делителей заносим 2, в список составных - в конец;
- Если не четное, аналогично проверяем делимость на 3;
- В противном случае используем алгоритм Ленстры для поиска делителя, пока он не будет найден. Когда делитель найден, добавляем его и в список составных делителей в конец.
-
Результатом алгоритма будут все числа из списка простых делителей.
Скорость работы
Время работы данного алгоритма зависит не от самого факторизуемого числа, а то размера наименьшего делителя.
Время работы:
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.