Сравнение x^4 + 1 = 0 (mod p^3)

[maxal]

Для простого числа $p$ решить сравнение

$$x^4 + 1\equiv 0\pmod{p^3}$$

[Руст]

Что значит решить?
Во первых, $p$ должно удовлетворять необходимому условию $p=1\mod 8$. В этом случае для $x=g^{p^2(p-1)/8}\mod p^3$ выполняется равенство при любом образующем g.

[maxal]

Решить - значит, найти все решения.

[Руст]

Указанная формула так же даст все решения.

[maxal]

Руст, указанная формула не считается. С таким же успехом можно было предложить пробежаться по всем вычетам и выбрать те, что удовлетворяют сравнению.

Добавлено спустя 4 минуты 2 секунды:

Для начала неплохо бы было указать, сколько различных решений (по модулю $p^3$) есть у этого сравнения.

[Руст]

maxal писал(а):

Руст, указанная формула не считается. С таким же успехом можно было предложить пробежаться по всем вычетам и выбрать те, что удовлетворяют сравнению.

Добавлено спустя 4 минуты 2 секунды:

Для начала неплохо бы было указать, сколько различных решений (по модулю $p^3$) есть у этого сравнения.

Количество решений бесконечно. Конечно, если ограничится только с $1\le x<p^3$ то их 4.
По видимому вам хочется явное выражение через биномиальный коэффициент. Однако, с алгоритмической точки зрения такое выражение менее эффективно, чем поиск по указанной формуле через образующую.

[RIP]

Можно свести к решению сравнения
$x^2\equiv\left(\frac{p-1}2\right)!\pmod p.$
Если $x_0$ — решение этого сравнения, то решениями исходного сравнения будут $\pm x_0^{p^2},\pm\Bigl(\left(\frac{p-1}2\right)!x_0\Bigr)^{p^2}$.

[maxal]

Перевожу вопрос в алгоритмическую плоскость: указать полиномиальный (по $\log p$) алгоритм для отыскания всех решений указанного сравнения (специально для Руст повторяю: решения рассматриваются по модулю $p^3$ - пассаж о бесконечности не проходит).

[Руст]

maxal писал(а):

Перевожу вопрос в алгоритмическую плоскость: указать полиномиальный (по $\log p$) алгоритм для отыскания всех решений указанного сравнения

Вообщем всё ещё не понятно что вы хотите?
Достаточно найти решения $x^4+1=0\mod p$ и потом если необходимо возвести в степень $p$ или $p^2$. Т.е. с точки зрения алгоритма достаточно найти $x^4+1=0\mod p$. Для этого достаточно найти квадратичный невычет по модулю p g(не обязательно образующую) и возвести в степенрь (p-1)/8 всё это делается за полиномиальное время. Найдя одно решение x находим остальные $x,x^3,x^5,x^7\mod p$.

[maxal]

Руст писал(а):

maxal писал(а):

Перевожу вопрос в алгоритмическую плоскость: указать полиномиальный (по $\log p$) алгоритм для отыскания всех решений указанного сравнения

Вообщем всё ещё не понятно что вы хотите?

Я вроде бы на русском языке четко поставил задачу. В чем непонятки-то?

Руст писал(а):

Достаточно найти решения $x^4+1=0\mod p$ и потом если необходимо возвести в степень $p$ или $p^2$. Т.е. с точки зрения алгоритма достаточно найти $x^4+1=0\mod p$. Для этого достаточно найти квадратичный невычет по модулю p g(не обязательно образующую) и возвести в степенрь (p-1)/8 всё это делается за полиномиальное время. Найдя одно решение x находим остальные $x,x^3,x^5,x^7\mod p$.

Вот теперь решение засчитывается

[Руст]

maxal писал(а):

Руст писал(а):

Я вроде бы на русском языке четко поставил задачу. В чем непонятки-то?

В том то и дело, что условие было сформулировано так, что каждый раз приходилось догадываться что же вы на самом деле хотите?.
1. Не понятно зачем $mod p^3$.
2. Чем не понравилось первоначальное решени?
Вообще то, что найти образующую, что квадратичный невычет всё равно надо перебирать простые q примерно до $N=ln^2p$ и проверить по полиномиальному тесту возведения в степень. Только здесь бесполезна (и не нужна) проверка, что g является образующей.
Однако, гипотеза о том, что проверка до $N=Cln^2p$ достаточно не доказано, доказаны результаты типа $N=C\sqrt p$ как для минимальной образующей так и для минимального квадратичного вычета. Т.е. что указанный алгоритм всегда закончится за полиномиальное время не доказано (на практике эта гипотеза оправдывается). Вроде имеется доказательство о том, что в среднем (по всем простым меньше х) это действительно полиномиальное.
3. С точки зрения решения эта задача эквивалентно более общей: найти примитивные корни х: $x^n=1\mod p^k$. Общая задача решается абсолютно так же. Находится необходимое условие $n|p-1, c=\frac{p-1}{n}$, если $n=p_1^{k_1}...p_m^{k_m}$ то возводим числа a в степень c $x=a^c$ и если для всех $x^{n/p_i}\not =1,i=1,..m$ то x примитивный корень по модулю p. Возводим k-1 раз в p - ую степень по модулю $p^2$ потом по модулю $p^3$ ,... по модулю $p^k$ и получим примитивный корень по модулю $p^k$. Остальные примитивные корни по модулю $p^k$ находятся возведением полученного решения по модулю $p^k$ в степени взаимно простые по модулю n.
Если дадите ответ на указанные вопросы, может пойму смысл вашей задачи.

[maxal]

Руст писал(а):

maxal писал(а):

Я вроде бы на русском языке четко поставил задачу. В чем непонятки-то?

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

У меня аналогичные претенции к вашим решениям - каждый раз приходится догадываться, что вы имели в виду.

Руст писал(а):

1. Не понятно зачем $mod p^3$.

А почему бы и нет? Как автор-постановщик задачи имею право на использование $\bmod p^3$ или любого другого модуля
А вообще именно в таком виде задача разбиралась в журнале Scripta Mathematica, и я не стал ее переиначивать.

Руст писал(а):

2. Чем не понравилось первоначальное решени?

Потому как предложеное множество решений:

$$\{ g^{p^2(p-1)/8}\bmod p^3\mid g - \mbox{образующая}\}$$

подразумевает для точного определения его элементов прогонку по всем образующим, а это крайне неэффективно.

Руст писал(а):

Если дадите ответ на указанные вопросы, может пойму смысл вашей задачи.

Смысл был полностью решить задачу. Какой еще смысл нужен?