模法导论(下)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

高阶模法

  • 幂塔求模

下面是本模导书的重点所在了.所谓幂塔就是形如${a^{{b^c}}}$的存在,基本上c稍微大一点就是算不出来的了.大丈夫,我们不是有上面的欧拉幂模定理大法吗?

例:求4^5^6的最后两位.

$$\begin{aligned}
&\quad \ {4^{{5^6}}}\bmod 100\\
&= {4^{{5^6}\bmod \varphi (100)}}\bmod 100\\
&= {4^{15625\bmod 40}}\bmod 100\\
&= {4^{25}}\bmod 100 \\
&= 4{({4^{12}}\bmod 100)^2}\bmod 100\\
&= 4{\left( {{{\left( {4096\bmod 100} \right)}^2}\bmod 100} \right)^2}\bmod 100\\
&= \cdots = 24\quad\textbf{Wrong process!}
\end{aligned}$$

这题很巧,就算用了错误的方法答案还是对的,3^4^5mod12就能让你得0分,而且据我所知高考的时候答案对过程全错只有两分安慰分...

都说了只有a,n互质才能用欧拉幂模大法...

那这个定理岂不是很弱鸡?求尾数难道所有偶数底都只能拉出去枪毙?

说了多少遍,有火灾灭火,没火灾就去点燃啊.令

$\left\{ \begin{gathered}
g = \gcd (a,n)\\
a = g \times d\\
n = g \times f\\
\end{gathered} \right.$

$\begin{aligned}
{a^{{b^c}}}\,\bmod \,n &= {g^{{b^c}}} \times {d^{{b^c}}}\,\bmod \,(g \times f)\\
&= (g \times ({g^{{b^c} - 1}}{d^{{b^c}}}\,\bmod \,f))\,\bmod \,n\\
&= \left( {g \times \left( {\left( {{g^{{b^c} - 1}}\bmod \,f} \right)\left( {{d^{{b^c}}}\bmod \,f} \right)\,\bmod \,f} \right)\,} \right)\bmod \,n\\
&= \left( {g \times \left( {\left( {{g^{{b^c}\bmod \,\varphi (f) - 1}}\bmod \,f} \right)\left( {{d^{{b^c}\bmod \,\varphi (f)}}\bmod \,f} \right)\,\bmod \,f} \right)\,} \right)\bmod \,n
\end{aligned}$

这样就把问题递归掉了.

话是这么讲,但是写程序的时候还是要点小优化的.假定幂塔用一个向量表示.代码写出来大概如此:


葛立恒数后8位是64195387,诸位一定很感兴趣这是怎么算出来的.这个数照理是无法形容的大,计算机怎么可能算得出来.

  • 超幂运算取模

其实很容易想到,因为欧拉函数定义在整数上,然后他又要严格单调递减,那么不断迭代迟早收敛到不动点1,N mod 1=1,N有多大就不用管了.

再说欧拉函数是个积性函数,变成1需要的迭代次数不会多的.设需要的次数为序列${a_n}$,分析下可知:

$$\begin{aligned}
&{a_n} = {a_{\varphi (n)}} + 1\\
&{\log _3}n < {a_n} < {\log _2}n
\end{aligned} $$

所以我写的代码里覆写掉了Mathematica自带的PowerMod,这样就限制了递归深度.简单的说,对于任意一个超运算,我们只要计算下欧拉函数迭代到1的长度,然后直接截断就行了.

也就是说计算复杂度其实只和模数有关而和底数几乎无关.平均来说迭代深度就是位数乘3.


题图为复平面上的平方模迭代.不要强迫症去改绘图区域,会导致图像断裂,代码如下:

发表评论