多项式倍增

    阅读全文
fightinggg's avatar
fightinggg 5月 02, 2019

位运算

    阅读全文
fightinggg's avatar
fightinggg 10月 15, 2018

蒙哥马利模乘

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 核心思想蒙哥马利运算是一种新的运算,他把乘模简化为对进制数的除法,以及简单加法,这就使得乘模避开了大量的取模试除。 蒙哥马利表示法例如$a%mod$的蒙哥马利表示法为$f(a) = a\times p% mod$,$p$是一个进制数, 我们储存$f(a)$的值,而不是a的值。 复原于是我们很容易发现,对于蒙哥马利表示法变回普通表示法时只需要乘p对mod的逆元即可。 p的取值蒙哥马利表示法会找一个进制数使得普通数字转化为蒙哥马利表示法,一般来说这是一个刚好大于模数的进制数。     阅读全文
fightinggg's avatar
fightinggg 10月 15, 2018