求解部分x^k=b(mod m)问题

原本信誓旦旦的想要解决整个一般性的xk≡b(mod m)问题,然而发现推理过程出了点问题(原因可看这里),故把标题加了“部分”两字,亦即对另一部分的这类问题我还不会解决。 对ab≡c(mod m)这个式子,实际上包括3个问题。在这篇文章中,我们知道了已知a和b Continue reading 求解部分x^k=b(mod m)问题

求解x=a^b(mod m)

本文致力于解决如下问题:求解x≡ab(mod m),其中a,b,m都是正整数。 如果b足够小,则可直接用逐次平方法求解,如果你不知道逐次平方法,可以先看这里。所以这里假设b足够大(这不是说是一个64位整数,而是可以上百上千位的一个数),大到逐次平方法也已不足以 Continue reading 求解x=a^b(mod m)