一般にq乗根でも指数がΣp^t≡0 mod qになるので動く
posted at 17:49:00
| Stats | Twitter歴 3,682日（2013/05/06より） |
ツイート数 10,967（2.9件/日） |
表示するツイート :
2020年01月18日(土)10 tweetssource
(x^p)^pはx^2pではなくx^(p^2) 頭大丈夫笑
posted at 17:48:15
これ間違いで、(m-α)^(p^2)=m-ωωαなので、(m-α)^(p^2+p+1)=nになって指数部はちゃんと3で割れて、うまく動く
posted at 17:47:41
nの3乗根だとx:=m^3-nが3乗非剰余になるようなmをとってα=qbrt(x)としてFp(α)で考えて、(m-α)^p=m-ωα、(m-α)^2p=m-ωωαだから、(m-α)^(3p+1)=m^3-x=nになって困る（指数が3で割れない）
posted at 12:29:24
cipollaも一般冪根に拡張できるのマジか
posted at 12:23:44
@noshi91 霧香さんのpdfにあります
posted at 02:22:23
@___n___z >非常に分かりやすいです
そういっていただけるとありがたいです
posted at 00:51:40
@___n___z >q乗すれば
「q(a,b)=(qa,qb)=(0,qb)であり、qはkと互いに素なので、bが互いに素⇒qbはkと互いに素⇒(0,qb)はk乗非剰余」です。
>消したい非ゼロ
一発でやるのではなく、線形時間掛けてやります。（"末尾の0の個数"が増えていることが確かめられるまで、最大k-1回操作を繰り返します）
posted at 00:51:27
https://pic.twitter.com/pNvJl7S0sO
posted at 00:06:57
@___n___z 一応補足ですが、kは素数のみを考えます（k-torsionが分離できないと困るので）
posted at 00:06:35