在^ x = a(mod n)中找到x

Question

我要计算一^米模N,其中ñ是一个素数,而米是非常大的.而这样做二进制功率计算,我想找到这样X那一个^X =α(MOD N) ,然后计算一个^(M模x)的模N.

显然这样的x存在于任何a,因为powers mod n在某个时刻循环,但我没有找到如何使用模块化算术计算它.我想知道我是否遗漏了某些东西,或者是否存在一些数值方法？

Answer 1

你的模数是素数,这使得它很容易开始,就像Fermat(不恰当地称为"小")定理一样,然后

a^n ? a (mod n)

为了所有人a.公式是等价的

a^(n-1) ? 1 (mod n),  if n doesn't divide a.

那你有

a^m ? 0 (mod n) if a ? 0 (mod n) and m > 0

和

a^m ? a^(m % (n-1)) (mod n) otherwise

(请注意,您的建议a^(m % x)一般不正确,如果m = q*x + r您有

a^m ? (a^x)^q * a^r ? a^q * a^r ? a^(q+r) (mod n)

并且你需要重复这个减少,q+r直到你得到一个小于的指数x.

如果你真的对最小的x > 1那样感兴趣a^x ? a (mod n),那么情况又a ? 0 (mod n)是微不足道的[ x = 2],而对于其他情况,让y = min { k > 0 : a^k ? 1 (mod n) },然后是期望的x = y+1,并且,由于环中的单位Z/(n)形成一个(循环)秩序组n-1,我们知道这y是一个除数n-1.

如果你的因数分解n-1,除数,因此考生y很容易找到并检查了,所以没有太多的工作找y那么-但通常仍远低于计算更多的工作a^r (mod n)为一个单一的0 <= r < n-1.

找到因子分解n-1可能是微不足道的(例如对于费马素数),但它也可能非常难.除了找到a模数的确切周期n通常远比仅为a^r (mod n)某些计算更多的工作这一事实之外0 <= r < n-1,这使得甚至试图进一步减少指数是否值得非常怀疑.

通常,当模数不是素的情况下,当gcd(a,n) = 1是类似的,与n-1通过所取代?(n)[其中?是卡迈克尔功能,其产生的基团的单元的最小指数Z/(n); 对于素数n,我们有?(n) = n-1].