楕円曲線

Kを標数\(\neq2,3\)の体とし\(x^3+ax+b(a,b\in K)\)を重根を持たない3次多項式とする。この時\(K\)上の楕円曲線とは無限遠点と呼ばれる\(O\)と書かれる1つの要素を含む方程式\(y^2=x^3+ax+b\)で表される曲線である。

楕円曲線の例として,\(\mathbb{R}\)上の楕円曲線\(y^2 =x^3+1\) は

x<-seq(-1,5,0.01)
y<-sqrt(x^3+1)
plot(x,y,ylim=c(-3,3),xlim=c(-3,4),type="l")
y<--sqrt(x^3+1)
par(new=T)
plot(x,y,ylim=c(-3,3),xlim=c(-3,4),type="l")

\(y^2 =x^3-x\)は

x<-seq(1,5,0.01)
y<-sqrt(x^3-x)
plot(x,y,ylim=c(-3,3),xlim=c(-2,4),type="l")
y<- -sqrt(x^3-x)
par(new=T)
plot(x,y,ylim=c(-3,3),xlim=c(-2,4),type="l")
x<-seq(-1,0,0.01)
y<-sqrt(x^3-x)
par(new=T)
plot(x,y,ylim=c(-3,3),xlim=c(-2,4),type="l")
y<- -sqrt(x^3-x)
par(new=T)
plot(x,y,ylim=c(-3,3),xlim=c(-2,4),type="l")

\(\mathbb{F}_{19}\)上の\(y^2 =x^3+x+1\)は

n<-19
x<-0:(n-1)
y<-0:(n-1)
z<-matrix(0,nrow=n,ncol=n)
E<-function(i,j){
  if((j*j-i*i*i-i-1)%%n==0){
    return(1)
  }
  else{return(0)}
  }
for(i in 0:(n-1)){
  for(j in 0:(n-1)){
    z[i+1,j+1]<-E(i,j)
  }
}
image(x,y,z,col=cm.colors(100))

となる。まずハッセの定理が成り立っていることを確かめるのを目標とする。ハッセの定理とは有限体上の楕円曲線の点の数についての定理である。今回は位数が素数の時に成り立っていることを見る。

エラトステネスの篩

有限体を作るために素数の集合を作る。 エラトステネスの篩を用いてn以下の素数の集合を作ることにする。

P<-function(n){
  Q<-logical(n) 
  Q[1]<-TRUE
  P<-NULL
  for(i in 2:sqrt(n)){
    if(!Q[i]){ 
      Q[seq(i*2,n,by=i)]<-TRUE
    }
  }
  P<-(1:n)[!Q]
  return(P)
}

平方剰余

\(p\)を奇素数とし\(a\)を\(p\)で割れない整数とするとルジャンドル記号\(\left(\frac{a}{p}\right)\)を \(x^2\equiv a (mod p)\) となる\(x\)が存在する時\(\left(\frac{a}{p}\right)=1\)とし存在しない時\(\left(\frac{a}{p}\right)=-1\)と定義する。(\(a=0\)のとき便宜上\(\left(\frac{0}{p}\right)=0\)と定義する。)次に\(n\)を奇数、\(a\)をgcd\((n,a)=1\)を満たす整数とする。ヤコビ記号を\(n\)が\(n=p_1p_2\cdots p_m\)と因数分解できる時ルジャンドル記号の積として\[\left(\frac{a}{n}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_m}\right)\]と定義する。(左辺がヤコビ記号で右辺がルジャンドル記号である) この時次のことが成り立つ、\(n\)と\(m\)を互いに素な奇数とする時\[\left(\frac{n}{m}\right)=(-1)^{\left(\frac{n-1}{2}\right)\left(\frac{m-1}{2}\right)}\left(\frac{m}{n}\right) =\begin{cases} \left(\frac{m}{n}\right)&m\equiv 1\text{or}\ n \equiv 1(mod 4)\\ -\left(\frac{m}{n}\right)&m\equiv n\equiv 3(mod 4) \end{cases} \]それに加え次のことも成り立つ。\[\left(\frac{-1}{n}\right)=(-1)^{\frac{n-1}{2}}=\begin{cases} 1&n\equiv 1(mod\ 4)\\ -1&n\equiv 3(mod\ 4) \end{cases} \] \[\left(\frac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}=\begin{cases} 1&n\equiv 1\text{or}\ 7(mod\ 8)\\ -1&n\equiv 3\text{or}\ 5(mod\ 8) \end{cases} \] \[ \left(\frac{n}{m}\right)=\left(\frac{n\ \ mod\ m}{m}\right) \] これらを用いて\(x^2\equiv a(mod\ p)\)となる\(x\)が存在するかを求める関数を作る。
\(m\)を奇素数とし\(n\)を\(m\)で割れない整数とする.\(\left(\frac{n}{m}\right)\)は次のように求める。(\(x\)は始め\(1\)とし\(x\)を出力する)
アルゴリズム
(1)\(n\gets\)(\(n\)を\(m\)で割ったあまり)をして(2)へ
(2)\(n=m-1\)なら(3)へ,でないなら(4)へ
(3)\(m\equiv 3\)(mod 4)なら\(x\gets\) -xをして(終了),でないならそのまま(終了)
(4)\(n=1\)なら(終了),でないなら(5)へ
(5)\(n\)が偶数なら(6)へ,奇数なら(7)へ
(6)n\(\gets\frac{n}{2}\)をして,\(m\equiv 3\)or\(5\)(mod 8)なら\(x\gets -x\)をし(4)へ
(7)\(m\equiv n\equiv 3\)(mod 4)なら\(x\gets-x\)をして,\(n,m\)を入れ替えて(1)へ

PR<-function(n,m){
  x<-1
  n<-n%%m                           ##(1)　　　
  a<-NULL
  if(n==0){
    return(0)
  }
  if(n==m-1){                       ##(2)
    if(m%%4==3){                    ##(3)
      x<--x
    }
    return(x)
  }
  while(n!=1){                      ##(4)
    if(n%%2==0){                    ##(5)
      n<-n/2                        ##(6)
      if(m%%8==3|m%%8==5){
        x<--x
      }
    }
    else{
      if(m%%4==3&n%%4==3){          ##(7)
        x<--x
      }
      a<-n
      n<-m
      m<-a
      n<-n%%m
      if(n==m-1){
        if(m%%4==3){
          x<--x
        }
        return(x)
      }
    }
  }
  return(x)
}

楕円曲線の解の個数

これらを用いて\(\mathbb{F}_p\)上の楕円曲線の点の個数を求める。楕円曲線が\(y^2=f(x)\)で定義されてたとすると曲線の点の個数は\[N(p)=\sum_{x\in\mathbb{F}_{p}}\left(1+\left(\frac{f(x)}{p}\right)\right)+1\]と表すことができる。これを用いて\(\mathbb{F}_{p}\)上の楕円曲線の点の個数を求める関数を作る(ただし実際に作る関数は無限遠点を除いた点の数とする)。今回は\(f(x)=x^3+x+1\)としてハッセの定理を確かめることにする。

N<-function(p){
  n<-0
  for(i in 0:(p-1)){
    j<-((i*((i*i)%%p))%%p)+i+1
    n<-1+PR(j,p)+n
  }
  return(n)
}

ハッセの定理

楕円曲線のハッセの定理とは位数\(q\)の有限体上の楕円曲線の点の数を\(N(q)\)とすると\[|N(q)-q-1|\leq 2\sqrt{q}\]を満たすという定理である。 では実際にハッセの定理が成り立っていることを確かめる。 計算を少なくするためにここからprimeを2から20000までの素数としApを\(i\)番目の値が\(i\)番目の素数をpとした時N(p)となるベクトルとする。

prime<-P(20000)
n<-length(prime)
Ap<-numeric(n)
for(i in 1:n){
Ap[i]<-N(prime[i])
}
HG<-function(x){
  n<-length(x)
  for(i in 1:n){
    x[i]<-abs(x[i]-Ap[i])
  }
  return(x)
}

グラフにして

x<-P(10000)
y<-HG(x)
plot(x,y,xlim=c(0,10000),ylim=c(0,210))
y<-2*sqrt(x)
par(new=T)
plot(x,y,type="l",col="red",xlim=c(0,10000),ylim=c(0,210))

これより実際にハッセの定理が成り立っていることが確かめられる。 次に\(a_p=N(p)-p-1\)として\(x^2-a_px+p\)を考える。この解はハッセの定理より\(a_p^2-4p\leq0\)なので複素数であることがわかる。その解\(\displaystyle{\frac{a_p\pm\sqrt{4p-a_p^2}i}{2}}\)を複素平面上にplotしてみる。

SS<-function(a){
  n<-length(a)
  x<-NULL
  y<-NULL
  z<-NULL
  w<-NULL
  for(i in 1:n){
    z<-(a[i]-Ap[i])
    w<-sqrt(4*a[i]-z^2)/2
    z<-z/2
    x<-c(x,z)
    y<-c(y,w)
    x<-c(x,z)
    y<-c(y,-w)
  }
  plot(x,y,xlim=c(-160,160))
}
SS(P(10000))

となる。偏角が\(\frac{\pi}{2},\frac{3}{2}\pi\)の場所に多く分布していることがわかる。これ角度分布をグラフにした時に次の予想ができる。

佐藤-Tate予想

ハッセの定理の式を変形して\(-2\sqrt{p}\leq N(p)-p-1\leq2\sqrt{p}\)とできこれより\(\cos\theta_p=\frac{N(p)-p-1}{2\sqrt{p}}\)と置くことができる。この時、佐藤Tate予想とは次のことが成り立ついう予想である。\(p\)を素数とし \(0\leq\alpha\leq\beta\leq\pi\)となる\(\alpha,\beta\)に対して\[\lim_{x\to\infty}\frac{\#\{p\leq x|\alpha\leq\theta_p\leq\beta\}}{\pi(x)}=\frac{2}{\pi}\int_{\alpha}^{\beta}\sin^2 x dx\]となるだろうという予想である(ただしこの時の楕円曲線は虚数乗法を持たないものとし\(\pi(x)\)は\(x\)以下の素数の個数とする)。この予想は2011年にTaylorらによって解決された。次にこれを10度間隔で確かめることにする。

STG<-function(x){
  n<-length(x)
  s<-NULL
  r<-numeric(18)
  j<-0
  for(i in 1:n){
    s<-acos((x[i]-Ap[i])/(2*sqrt(x[i])))*18/pi
    while(j>s|s>j+1){
      j<-j+1
    }
    r[j+1]<-r[j+1]+1
    j<-0
  }
  return(9*r/n)
}

グラフにすると

x<-prime
y<-STG(x)
x<-0:17
plot(x,y,type="l",ylim=c(0,1.2))
y<-(sin(x*pi/17)^2)
par(new=T)
plot(x,y,type="l",col="red",ylim=c(0,1.2))

となる。では、楕円曲線が虚数乗法を持つときどうなるか確かめてみる。\(y^2=x^3-x\)は虚数乗法を持つのでこの楕円曲線を用いる。

N<-function(p){
  n<-0
  for(i in 0:(p-1)){
    j<-((i*((i*i)%%p))%%p)-i
    n<-1+PR(j,p)+n
  }
  return(n)
}
prime<-P(2000)
n<-length(prime)
Ap<-numeric(n)
for(i in 1:n){
Ap[i]<-N(prime[i])
}
x<-prime
y<-STG(x)
x<-0:17
plot(x,y,type="l",ylim=c(0,2))
y<-(sin(x*pi/17)^2)
par(new=T)
plot(x,y,type="l",col="red",ylim=c(0,2))

図より明らかに中心(\(\frac{\pi}{2}\))によっているのがわかる。

まとめ

ハッセの定理は素数pの時確かに成り立っていそうだった。
一般の有限体は多項式を扱う必要がありできなく、成り立っていることを確かめられなかった。
佐藤Tate予想は成り立っていそうではあるが,素数定理と似ているからか収束率が悪くまだ\(\sin^2\)に収束するか分からない。 楕円曲線が虚数乗法を持つときは佐藤Tate予想は成り立ちそうにないことが見れた。楕円曲線が虚数乗法を持つか判定するのは難しいがコンピュータでは簡単に分かりそう。

参考文献

・和田秀男(1999/4/1)コンピュータと素因子分解,遊星社