algorithm - 非线性同余方程解的个数

Question

我正在尝试找到解决方案的数量

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

其中 b<=50 但 a 和 u 可以很大。我的方法是遍历从 0 到 min(b,u) 的每个 x 值，如果它满足等式，则添加 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 }

并对 t 求和。我想知道我的算法是否正确，是否还有其他更高效的算法。

Answer 1

是的，如果 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];