pを奇数の素数とします。 pを整数の2乗の和として表すことができることは非常に広く知られていますp = a ² + b ² 2、17 = 1 ² +4 ² 、...; 3、7、11、...は表現できません。 aとbが1つの楕円曲線に直接関係する美しい式で書き留められることはあまり知られていません。 1907年のこの結果について、ヤコブスタールという名前のドイツ人の著者によるものと、関連するものについてお話します。



3、7、11、および4で割ったときに3の剰余を与える他の数値がa ² + b ^2の形式で表現できない理由を理解するのは非常に簡単です：偶数の²乗は常に4で除算し、奇数の2乗は常に4で割ったとき剰余1を与えます、4で割ったときの2つの平方の合計は、0、1または2の剰余を与えることができますが、3ではありません。4k+ 1の形式の素数の表現可能性は明白ではありません（特に、単純さが不可欠​​であることに気づいた場合：望ましい21の数21は、合計が2です正方形なし）。

控除

自然数は無限にあります。 いくつかの理由でそれらをクラスに結合すると便利です。 特に、ある数nによる除算の剰余を結合すると、 nを法とする剰余になります。剰余x̅は、 nで除算するとxと同じ剰余を与えるすべての数のクラスです。 これは同等であり、剰余x̅はx + n∙kの形式のすべての数で構成されます。ここで、 kは整数です。 この投稿のフレームワーク内では、すべての残基はモジュロp （導入部と同じ奇数の素数）になります。 当然、 pで除算した残基、つまり正確にpの残基と同じ数の異なる残基があります。 自然数の無限と比較して、残基への移行はオプションの数を大幅に減らします。

クラス操作は常に意味をなさない。 たとえば、素数のクラスを複合数のクラスに追加しようとしても意味がありません。数字のみを追加でき、素数と複合数の合計にはクラスに共通のプロパティが表示されません。 トートロジークラブのメンバーは、素数のクラスと複合数のクラスを合計すると、素数と複合数の合計で合計できる数のクラスを与えると言うことができます。



ただし、控除の場合、自然数から「継承」される加算、減算、および乗算は、他の控除を与えます。 たとえば、2̅+3̅=5̅：剰余2の任意の数を取り、残り3の任意の数を取り、それらの合計は間違いなく5の剰余を与えます。不快なモジュール6。 しかし、単純なモジュールの場合、明らかに、これは起こりません。彼らが言うように、 ゼロ除数はありません 。 さらに、 a̅=0̅の場合を除き、任意の2つの剰余について方程式a̅∙x̅=b̅ （除算）を解くことができ、結果は一意に決定されます。 一意性は、非ゼロの剰余の積が非ゼロであるという事実から得られます。 a̅≠0̅であるため、 aとpの最大公約数は1です（ここでも単純さpが必要です）。 拡張ユークリッドアルゴリズムは、 a∙x + p∙y = 1のようにxとyを見つけます。つまり、 a̅∙（b̅∙x̅）=b̅となります。



ゼロ除数がないことの重要な結果：次数nの単一変数の非ゼロ多項式は、 nを超える根を持つことはできません。 （これは通常の整数ではよく知られていますが、剰余演算を使用する場合、追加の正当化が必要です。3̅∙x̅=0̅6を法とする3つの解0̅、2̅、4̅があります。）実際、通常の「列」除算は多項式f（x）は、 f（x）=（x-c）g（x）+ （定数）として表すことができます。ここで、多項式g（x）の次数は1未満です。 cがf（x）の根である場合、定数はゼロ（ x = cを代入）です。 c 'がf（x）の別のルートである場合、 g（x）のルートになります（ここではゼロ除数がないことが重要です）。したがって、プロセスを続行できます。 n個の根が既に蓄積されている場合、残りのg（x）は定数であり、さらにゼロ以外（f（x）= 0 ）であり、根はもうありません。



単純なモジュールによる控除は、加算、減算、乗算できます。 非ゼロの控除は分割できます。 これらすべての操作には、タイプa̅∙b̅=b̅∙a̅の通常のプロパティがあります。 スマートブックは、単純なモジュールによる控除がフィールドを形成すると言います （そして、分割することが不可能で、他のすべてが同じである複合モジュールによる控除は可換環です ）。 そして、この分野を有限と呼ぶのに賢い本である必要はありません。 残差フィールドは唯一の有限フィールドではありませんが、他の最終フィールドは必要ありません。

楕円曲線について少し

pを法とする楕円曲線（同じ奇数素数）は、方程式y ² = x ³ + a ₂ x ² + a ₄ x + a ₆の解の集合と考えることができます。ここで、 x 、 y 、およびすべてのaは剰余です（各解は1と呼ばれます） point ）に加えて、ペアx、yを持たない1つの特別なポイントO。 方程式の右辺は正方形で除算しないでください。そうしないと楕円曲線になりません。タイプy ² =（x-1̅） ² （x +2̅）の方程式では、変数yをz = y /（x-1̅）に置き換えて依存関係を取得できます3度ではなく2度。

p≠3の場合、変数xの代わりにx + a 2/3を取り 、 x ^2の項を取り除きます。



x、yは有限集合に属するため、楕円曲線上の点の数も有限であることは明らかです。 それらのいくつ？ これは一般的に難しい質問です。 y ² = x ³ -k∙xの形式の曲線に制限します。 そのような曲線の場合、完全な証明を1つのHabrポストに入れることができます（かなり長いものですが）。

二次控除と非控除

まず簡単な質問をしてみましょう。 方程式y ² = cの解はいくつありますか。ここで、 y、cは剰余です。 p = 7の例：

y	0̅	1̅	2̅	3̅	4̅	5̅	6̅
y 2	0̅	1̅	4̅	2̅	2̅	4̅	1̅

c =0̅の場合、1つの解y =0̅があります。 残りのy値は、1̅から（p-1）/ 2に対応する控除まで、および（p + 1）/ 2に対応する控除から-1̅までの2つの半分に分割されます。 y ² =（-y） ²であるため、 y ²の値の行の後半は、前半に対して鏡面対称です。 一方、方程式には少なくとも4つの解があり、2次の多項式では不可能であるため、各半分に繰り返しはありません。したがって、正確に2つの解があり、同じ数の（p-1）/ 2の剰余cがあります。解がまったくない残基c



解が存在するcの非ゼロの剰余は、 2次剰余と呼ばれます。 解が存在しない剰余cは2次剰余と呼ばれます。 二次的な非控除は控除であることに注意する価値があります。二次的であることは彼が幸運ではなかったというだけです。 ルジャンドル記号 cと2乗の関係を示します。適用される場合は1（つまり、 cは二次剰余）、-1が適用されない場合（つまりcは二次剰余）、 c =0̅の場合は0です。 方程式y ² = cの解の数は 。



楕円曲線に戻ります。 固定xのオプションyの数、曲線上のポイントの総数y ² = x ³ -k∙xは、すべてのxを合計し、特別なポイントを忘れずに書き留めることができます。 。 前に現れなかったシンボルF _pによって、 _pを法とする剰余のフィールド（フィールド）を示すのが慣例です。



これで、2乗和のpの展開の成分の約束された式を提示する準備ができました。 定理 gを任意の2次非剰余とします。 pを4で除算して余り1が得られる場合、



また、最初の括弧内の数字は奇数の整数であり、2番目の括弧内の数字は偶数の整数です。 pを4で除算すると、剰余が3になる場合、括弧内の両方の合計はゼロになります（つまり、楕円曲線上の点の数はp + 1になります ）。

証明

ポストはすでに長いため、証拠はネタバレの下で削除されます。 知覚を損なうことなく安全にスキップできます。

暗号化はどうですか？

ルジャンドル記号をp回カウントしてaとbを計算するのは実用的ではありません。 Cornacchiaアルゴリズムは、これをはるかに高速に処理できます 。 実際の利点は、a、bの式を反対方向に使用することです。展開p = a ² + b ^2は 、 aとbの順列と符号の変化まで一意であることが証明できるため、 aとbを見つけることは曲線y上の点の数を知ることを意味します² = x ³ -t∙x非ゼロtの場合、これはp + 1±2aおよびp + 1±2bになります。



曲線上のポイントの数を知ることは、この曲線上の暗号化にとって重要です。 楕円曲線では、ゼロの役割の特別なポイントOを使用して、ポイントを追加する操作（暗号化について少なくとも何かを知っている人なら誰でも聞いているかもしれません）を入力できます。 加算演算に基づいて、自然数による乗算を決定できます： 2P = P + P 、 3P = P + P + Pなど 。 したがって、 nが曲線の次数である場合、任意の点Pに対してnP = Oであることを証明できます。 n、c、dが わかれば 、 x∙（cP）= dPという形式の方程式を解くことができます。剰余の除算に完全に類似しています。高度なユークリッドアルゴリズムは、 c∙x + n∙y = 1 、 x x（cP）+ y∙（nP）= P 、つまりx∙（cP）= P. さらに、 c、dが不明で、 cPとdPが座標で与えられている場合、有効な分割方法は一般に不明です。



与えられた曲線上の点の数を計算することはかなり困難です（多項式アルゴリズムが存在しますが、実際にはかなり遅いです）。 ポイント数に関するいくつかのプロパティを使用して曲線を作成するには、必要なものが得られるまでランダム係数を取り、サイクル内のポイント数を計算しようとしますが、待つ必要があります。 幸いなことに、別の方法があります。



4k + 1の形式の素数と特別な形式の曲線y ² = x ³ -t∙x （ある意味、任意の非ゼロtの曲線）に満足し、点数p + 1±2aまたはp + 1± 2b 、あなたはそれを取ることができます。 他の曲線はどうですか？



少し後の1911年に、別の著者von Schrutkaが y ² = x ³ -tの形式、 6k + 1の単純な形式、および表現p = a ² + 3b ^2の曲線について同様の結果を得ました 。 そのため、曲線y ² = x ³ -t上の点の数を見つけるために、Cornacchiaアルゴリズムが再び可能にします。





後に、楕円曲線の理論が発展するにつれて、 4p = a ' ² + d∙b' ^2の表現がある場合、 dは自然であり、4で割ると、0または3の剰余が得られ、 pとは互いに素であることが明らかになりました大きすぎると、 pが非常に大きい場合でも、正確にp + 1±a 'ポイントを持つ曲線を効率的に作成できます。 2つの最小値d = 3およびd = 4は、曲線y ² = x ³ -tおよびy ² = x ³ -t∙xに対応します。 d = 163の例：



奇数p≠163の場合、この方程式は楕円曲線を定義します。 4pが整数a '、b'でa ' ² + 163b' ²の形式で表現できる場合、楕円曲線上の点の数はp + 1±a 'です。 そうでない場合は、 p + 1です。 残念ながら、この証明は「ハード」理論を使用しているため、ここではヒントすらありません。

ただし、通常、ラジカルが取得されます。 たとえば、 d = 15の場合 ： 。 4pが合計a ' ² + d∙b' ^2に分解され、 pが d と互いに素である場合、すべてのラジカルが必ず抽出され（たとえば、 d = 15の場合、 c ² =5̅の剰余cが常に存在します ）、次の楕円曲線が得られます希望のポイント数。