原根若干性质及最小原根的求解

重要修正:本想把原根的概念推广到所有正整数,之后就可作为解决一般性问题xk≡b(mod m)的基础(我原本就是打算写这个主题,先写本文是为了引出先导性的知识)。然而测试之后发现m为9407的时候,这个数根本没有原根!这之后就纠结了?到底是哪里出了问题?之后一直 Continue reading 原根若干性质及最小原根的求解

求解x=a^b(mod m)

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