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

Я пытаюсь найти число решений для

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

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

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

Я могу создать все неупорядоченные пары x и y такие, что x‹=y до (x,y)‹=min(b,u) и снова вычислить i=ceil((u-x)/b) и j=ceil((u-y )/b) и умножьте сумму как:

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

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


algorithm math discrete-mathematics modular-arithmetic number-theory
person user2179293    schedule 04.08.2013    source источник
comment
Да, ваш первый алгоритм верен, как следует из следующего ответа на аналогичный вопрос: stackoverflow.com/a/18042254/509868   -  person anatolyg    schedule 04.08.2013

Ответы (1)


arrow_upward
0
arrow_downward

Да, если x^a mod b = c, то (x+b)^a mod b = c. Таким образом, до сих пор было бы в общей сложности 1 + floor((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^a mod 35 = -1 ≡ 34, также будут решением.

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

for (i=0 ; i < b ; i++)
   count += T[i]*T[(b +c -i)%b];
person Apprentice Queue    schedule 04.08.2013
comment
Причина, по которой мне нужно обрабатывать x = y и x! = y, заключается в том, что комбинация (a, a) дает нам одно решение, а (a, b) дает нам два решения, но, используя вашу логику, как я могу сделать вывод, если x и y используемые для получения остатка i и c-i были разными или одинаковыми - person user2179293; 05.08.2013
comment
Хорошо, теперь я понимаю, что делал ошибку в расчете перестановок. Большое спасибо за ответ. - person user2179293; 05.08.2013