UOJ Logo hly1204的博客

博客

一个无聊的 trick

2020-09-11 02:05:08 By hly1204

最近发现 NTT 中没有必要求原根,只要求一个阶(记为 $\operatorname{ord}$ )为 $2^{k}$ 次的东西就可以了,对于奇素数 $p$ ,找到某些 $r,s$ 满足 $p-1=2^{r}\cdot s$ 且 $s\bmod{2}=1$ ,用随机方法找到一个二次剩余 $v$ ,认为对于某个原根 $g$ 存在 $g^{k}\equiv v\pmod{p}$ 且 $k\bmod{2}=1$ ,那么 $$\operatorname{ord}(v^{s})=\operatorname{ord}(g^{sk})=\frac{2^{r}\cdot s}{\gcd(2^{r}\cdot s,sk)}=2^{r}$$ 就找到了这样一个元素,那么用这个来生成阶为 $2^{t},t\in{0,1,\dots ,r}$ 的元素就可以了。

这让我想到了一个人生感悟:

人的一生总有时候会为他人做嫁衣,仿佛如原根一般,原根只是为了求这个阶为 $2^{k}$ 的东西之后就被丢弃了,完全没有用了,希望我们的人生不要如此吧!

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。