2021-04-18 (日)

数学

Cohen の Alg. 3.4.6 や Prop. 3.4.7 について考えていた。U = T + T^2 + T^4 + ... というのは T のトレースに対応していて、T^{2^d} - T = U(U + 1) というのはトレースは F_2 の元で 0 か 1 のどちらかというのに対応している。それに対し奇素数 p に対するアルゴリズムでは T^{(p^d-1)/2} = (N T)^{(p-1)/2} を考えていて、ノルム写像は (乗法群の間の) 全射準同型なので、T (に対応する F_p(theta) の数) (であって 0 でないもの) について N T が平方剰余となる確率は 1/2 である。(今は d 次の因数を見つけることにフォーカスしていて、見つけるべき d 次式 f(X) の根の一つを theta としたとき、f(X) | T^{(p^d-1)/2} - 1 と N (T に対応する F_p(theta) の数) が平方剰余であることは同値。) つまり、これでd 次式の因数を 1/2 くらいの確率で分類できるということになる。(厳密には、任意の二因数 f(X), g(X) に対して、一方が T^{(p^d-1)/2} - 1 側に行きもう一方が T^{(p^d-1)/2} + 1 側に行く確率が 1/2 程度以上であることを言わないといけないが…。)