2021-04-20

2021-04-19 (月)

数学

p を奇素数とする。多項式 mod p の素因数分解について、A(X) = A_1(X) A_2(X), A_1(X) と A_2(X) は異なる d 次式としたとき、T(X) を 2d - 1 次以下の一様ランダムな多項式とすれば A_1 と A_2 が T(X)^{(p^d-1)/2} ± 1 の異なる方の約数になる確率は 1/2 程度以上という命題 (?) について、考えているがよくわからない。

2021-04-20

2021-04-12 (月) - 2021-04-18 (日) 進捗

数学

多項式 mod p の素因数分解について勉強した。

開発

WASM のチュートリアル: 進捗なし
rust-number-theory: 進捗なし
GitHub - koba-e964/rust-quantifier-elimination: Quantifier elimination: 進捗なし

競プロ

進捗なし

ラテン語

Ritchie’s Fabulae Faciles: 進捗なし

チェス

chess.com tactics: 2234 -> 2281 (+47)
lichess rapid: 1812? (進捗無し)
lichess tactics: 2097 -> 2173 (+76)

2021-04-20

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 程度以上であることを言わないといけないが…。)