综合文案求解xabmod narutoacm.pdfVIP

NARUTOACM

Anime+Mathematics+Program+Sports

Search

-a^k=x(modm)

←PreviousNext→

求解x=a^b(modm)

Postedon2012年11月6日byNARUTOACM14Comments↓

b

本文致力于解决如下问题：求解x≡a(modm)，其中a,b,m都是正整数。

如果b足够小，则可直接用逐次平方法求解，如果你不知道逐次平方法，可以先看这里。所以这里假设b足够大（这不是说是一个64位整数，而是可

以上百上千位的一个数），大到逐次平方法也已不足以快速出解。

用素数探路的思想，先假设m是素数，那么要么a与m互素，要么ma。前者可利用小定理，令b=k(m-1)+b′，其中0≤b′m-1，则有ab≡ak(m-

1)+b′≡ab′(modm)。可用逐次平方法快速求解。若ma，结果显然为0。

现在考虑要求m可以是任意数的情况。同样，若a与m互素，由上边我们可联想到欧拉，利用欧拉求解。令b=kΦ(m)+b′，其中

bkΦ(m)+b′b′

0≤b′Φ(m)，则有a≡a≡a(modm)，用逐次平方法快速求解。如果a与m不互素，即(a,m)1，这种情况下应该怎么做？

注意到b如此大，而模m的不同的数最多只有m个，显而易见的，ab一定和某个很小的指数ab′模m同余，如果找到这个小的指数，就可以利用逐次平

方法求解。考虑如下序列：

01m

a,a,...,a(modm)

rr+s

由鸽巢原理可知，必有一个最小的r和一个最小的s，使得a≡a(modm)，其中r+s≤m。若找到这样的r和s，那么显然有

xkr+x0kr+s+x0x+sm)，其中x是大于或等于r的任意数。要注意的是，对任意大于或等于r的x，不存在更小的数s1，使得

a≡a≡a≡a(mod

xx+s1