NAS2007予稿執筆中

5/11提出期限のNAS2007予稿を執筆中。
自身初の試みで、少し緊張しています。今日はその書き出しを公開。

擬似ニュートン法による代数平方根の計算

Computation of algebraic square root by Quasi-Newton’s method

1. はじめに
RSA暗号は多数桁数での因数分解の困難性を利用している。現在、1024ビットのRSA暗号の解読はスーパーコンで数千年かかると言われており、解読は困難である。多数桁数の因数分解、とくにRSA暗号解読に使用される因数分解には篩系の解法を用いる。篩系の解法としてMPQS(複数多項式2次篩法)、GNFS(一般数体篩法)、MBPS(多重基底多項式篩法)がある。さらにMBPS(多重基底多項式篩法)にはDBPS(2重基底多項式篩法)、TBPS(3重基底多項式篩法)の2種類がある。ここでは特にGNFS(一般数体篩法)、TBPS(3重基底多項式篩法)で行われる代数平方根の計算について述べる。一般的に代数平方根の計算には、中国剰余定理系の解法が用いられているが、我々は擬似ニュートン法を使用して非線形方程式を反復計算し求める解法を検討している。

擬似ニュートン法について学んでいきます。
なるべくこのﾌﾞﾛｸﾞにもｱｯﾌﾟしていく予定です。

じゃまた。