число решения нелинейного уравнения конгруэнции

Question

Я пытаюсь найти количество раствора

 x^a (mod b) =c with 0<=x<=u 

где б < = 50, но и у может быть большим. Мой подход заключается в повторении каждого значения x от 0 до min (b, u), и если он удовлетворяет уравнению, добавьте ceil ((ux)/b) (для учета количества значений x is больше b но эквивалентны в мультипликативном поле b) на число решений. Я не уверен в правильности моего алгоритма. И я могу расширить свой подход к более чем одной переменной, как если есть

(x^a + y^a) (mod b)=c 

я могу производить все неупорядоченные пары х и у такие, что х < = у до (х, у) < = мин (б , и) и снова вычислить I = CEIL ((УБ)/б) и J = CEIL ((иу)/б) и умножить добавить сумму как:

  t={i+i*(i-1)*2 if x=y , i*j*2 if x!=y } 

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

Answer 1

Да, если x^a mod b = c, то (x + b)^a mod b = c. Таким образом, на сегодняшний день существует всего 1 + этаж ((u-x)/b). Вам просто нужно помнить, чтобы пропустить эти числа, пока вы ищете другие решения от (x + 1) до min (u, b).

Концепция работает для 2 переменных, но гораздо более интенсивна в вычислительных целях. Вы решаете x^a mod b = d и сохраняете счет как T [d], где 0 ≤ d < b. Вы можете спросить, почему 0 ≤ d < b, а не 0 ≤ d ≤ c. В этом примере: если c = 7 и b = 35, то (x, y) такое, что x^a mod 35 = 8 и y^mod 35 = -1 ≡ 34 также будет решением.

Тогда общее число решений, подобно тому, что вы предложили, за исключением я не заморачиваться с отдельной обработкой х = у и х ≠ у:

for (i=0 ; i < b ; i++) 
    count += T[i]*T[(b +c -i)%b];