一些解決非線性同餘方程

Question

我試圖找到解決數量

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

其中b < = 50，但A和U可以很大。我的方法是遍歷x從0到min（b，u）的每個值，並且如果它滿足公式add ceil（（ux）/ b）（考慮到x的值的數量大於b但在b）的乘法域中等價於解的數目。我不確定我的算法的正確性。並且可以將我的方法延伸到一個以上的變量一樣，如果有

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

我可生產無序對x和y這樣的使得x < = Y直到（X，Y）< =分鐘（二中，u），並再次計算I =小區（（UX）/ b）和J =小區（（UY）/ b）和乘加的總和爲：

  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 + 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];