求解x=a^b(mod m)

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

利用逐次平方法快速求幂

利用逐次平方法可以快速求幂,这里不局限于数的幂,但以数的幂来举例说明。 要求ak,如果直接用a连乘k次,复杂度比较大。如果把k写成如下形式: k = u0 + 2u1 + 22u2 + ... + 2rur, ui = 0 或 1. 然后制作模a的幂次表: a Continue reading 利用逐次平方法快速求幂