ただのメモ

他の人に見せても良い方のメモ

整数方程式から「Exponential Congruences」

こちらのペイパーを使う。

 F_q^*を有限体 F_q乗法群(二項演算(乗法)で、零元を除いた集合で閉じているもの)をとおく。
a, b, c, f, gをFq*の要素として、 a f^x + b g^y = cを考えたい。x, yは非負整数である。
この式は、cyclotomic classes理論から、f,g を求める問題と、等価である。(双対問題として規定されている)
これは、半直積群(この場合、内部半直積で、2つの群、でかい群の正規部分群(共役変換によって不変、可換みたいなイメージ)と、部分群が、自明な共通部分を持つ群を、いう。ちなみに外部半直積は、デカルト集合みたいなので、ホモロジー代数的な定義では、群Nの群Hによる群の拡大の中で「もっとも単純なもの」らしい) \mathbb{Z}/N ×| \mathbb{Z}/p) hidden subgroup 問題を解く時に重要になる。
ちなみにCyclotomic fieldとは、円分体といって、有理数体に、1のm乗根を加えた代数体であり、 拡大次数は、 \phi(m)オイラー関数)で、任意の円分体は、ガロア核大体である。mが合成数のときは、合成体として、分けっこ出来たりもする。


ホモロジーを分かりたいので、一旦そちらを調べる

  • 群論的には、群と群準同型の列f:id:medical-science:20210730152806p:plainは、各準同型の像が、次の準同型の核に等しいとき、その群と群準同型の列を、完全、という。定義から、前の写像と次の写像の合成は、常に零元となる。(逆は成り立たない)。加群に対しても、出来るよね。
  • とは、基点のあるなしで、意味あいが変わってくる。1)基点がない構造の場合、2つの基点のない構造を持つ集合A, Bで、f:A→Bを構造を保つ準同型とすると、fの核は、写像で移したものが互いに一致するような、もとのAの元2つの組、であった。このKerfはAにおける二項関係を定めた。2)基点を持つ構造の場合、同種の構造を持つ、基点を持つ集合(A, a), (B, b)として、f:A→B、f(a)=bを構造を保つ準同型とすると、核は、終域Bの基点bの原像、となる。自明な核は、Kerfが{a}のとき。
  • 短完全列とは、短い完全列で、0→A→B→C→0、なる形の完全列だ。Aは写像を介してBの一部に移されるも、次の写像でいなくなるので、Cは商対象B/Aと同一視されるそう。短完全列が、分裂するとは、切断・断面と言われる、写像s:C→Bで、g○s=idc(Cへの恒等写像)が、ある(存在する)こと。

さて、本題に戻ると、
ここから、2つ程重要な単語が出てくる。
1つは、Parseval's identityといって、フーリエ変換で分解した後で、その関数の大きさチックなものを取ろうとしたとき、正規直交基底で分解したときの係数の大きさチックなもののを集めて、表現できるよ。ということ。情報の損失がないから、当たり前か。
2つ目は、離散対数問題素数Pと整数Aが与えられて、整数Yを y \equiv a^x \bmod pとして、Yから整数解Xを求める問題。Pが大きな素数だと難しくなる。

今回は、ここらで、終わりとしよう。

バイバイ!

a = 20
y = 9
p = 11
x = -1
while True:
  x += 1
  if y == (a**x)%p :
    print(x)
    break