数論システム NZMATH の 開発と応用 巨大な自然数の高速計算に すぐ使えるプログラム 理工学研究科 中村 憲 数理情報科学専攻 内山 成憲 2006年12月8日 東京国際フォーラム 本講演の内訳 • • • • どうして必要なのか あるもので間に合わないのか 何ができ, どうやって使うのか 手に入れるには, また開発に参加するには 30 September 2015 数論システム NZMATH 2 どうして必要なのか…例えば暗号 • みんなが広く使える暗号の必要性 – 不特定多数がアクセスできる状況の維持 – 情報の通信や保存の機密性･安全性の確保 • 暗号の仕組は一般に公開されている – 平文を暗号文にする暗号鍵 これが公開されている公開鍵暗号もある – 暗号文を平文に戻す復号鍵 正当な利用者のみの秘密 • 復号鍵は暗号文や暗号鍵から計算困難 – その保証に巨大な自然数の計算がしばしば必要 (あまり厳密ではないが印象を理解する為の説明を少し詳しくする) 30 September 2015 数論システム NZMATH 3 どうして必要なのか…公開鍵暗号 • 一方で復号鍵は暗号鍵から計算困難 • 他方で復号鍵は暗号鍵の逆の操作をする 暗号鍵 平文 計算困難 暗号文 復号鍵 簡単 異なる自然数 p, q p, q を隠す 分解は極めて困難 30 September 2015 数論システム NZMATH 積 n＝p×q n を公開する 4 どうして必要なのか…整数因数分解 • 21桁の n を n＝p×q, p≠1, q≠1 と分解したい: n＝400849298419414319179 • 小さい奇数 3, 5, 7, 9, … で順に試し割算する: 全部で 10010610563 回が必要で 3.2GHzのパソコンで8時間45分30秒かかり p＝20021221127, q＝ 20021221277 • 逆に p×q は一瞬で, 手計算でも8時間は不要 • この方法では n が50桁以上なら, これ迄現存し た計算機の全能力を総動員したとしても不可能 • 数論アルゴリズムで n が百数十桁なら分解可能 30 September 2015 数論システム NZMATH 5 あるもので間に合わないのか 1. Maple, Mathematica, Macsyma … 高額 2. Magma … 開発援助費程度 ☆これらはソース非公開で細部修正できない☆ 3. Pari/GP, Kant/Kash, SIMATH/SimCalc a. 基本的に無料ライセンス b. 利用言語と開発言語が違う c. 開発者が数論アルゴリズム以外に忙殺される (メモリ管理, 多倍長, データ構造, 対話式インタプリタ) ☆このうち b, c は 1, 2 にも当て嵌まる☆ 30 September 2015 数論システム NZMATH 6 あるもので間に合わないのか 利用者=開発者 … Python 1. 2. 3. 4. メモリ管理, 多倍長を備えている 豊富なデータ構造を持つオブジェクト指向 利用言語と開発言語が同じスクリプト言語 広範に利用されている易しい言語 – 計算速度より開発速度を重視 – どんな OS でも移植が簡単にできる 5. 他の言語との相互リンクができる – 計算速度の向上や他システムの利用 30 September 2015 数論システム NZMATH 7 何ができ, どうやって使うのか arith1 (初等数論), bigrandom (巨大乱数), combinatorial (初等組合せ論), elliptic (楕円曲線), equation (多項式の根) , factor (自然数因数分解), finitefield (有限体), gcd (互除法), group (群), imaginary (近似複素数), integerResidueClass (整数剰余), lattice (格子), matrix (行列), multiplicative (乗法的関数), permute (置換群), polynomial (多項式), prime (素数判定), quad (二次体), rational (有理数), rationalFunction (有理関数), real (近似実数), ring (環), vector (ベクトル), zassenhaus (整多項式因数分解) 30 September 2015 数論システム NZMATH 8 何ができ, どうやって使うのか 応 用 基 礎 近似実数 近似複素数 多項式の根 群 置換群 環 有理数 整数剰余 整多項式 因数分解 二次体 多項式 有限体 楕円曲線 有理関数 ベクトル, 行列, 格子 初等数論 互除法 乗法的関数 素数判定 自然数因数分解 補助 30 September 2015 巨大乱数 予定 初等組合せ論 半群, 代数拡大, 局所体 数論システム NZMATH 9 何ができ, どうやって使うのか 先の例の n＝ 400849298419414319179 の因数分解を実演してみます. •まず python (command line) を起動します. •次の二つのコマンドを実行します. import nzmath.factor.methods nzmath.factor.methods.mpqs(400849298419414319179) 30 September 2015 数論システム NZMATH 10 手に入れるには また開発に参加するには • 公式サイト: http://tnt.math.metro-u.ac.jp/nzmath/ • メイリングリスト: http://tnt.math.metro-u.ac.jp/nzmath/ml.html • 開発プロジェクトページ: http://sourceforge.net/projects/nzmath/ • 開発グループ: http://nzmath.sourceforge.net/ 30 September 2015 数論システム NZMATH 11 Please read README for more details. Python is available from http://www.python.org/ . Windows Installer NZMATH Version 0.5.1 解凍レンジ マイ コンピュータ プロパティ 詳細設定 環境変数 ユーザ環境変数 PYTHONPATH C:\Documents and Settings\nakamula\ デスクトップ\nzmath-seeds-2006\NZMATH-0.5.1 システム環境変数 Path ;C:\Python25 please refer Tutorial. 30 September 2015 数論システム NZMATH 12 御静聴ありがとうございました 興味のある方は本文に subscribe とだけ書いたメイルを [email protected] 宛に出してください 30 September 2015 数論システム NZMATH 13
© Copyright 2024 ExpyDoc
