正方形の合同
Congruence used in integer factorization algorithms

数論において、平方合同は整数因数分解アルゴリズムでよく使用される合同です。

導出

フェルマーの因数分解法は、正の整数 nが与えられたとき、次の等式を満たす数xとyを見つけることに依存する。

x 2 − y 2 = n {\displaystyle x^{2}-y^{2}=n}

次に、 n = x 2 − y 2 = ( x + y )( x − y )を因数分解します。このアルゴリズムは実際には遅くなります。なぜなら、そのような数を多数探索する必要があり、方程式を満たす数はごくわずかだからです。しかし、より弱い平方合同条件を満たすことができれば、 nも因数分解できます。

x 2 ≡ y 2 ( mod n ) {\displaystyle x^{2}\equiv y^{2}{\pmod {n}}}
x ≢ ± y ( mod n ) {\displaystyle x\not \equiv \pm y\,{\pmod {n}}}

ここから簡単に推測できるのは

x 2 − y 2 ≡ 0 ( mod n ) {\displaystyle x^{2}-y^{2}\equiv 0{\pmod {n}}}
( x + y ) ( x − y ) ≡ 0 ( mod n ) {\displaystyle (x+y)(x-y)\equiv 0{\pmod {n}}}

これは、n が 積 ( x + y )( x − y )を割り切れることを意味します。2つ目の非自明性条件は、n が( x + y ) も ( x − y ) も個別に割り切れないことを保証します。したがって、 ( x + y ) と ( x − y ) はそれぞれnの因数の一部を含みますが、すべてではありません。そして、( x + y , n ) と ( x − y , n ) の最大公約数はこれらの因数になります。これはユークリッドの互除法を用いて素早く行うことができます。

平方の合同性を求めるアルゴリズムのほとんどは、実際には非自明性を保証するものではなく、単にその可能性を高めるだけです。見つかった合同性が自明である可能性もあり、その場合は別のxとyを探し続ける必要があります。

平方数の合同性は、整数因数分解アルゴリズムにおいて非常に有用です。逆に、合成数を法とする平方根を求めることは、その数を因数分解することと確率的多項式時間で等価となるため、任意の整数因数分解アルゴリズムを平方数の合同性の特定に効率的に使用できます。

因数基数の使用

ディクソンの因数分解法によって開拓され、連分数因数分解、二次ふるい、一般数体ふるいによって改良された手法は、因数底を使用して平方数の合同性を構築することです。

1 つのペアを直接探す代わりに、 y が小さな素因数 (滑らかな数 ) のみを持つ多くの「関係」を見つけ、それらのいくつかを掛け合わせて右側に 正方形を取得します。 x 2 ≡ y 2 ( mod n ) {\displaystyle \textstyle x^{2}\equiv y^{2}{\pmod {n}}} x 2 ≡ y ( mod n ) {\displaystyle \textstyle x^{2}\equiv y{\pmod {n}}}

yを全て因数分解できる小さな素数の集合を因数基数と呼びます。各行がy を1つ、各列が因数基数の1つの素数に対応し、要素がyにおけるその因数が出現する回数の偶奇性（偶数または奇数）となるような論理行列を構築します。目標は、合計がすべてゼロの行となる行のサブセットを選択することです。これは、積が平方数、つまり因数分解の指数が偶数のみとなるy値の集合に対応します。x値とy値の積は、平方数の合同を形成します。

これは古典的な連立一次方程式の問題であり、行数が列数を超えるとすぐにガウス消去法を用いて効率的に解くことができます。最初の解が自明な合同となる場合に備えて、行列の零空間に複数の解が存在するようにするために、追加の行がしばしば追加されます。

この手法の大きな利点は、関係の探索が驚くほど並列化されていることです。多数のコンピュータを投入して、x値の様々な範囲を探索し、得られたyを因数分解することができます。中央コンピュータに報告する必要があるのは、発見された関係のみであり、特に急いで報告する必要はありません。探索を行うコンピュータを信頼する必要さえありません。報告された関係は最小限の労力で検証できます。

この技法には多くの応用があります。例えば、 「大きな素数」の変種は、 yが因数基数に完全に因数分解できる関係に加えて、 yが1つの大きな因数を除いて完全に因数分解できる「部分関係」も収集します。同じ大きな因数を持つ2つ目の部分関係を1つ目の部分関係に掛け合わせると、「完全な関係」が得られます。

例

35を因数分解する

n  = 35と すると、

6 2 = 36 ≡ 1 = 1 2 ( mod 35 ) {\displaystyle \textstyle 6^{2}=36\equiv 1=1^{2}{\pmod {35}}} 。

したがって、

gcd ( 6 − 1 , 35 ) ⋅ gcd ( 6 + 1 , 35 ) = 5 ⋅ 7 = 35 {\displaystyle \gcd(6-1,35)\cdot \gcd(6+1,35)=5\cdot 7=35}

1649を因数分解する

n = 1649を用いて 、非平方数の積から構成される平方数の合同性を求める例として（ディクソンの因数分解法を参照）、まずいくつかの合同性を得る。

41 2 ≡ 32 = 2 5 ( mod 1649 ) , {\displaystyle 41^{2}\equiv 32=2^{5}{\pmod {1649}},}
42 2 ≡ 115 = 5 ⋅ 23 ( mod 1649 ) , {\displaystyle 42^{2}\equiv 115=5\cdot 23{\pmod {1649}},}
43 2 ≡ 200 = 2 3 ⋅ 5 2 ( mod 1649 ) . {\displaystyle 43^{2}\equiv 200=2^{3}\cdot 5^{2}{\pmod {1649}}.}

これらのうち、1番目と3番目は因数として小さな素数のみを持ち、これらの積は各小さな素数の偶数乗となるため、平方

32 ⋅ 200 = 2 5 + 3 ⋅ 5 2 = 2 8 ⋅ 5 2 = ( 2 4 ⋅ 5 ) 2 = 80 2 {\displaystyle 32\cdot 200=2^{5+3}\cdot 5^{2}=2^{8}\cdot 5^{2}=(2^{4}\cdot 5)^{2}=80^{2}}

正方形の合同性を得る

32 ⋅ 200 = 80 2 ≡ 41 2 ⋅ 43 2 ≡ 114 2 ( mod 1649 ) . {\displaystyle 32\cdot 200=80^{2}\equiv 41^{2}\cdot 43^{2}\equiv 114^{2}{\pmod {1649}}.}

80と114の値をxとyの値として使うと、因数が得られます

gcd ( 114 − 80 , 1649 ) ⋅ gcd ( 114 + 80 , 1649 ) = 17 ⋅ 97 = 1649. {\displaystyle \gcd(114-80,1649)\cdot \gcd(114+80,1649)=17\cdot 97=1649.}

参照

参考文献

  • Bressoud, David M. (1989). 「8. 二次ふるい」. 因数分解と素数判定(PDF) . 数学学部テキスト. Springer-Verlag. ISBN 0-387-97040-1。
  • ライゼル、ハンス (1994).素数と因数分解のためのコンピュータ手法. 数学の進歩. 第126巻 (第2版). Birkhaüser. ISBN 0-8176-3743-5。
  • ワグスタッフ, サミュエル・S・ジュニア(2013). 『因数分解の喜び』 学生数学図書館 第68巻. プロビデンス, ロードアイランド州:アメリカ数学会. pp.  195– 202. ISBN 978-1-4704-1048-3。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Congruence_of_squares&oldid=1320712524"