Исходные данные
Пусть задано сравнение
|
((1)) |
Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
Описание алгоритма
1 этап. Пусть
|
|
Сформируем множество
|
|
где q — простые.
2 этап. С помощью некоторого просеивания ищем пары
— такие, что
, и
|
|
(рассматривается абсолютно наименьший вычет). При этом так как
, то
|
|
причём это абсолютно наименьший вычет в этом классе и он имеет величину
. Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.
Логарифмируя по основанию a, получим соотношение
|
|
Мы можем также считать, что a является гладким, то есть
|
|
откуда
|
|
3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём
.
4 этап. Для нахождения x введём новую границу гладкости
. Случайным перебором находим одно значение w, удовлетворяющее соотношению
|
|
u — простые числа «средней» величины.
5 этап. С помощью методов, аналогичных этапам 2 и 3, мы находим логарифмы простых чисел u, возникших на этапе 4.
6 этап. Находим ответ:
|
|
Оценка сложности
Данный алгоритм имеет сложность
арифметических операций. Предполагается, что для чисел
данный алгоритм более эффективен, чем решето числового поля.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .