数論システム NZMATH の 開発と応用 巨大な自然数の高速計算に すぐ使えるプログラム 理工学研究科 数理情報科学専攻

Presentation on theme: "数論システム NZMATH の 開発と応用 巨大な自然数の高速計算に すぐ使えるプログラム 理工学研究科 数理情報科学専攻"— Presentation transcript:

1 数論システム NZMATH の 開発と応用 巨大な自然数の高速計算に すぐ使えるプログラム 理工学研究科 数理情報科学専攻
17 November 2018 数論システム NZMATH の 開発と応用 巨大な自然数の高速計算に すぐ使えるプログラム 理工学研究科 数理情報科学専攻 中村 憲 内山 成憲 2006年12月8日 東京国際フォーラム 中村 憲, 内山 成憲

2 本講演の内訳 どうして必要なのか あるもので間に合わないのか 何ができ, どうやって使うのか 手に入れるには, また開発に参加するには
17 November 2018 数論システム NZMATH

3 (あまり厳密ではないが印象を理解する為の説明を少し詳しくする)
どうして必要なのか…例えば暗号 みんなが広く使える暗号の必要性 不特定多数がアクセスできる状況の維持 情報の通信や保存の機密性･安全性の確保 暗号の仕組は一般に公開されている 平文を暗号文にする暗号鍵 これが公開されている公開鍵暗号もある 暗号文を平文に戻す復号鍵 正当な利用者のみの秘密 復号鍵は暗号文や暗号鍵から計算困難 その保証に巨大な自然数の計算がしばしば必要 (あまり厳密ではないが印象を理解する為の説明を少し詳しくする) 17 November 2018 数論システム NZMATH

4 どうして必要なのか…公開鍵暗号 一方で復号鍵は暗号鍵から計算困難 他方で復号鍵は暗号鍵の逆の操作をする 暗号鍵 計算困難 平文 暗号文
簡単 異なる自然数 p, q 積 n＝p×q p, q を隠す n を公開する 分解は極めて困難 17 November 2018 数論システム NZMATH

5 どうして必要なのか…整数因数分解 21桁の n を n＝p×q, p≠1, q≠1 と分解したい:
小さい奇数 3, 5, 7, 9, … で順に試し割算する: 全部で 回が必要で 3.2GHzのパソコンで8時間45分30秒かかり p＝ , q＝ 逆に p×q は一瞬で, 手計算でも8時間は不要 この方法では n が50桁以上なら, これ迄現存した計算機の全能力を総動員したとしても不可能 数論アルゴリズムで n が百数十桁なら分解可能 17 November 2018 数論システム NZMATH

6 あるもので間に合わないのか Maple, Mathematica, Macsyma … 高額 Magma … 開発援助費程度
☆これらはソース非公開で細部修正できない☆ Pari/GP, Kant/Kash, SIMATH/SimCalc 基本的に無料ライセンス 利用言語と開発言語が違う 開発者が数論アルゴリズム以外に忙殺される (メモリ管理, 多倍長, データ構造, 対話式インタプリタ) ☆このうち b, c は 1, 2 にも当て嵌まる☆ 17 November 2018 数論システム NZMATH

7 あるもので間に合わないのか 利用者=開発者 … Python
メモリ管理, 多倍長を備えている 豊富なデータ構造を持つオブジェクト指向 利用言語と開発言語が同じスクリプト言語 広範に利用されている易しい言語 計算速度より開発速度を重視 どんな OS でも移植が簡単にできる 他の言語との相互リンクができる 計算速度の向上や他システムの利用 17 November 2018 数論システム NZMATH

8 数論システム NZMATH 17 November 2018 何ができ, どうやって使うのか arith1 (初等数論), bigrandom (巨大乱数), combinatorial (初等組合せ論), elliptic (楕円曲線), equation (多項式の根) , factor (自然数因数分解), finitefield (有限体), gcd (互除法), group (群), imaginary (近似複素数), integerResidueClass (整数剰余), lattice (格子), matrix (行列), multiplicative (乗法的関数), permute (置換群), polynomial (多項式), prime (素数判定), quad (二次体), rational (有理数), rationalFunction (有理関数), real (近似実数), ring (環), vector (ベクトル), zassenhaus (整多項式因数分解) 17 November 2018 数論システム NZMATH 中村 憲, 内山 成憲

9 何ができ, どうやって使うのか 応用 基礎 近似実数 近似複素数 多項式の根 整多項式 因数分解 二次体 楕円曲線 群 置換群
数論システム NZMATH 17 November 2018 何ができ, どうやって使うのか 応用 近似実数 近似複素数 多項式の根 整多項式 因数分解 二次体 楕円曲線 群 置換群 環 有理数 多項式 有理関数 整数剰余 有限体 ベクトル, 行列, 格子 初等数論 互除法 乗法的関数 初等組合せ論 素数判定 自然数因数分解 基礎 補助 巨大乱数 予定 半群, 代数拡大, 局所体 17 November 2018 数論システム NZMATH 中村 憲, 内山 成憲

10 何ができ, どうやって使うのか 先の例の n＝ 400849298419414319179 の因数分解を実演してみます.
まず python (command line) を起動します. 次の二つのコマンドを実行します. import nzmath.factor.methods nzmath.factor.methods.mpqs( ) 17 November 2018 数論システム NZMATH

11 手に入れるには また開発に参加するには 公式サイト: メイリングリスト: 開発プロジェクトページ: 開発グループ:
メイリングリスト: 開発プロジェクトページ: 開発グループ: 17 November 2018 数論システム NZMATH

12 Please read README for more details.
Python is available from . 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. 17 November 2018 数論システム NZMATH

13 御静聴ありがとうございました 興味のある方は本文に subscribe とだけ書いたメイルを 宛に出してください
宛に出してください 17 November 2018 数論システム NZMATH