число решений сравнения - ?

dragan24

Требуется найти число решений сравнения a^2+b^2+c^2+d^2=0 (mod p) в поле из p элементов.
p - простое.
/* Так как поле из р эл-тов при простом р изоморфно кольцу вычетов по модулю р, то считаем, что элементы поля - это 0, 1, ... , р-1.
Операции сложения, умножения определены стандартным образом (взятые по модулю р). */
//hint: число решений сравнения a+b+c+d=0 (mod p) известно: p^3.

emboweler

ответ при p>2 p(p^2+p-1). для p=2 уже написан (p^3).
геометрическое решение:
выкинем точку (0,0,0,0) из нашего множества, тогда получим квадрику в проективном пространстве FP3. Что на ней есть хотя бы одна точка должно быть очевидно. Тогда через эту точку проведем все прямые, не лежащие в касательной плоскости, получим P2\setminus P1, то есть p^2 прямых, на каждой еще по одной точке. И кроме того пересечение с касательной плоскостью есть пара проективных прямых - это еще 2p+1 точка. Получаем p^2+2p+1 точку. Вот теперь это мы умножаем на p-1, за счет того, что посчитали точки в проективном пространстве, а когда-то начинали в аффинном. и добавляем 1.
Решение на основе моих слабых знаний по ТЧ далее:
сначала найдем кол-во решений сравнения a^2+b^2=const
------------
у a^2+b^2=0 -- их либо 1, либо 2p-1
соответственно у a^2+b^2=k
либо (p+1)/2, либо (p-1)/2
----------------
и если p=4k-1, то 1:(p+1)/2 дают нам ответ
1^2 + (p-1)*(p+1)^2
а если p=4k+1, то 2p-1:(p-1)/2 дают ответ
(2p-1)^2 + (p-1)*(p-1)^2
Более того, эти ответы оба равны p(p^2+p-1).
=================
а найдем мы их на основе следующего анализа:
Сколько решений у сравнения a^2+b^2=1?
a=1+ct;
b=t
(a=-1, b=0 не учтено).
получаем 2сt+c^2 t^2 +t^2=0
2c+t(1+c^2) =0
если c^2 не -1, то получаем ровно одно t.
если c^2=-1 то ни одного t не получаем.
Соответственно для вычетов результат найден.
Для 0 зависит от того, какое p -- вида 4k-1 или 4k+1
(то есть, является ли -1 квадратом)
для невычетов все остальное. И на самом деле получается для вычетов и невычетов поровну.
правда решение какое-то чересчур сложное, в книжках наверняка можно и проще найти.

bmv007

Твоя подсказка мало помогает
Сравнение a+b+c+d=0(mod p) решается довольно просто:
a,b,c - любые (p^3 вариантов а d=-(a+b+c) (mod p).
В случае квадратов так не получиться, потому что сравнение x^2=y(mod p) разрешимо далеко не при всех y

dragan24

Уже сам разобрался
Символ Лежандра рулит.
Теперь только проблема: найти алгоритм сложности O(p*log(p для нахождения всех решений.
Пока что есть алгоритм сложности O(p^2).
Оставить комментарий
Имя или ник:
Комментарий: