0

楕円曲線暗号の解き方その2、その3、その4(オリジナル)

313
1

楕円曲線暗号の解き方その2、その3、その4(オリジナル)

楕円曲線暗号の解き方その2

F=y2=x3+5x+5の場合
1.xに適当な数の自然数を代入する。その値F(x)mとしてf(m)mに代入する。
2.かわぐちさんの素因数発見アルゴリズムで、素因数を見つける。
3.素因数の二乗で右辺を割った値Kが\sqrt{F}以上かつ整数であるか調べる。\sqrt{F}以下なら解けない。
4.Kに1.2.3.を繰り返す。
5.小さくなったKが平方数であることを確認するか、1.2.3.4.のみで整点を見つける。整点を見つければ、有理点を見つけることができる。

楕円曲線暗号の解き方その3、整点がなくても解ける楕円曲線暗号の解き方(こっちの方が重要)

y2=x3+ax2+bx+cとする
y2c=x3+ax2+bx
y2c=Y=f(x)と置き、両辺をxで微分すると、

Y=3x2+2ax+b
Y=0の時
x=a±a2b3
これで、大体どんなグラフか判る。
Y=0の時y=±cだから……などと一々考えなくてよい。Yf(x)=y2c=x3+ax2+bxを微分したものなので、xの関数の微分、つまり導関数であり、楕円曲線上で大体の場合xの導関数は0になるからだ。
Yを有理数の範囲で変えながら、xを極大点と極小点の間、その外で変える。
導関数の0以上、0以下の増減より定数Yf(x)がどこで交点を持つか、xに関する3次関数のようにたちどころに判るということ。
3次関数なので、増減表のf(x)=0で分かれた3つの部分を調べればよい。(場合により1,2箇所の可能性もある。)

楕円曲線暗号の解き方その4(これが本線)

その3の応用。
f(y)=x=y2c
つまりy=x2cでもよい。
その内のどちらかと、
f(x)=y=x3+ax2+bx
前者のグラフは、y=x2cという2次関数を90度回転させて上下反転したものである。
このグラフを、両方同じxy平面に書いてしまう。解が大体求まる。
コンピュータであれば正確に求めることが可能である。

注意:自分でも自信ないです。しかし、その4が一番使えて、しかも簡単だと思います。
式変形の同値性の原理はよく解りません。

同日追記 xの2次関数はy軸に対して対称だからですね。

投稿日:2023122
更新日:2023124
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

のんびりしようね。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 楕円曲線暗号の解き方その2、その3、その4(オリジナル)
  2. 楕円曲線暗号の解き方その2
  3. 楕円曲線暗号の解き方その3、整点がなくても解ける楕円曲線暗号の解き方(こっちの方が重要)
  4. 楕円曲線暗号の解き方その4(これが本線)