» www.Giftbox.Az - Bir birindən gözəl hədiyyə satışı
ウィキペディアランダム
毎日カテゴリ
共有: WhatsappFacebookTwitterVK

素因数分解

素因数分解 (そいんすうぶんかい、: prime factorization) とは、ある正の整数素数の形で表すことである[1]

素因数分解には次のような性質がある。

例えばを素因数分解すれば、となる。

インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。

通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。

素因数分解アルゴリズム

正の整数 N を素因数分解するための最も単純な方法は、2 から順に N までの素数で割っていく方法(試し割り法)である。しかし、N が大きくなると、この方法では困難である。

大きな N に対しては以下のような方法がある。

素元分解

整域において素因数分解(に相当する概念)を考える問題は、代数学における古典的な問題の一つである。

一般に可換環 R においては、「割り切る」という関係を単項イデアルの包含関係により定めることができる。すなわち、a, bR の生成する単項イデアル (a) = aR, (b) = bR に対し、(a) ⊃ (b) のときに a | b と書いて、ab を割り切る、とか、ab の約元である、とか、ba の倍元である、などという。言い換えると、ab を割り切るとは、b = ac を満たすような R可逆でも 0 でもない元 c が存在することをいう。

可逆でも 0 でもない R の元が、2つの非可逆元の積として表せるとき、可約であるといい、そうでないとき既約であるという。単項イデアル (p) が自明でない素イデアルであるとき、p素元という。素元既約元であるが、一般に逆は成立しない。

素元分解整域

R の元を既約元の積に表すことを既約元分解、素元の積に表すことを素元分解という。既約元分解が一意であるような環を素元分解整域もしくは一意分解環という(任意の元が素元の積に表せるなら、その表し方は一意である)。有理整数全体の成す環 Z上の多項式環 K[x] などは素元分解整域である(高校数学でいう多項式の“因数分解”とは、通常有理数体 Q 上の一変数多項式環における素元分解のことである)。これらの環はユークリッド整域にもなっているが、一般にユークリッド整域は単項イデアル整域であり、単項イデアル整域は素元分解整域になる。

素元分解整域でない例として有理数体 Q に方程式 x2 + 5 = 0 の根を添加した代数体 Q(−5)整数環 Z[−5]6 を既約分解することを考えてみる。整数 Z の範囲では 2 × 3(と同値なもの)のみであるが、Z[−5] の範囲では

6 = 2 × 3 = (1 + −5)(1 − −5)

と本質的に異なる2通りに既約分解される。したがって Z[−5] は素元分解整域ではない。しかし、イデアルとしては (2), (3)(1 ± −5) はさらに分解できて、素イデアルの積としては一意に

(6) = (2, 1 + −5)2(3, 1 + −5)(3, 1 − −5)

と分解される。一般に、代数体の整数環はデデキント環であり、素イデアルの積に一意的に分解する。

このような考察はクンマー理想数の理論に始まると考えられる。クンマー以降、デデキントイデアル論などを経て代数的整数論の基盤となっている。

素因数分解の記録

Cunningham Project とは、b = 2, 3, 5, 6, 7, 10, 11, 12 および多くの自然数 n に対し、bn ± 1 を素因数分解しよう、というプロジェクトである。RSA チャレンジについては(RSA暗号#RSA暗号解読コンテスト )を参照。

  • 2005年4月:11281 + 1 の約数として現れる176桁の合成数が素因数分解される((一般数体ふるい法)(英語版)立教大学NTT、富士通研究所)
  • 2005年5月:200桁の合成数 RSA-200(RSAチャレンジ)が素因数分解される(一般数体ふるい法、Bahr、Boehm、Franke、Kleinjung)
  • 2006年8月:10381 + 1 から67桁の素数が分解される(楕円曲線法、B. Dodson)
  • 2006年9月:7352 + 1 の約数として現れる128桁の合成数が素因数分解される(一般数体ふるい法、情報通信研究機構富士通、富士通研究所、フィールドプログラマブルゲートアレイおよびダイナミックリコンフィギュラブルプロセッサを用いた専用ハードウェアを初めて使用)
  • 2007年5月:21039 − 1 の約数として現れる307桁の合成数が素因数分解される(特殊数体ふるい法、NTT、ドイツのボン大学、スイス連邦工科大学との共同研究)
  • 20??年: 200桁(663ビット)
  • 2010年1月:232桁(768ビット)(NTT、スイス連邦工科大学ローザンヌ校 (EPFL)、独ボン大学、フランス国立情報学自動制御研究所 (INRIA)、オランダ国立情報工学・数学研究所 (CWI)。一般数体ふるい法。300台PCの並列計算処理。約3年)

多項式時間で解いた記録

多項式時間で解かれた記録は以下である(全て量子コンピュータによる記録である。)。

  • 2001年 - 15(=3×5)の分解に成功(IBM)
  • 2012年 - 21(=3×7)の分解に成功(ブリストル大学)

関連項目

参考文献

  • 和田秀男『コンピュータと素因子分解』遊星社、1999年4月1日。ISBN (978-4795268890)。 
  • (Crandall, Richard)、Pomerance, Carl 著、和田秀男 訳『素数全書 計算からのアプローチ』朝倉書店、2010年9月10日。ISBN (978-4254111286)。 
  • 山本, 芳彦『数論入門』岩波書店〈現代数学への入門〉、2003年。ISBN (4-00-006878-4)。 
  • 岡本和夫、森杉薫、根本博、永田潤一郎『未来へ広がる数学』 3巻、新興出版社啓林館、2022年2月10日、25頁。ISBN (978-4-402-02187-0)。 

外部リンク

  • Cunningham Project
  1. ^ a b 岡本 et al. 2022.
ウィキペディア、ウィキ、本、library、論文、読んだ、ダウンロード、自由、無料ダウンロード、mp3、video、mp4、3gp、 jpg、jpeg、gif、png、画像、音楽、歌、映画、本、ゲーム、ゲーム。