Wikipedia

素因数分解

正の整数を素数の積の形で表すこと
曖昧さ回避 「因数分解」とは異なります。

素因数分解（そいんすうぶんかい、英: prime factorization）とは、正の整数を素数の積の形で表すことである[1]。

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

例えば 48 を素因数分解すると 24 × 3 となる。

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

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

素因数分解アルゴリズム

編集

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

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

素元分解

編集

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

一般に可換環 R においては、「割り切る」という関係を単項イデアルの包含関係により定めることができる。すなわち、a, b ∈ R の生成する単項イデアル (a) = aR, (b) = bR に対し、(a) ⊃ (b) のときに a | b と書いて、a は b を割り切る、とか、a は b の約元である、とか、b は a の倍元である、などという。言い換えると、a が b を割り切るとは、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暗号解読コンテスト を参照。

多項式時間で解いた記録

編集

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

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

関連項目

編集

脚注

編集
  1. ^ a b 岡本 et al. 2022.
  2. ^ https://www.imes.boj.or.jp/research/papers/japanese/kk18-b1-3.pdf 1ページ
  3. ^ https://fussy.web.fc2.com/algo/math11_factorization.htm

参考文献

編集
  • 和田秀男『コンピュータと素因子分解』遊星社、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。 

外部リンク

編集
「https://ja.wikipedia.org/w/index.php?title=素因数分解&oldid=102138633」から取得