RSA暗号計算
2007/05/30 後 保範 (Ushiro Yasunori、東京工芸大学)
2008/10/01 改訂((4)QSプログラムの追加)
1. RSA暗号とユークリッド互助法
(1) 説明資料1 | 、
印刷資料1 |
(2) 最大公約数Javaプログラム GCD.java,
| BGCD.java
(3) 素数計算Javaプログラム | Prime.java
2. 多数桁の因数分解の方法
| 説明資料2 | 、
印刷資料2 |
3. QS(2次ふるい法)
(1) QS説明資料 | 、
QS印刷資料 |
(2) QS原理プログラム(ふるいは除算、行列計算はA+E)
Java: QS.java,
| TQS.java
(3) QSプログラム(ふるい改良1、行列計算はA+E)
Java: | QS2.java,
| TQS2.java
ふるい改良1: 本来のふるいを使用し、基本基底(-1を含まず)内だけ採用
同入力データは in.txt名のファイルに下記の順に改行して与える
分解対象数、最大素数番号、1回のふるい数、出力指定(0,1,2)
同入力データ例 | in1.txt,
| in2.txt,
| in3.txt,
| in4.txt
(3) QSプログラム(ふるい改良2、行列計算はAだけ使用)
Java: | QS3.java,
| TQS3.java
ふるい改良2: 基本基底(-1を含む)以外でも2個存在すると採用
同入力データは data.txt名のファイルに下記の順に改行して与える
分解対象数、最大素数番号、1回のふるい数、基本外素数比、出力指定(0,1,2)
同入力データ例 | data1.txt,
| data2.txt,
| data3.txt,
| data4.txt
(4) QSプログラム(ふるい改良2、行列計算はAをbitに詰める)
Java: | QS4.java,
| TQS4.java
Aをbitに詰める: 0-1行列なのでintに32データを詰めて計算
入力データは(3)のものと同一
(5) QSプログラム(ふるい改良3、基底で割るテストの高速化)
Java: | QS5.java,
| TQS5.java
4. MPQS(複数多項式2次ふるい法)
| 説明資料3 | 、
印刷資料3 |
5. 0-1行列の従属行の計算
説明資料4 | 、
印刷資料4 |
6. GNFS(一般数体ふるい法)
説明資料5 | 、
印刷資料5 |
7. MBPS(多重基底多項式ふるい法
説明資料6 | 、
印刷資料6 |