暗号アルゴリズムの詳細評価に関する報告書

2002 年 3月 18日

立 教 大 学木田 祐司

Chapter 1

素因数分解実験プロジェクト
2002/1/19

CRYPTREC 研究会 at 立教大学 S302 教室
2003/3/31 改訂
木田 祐司

この文書についてここに集めた文書は 2001 年度に立教大学で行われたセミナーの配布資料である1 。
Chapter 1 で全体の概論について述べ、Chapter 2-5 で各論の概論を述べる。これ以上の詳細な内容は
2002,2003 年度のセミナーで研究される予定である。

1.1

このプロジェクトの目的

1024bits の合成数の素因数分解にかかる時間を評価すること。そのために
1. 一般数体ふるい法 (GNFS) のプログラムを独自に開発し、数値実験を行う。
2. GNFS の理論的解析を行い、改良の余地を研究する。
より広い観点からの評価はすでに次の論文で行われている。我々の目的はこれらと（ある程度）独立に評価を行うことである。言いかえると、これらの論文の関連する部分の妥当性を判断することでもある。
è [Arjen K. Lenstra, Eric R. Verheul] "Selecting Cryptographic Key Sizes", http://www.cryptosavvy.com/Joc.pdf
è [Robert D. Silverman] "A Cost-Based Security Analysis of Symmetric and Asymmetric Key
Lengths", RSA Laboratories
ftp://ftp.rsasecurity.com/pub/pdfs/bulletn13.pdf

1.2

素因数分解の現状

Scott Contini の home page は非常に役に立つ。この小論でもここにある文書をたびたび紹介する。
http://www.crypto-world.com/FactorAnnouncements.html
1 実際のセミナーで補充した内容は収められていない。また冗長なため削除した部分もそのまま残している。読みやすくはないことをあらかじめお断りしておく。

1

CHAPTER 1. 素因数分解実験プロジェクト

2

1.2.1

各種の分解法1. 試し割り算
2. p Ä 1 法
3. モンテカルロ法 (ö法)
4. 連分数法
5. 楕円曲線法
6. 二次ふるい法
7. 数体ふるい法

1.2.2

1970 年以降の記録

TABLE 1: Historical Factoring Records
Silverman の前記報告文書より引用および追加
Year Size
1970

39

Number
2

128
223

+1
Ä1

2
3225 Ä 1
591 Ä 11193 + 1
1071 Ä 1

Who

MethodHardware

Brillhart/Morrison
Wunderlich

CFRAC
CFRAC

IBM Mainframe
IBM Mainframe

GerverWagstaã
Davis/Holdridge

QS
CFRAC
QS

HP-3000
IBM Mainframe
Cray

1978
1981
1982
1983
1984

45
47
51
63
71

1986

87

1987
1988
1990

90
100
111

Silverman
160
5 +1
Silverman
104
11 + 1 Internet
2484 + 1
Lenstra/Manasse

1991
1992
1996
1998
1999
2002

116
129
130
140
155
158

10142 + 1
RSA-129
RSA-130
RSA-140
RSA-5122953 + 1

Davis/Holdridge

5128 + 1

Lenstra/Manasse
AtkinsMontgomery
Montgomery
Montgomery
Bahr/Franke/Kleinjung

QS

Cray

MPQS
MPQS
MPQS

LAN Sun-3's
LAN Sun-3'sDistributed

MPQS
MPQS
MPQS
GNFS
GNFS
GNFS
GNFS

Distributed
Distributed
Distributed
Distributed
Distributed
Distributed
LAN PC's ?

CFRAC = Continued FRACtion = 連分数
QS = Quadratic Sieve = 二次ふるい
MPQS = Multiple Polynomial Quadratic Sieve = 複数多項式二次ふるい
GNFS = General Number Field Sieve = 一般数体ふるい
TABLE 2: Historical Factoring Records: Special Types
Silverman の前記報告文書より引用および追加
1990

148(155)

1999 211
2000 233
2003 244

9

22 + 1

Lenstra/Manasse
10 Ä 1 The Cabal
2773 + 1 The Cabal
2809 Ä 1 Franke+Kleinjung+Montgomery
211

SNFS
SNFS
SNFS
SNFS

Distributed
Distributed
Distributed
LAN PC's?

素因数分解の限界のもうひとつの見方として「全体の桁数に制約されない方法」を用いて「何桁の素因数が見つかったか」に注目する方向もある。これは 2001 年に 55 桁の素因数が山梨大学の宮本泉氏によって ECM(Elliptic Curve Method) で見つけられたのが最高である。

1.4. 素因数分解法のポイント

3

なぜ GNFS か

1.3

1024bits の RSA 暗号で使われる合成数 n は確実に 500bits 以上の二つの素数 p; q の積である。
この素因数 p; q を群論的方法で見つけることができるだろうか。
p Ä 1; p + 1 法では見つからないように p Ü 1; q Ü 1 は大きな素因数を持っていることだろう。

ECM では現状で 55 桁が限界であり、その進展のスピードは非常に遅い。

256bits(77 桁) の素因数を見つけることでさえ当面は達成できないと思われる。
残るは (PP)MPQS と GNFS であるが歴史的にも実際的にも GNFS が有利なことは疑いない。そこで
GNFS が対象となるわけである。

素因数分解法のポイント

1.4『ふるい (sieve)』系の素因数分解法ではどういうことを目標に新しい方法を探すのだろうか。

1.4.1

基本原理
平方差法の原理 合成数 n に対してなんらかの方法でx2 ë y 2 mod n;

x 6ë y mod nとなる整数 x; y を見つければGCD(x Ä y; n)
は n の約数となる。
こういう x; y は
xi ë yi mod n

かつ xi 6= yiとなる xi ; yi を集めて組み合わせて平方数になるものを探すという手順をとる。
例
14 Å67
31 Å67
14 Å31

ë 3
ë 20
ë 60

mod187
mod187
mod187より(14 Å31 Å67)2 ë 602 mod 187となる。
代表元を変えるというのは「加法的」な性質、素因数分解は「乗法的」な性質、それらをブレンドさせるところがポイントと言えるかもしれない。
ポイント

1.4.2

mod n での代表元を二通りにとってその素因数分解の違いを利用する。

線形代数

問題 一般にたくさんの整数 r1 ; r2 ; . . . ; rs が与えられたとき、その中から組み合わせて平方数になるものを見つけるにはどうするか。

CHAPTER 1. 素因数分解実験プロジェクト

4èまず適当な個数の素数の集合 fp1 ; p2 ; . . . ; pB g を決める。factor base という。

è次にその factor base で完全に素因数分解できてしまうもの、smooth な数という、つまり
ri =

B
Y

e(i;j)pj

j=1となる ri を B + 1 個以上捜す。これらをあらためて r0 ; r1 ; . . . ; rB としよう。
èこれらのべき指数部分に注目し、さらにそれを mod 2 で考えて次のような (Z=2Z 上の) B 次元ベクト
ルにする。
vi = (e(i; 1) mod 2; e(i; 2) mod 2; . . . ; e(i; B) mod 2)
è連立方程式を解き、自明でない関係式を求める。
c0 v0 + c1 v1 + ÅÅÅ+ cB vB ë 0 mod 2
è元に戻してcB
は平方数
r0c0 År1c1 ÅÅÅrB

ポイント r1 ; r2 ; . . . ; rs の絶対値が小さいほど良い。

1.4.3

定数倍法

アイディア 分解したい数 n に対して n=2 の近くの数を 2 倍して n を引けば代表元が "ずれる"。
例 n = 253 の場合
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)

2 Å127
2 Å1282 Å1292 Å130
2 Å131
2 Å132
2 Å1332 Å1342 Å135
2 Å136= 2 Å127= 28= 2 Å3 Å43= 22 Å5 Å13= 2 Å131= 23 Å11= 2 Å7 Å19= 2 Å2 Å67= 2 Å33 Å5= 24 Å17

ë1
ë3
ë5
ë7
ë9
ë 11
ë 13
ë 15
ë 17
ë 19

これより連立方程式を解けば (2),(4),(7),(9),(10) を組み合わせると良いことが分かる。実際
28 22 5 13 2 7 19 2 33 5 24 17
216 33 52 7 17 19

ë 3 7 17 19
ë 3 7 17 19より
216 Å32 Å52 = (28 Å3 Å5)2 ë 1
これから次を得る。
GCD(28 Å3 Å5 Ä 1; 253) = 11
ポイント smooth になってほしい数は n=2 程度の大きさ。

1.4. 素因数分解法のポイント

1.4.4

5

二次ふるい法アイディア 分解したい奇数 n に対して

pn の近くの数を 2 乗して n を引けば代表元が "ずれる"。
px = [ n] Ü m; m = 1; 2; . . .
に対して

pQ(x) = x2 Ä n ò Ü2m nを考えるということ。
n = 3937 の場合
632 Ä n642 Ä n

= 32
= 159

652 Ä n

= 288
= 419

672 Ä n= 552

662 Ä n...

= 25
= 3 Å53= 25 Å32= 419= 23 Å3 Å23の 63; 65 を組み合わせて (63 Å65)2 ë (25 Å3)2 mod n を得る。これより GCD(63 Å65 Ä 25 Å3; n) = 31。
p
ポイント smooth になってほしい数は H n 程度の大きさ。ただし m を ÜH の範囲で動か
すとする。

1.4.5

数体ふるい法アイディア 代数方程式の複素数体での解を í、mod n での解を M 、とすると íと M の式
は mod n で異なる代表元を与える。
正確に言うと、多項式 f (X) に対して(f (í)

f (M )= 0; í2 Cë 0 mod n;M 2 Zのとき、次の û は環準同型である
û: Z[í] Ä!
g(í) 7!

Z=nZ
g(M ) mod n

これによって次の図式を 2 通りに進んで、その分解の違いを利用する。この図式は Z=nZ で考えれば可換だが、Z では可換とは限らない。
a+? bí ÄÄÄÄ!
?
ûya + bMÄÄÄÄ!

Z[í] での分解?
?
yûZ での分解a + bíと a + bM が同時に smooth な a; b のペアがほしい。a + bíの smoothness は a + bíのノルム（後述）の絶対値の smoothness と同じである。

CHAPTER 1. 素因数分解実験プロジェクト

6

ポイント smooth になってほしい数は f (x) の次数を d、係数の最大値を c、変化させる a; bの最大値を H とすると
è a + bM は n1=d H 程度、
è a + bíのノルムの絶対値は c ÅH d 程度の大きさである。
d の増加に対して逆向きに反応する。最適なものをとると非常に良いものになる。

1.5

NFS

1.5.1

SNFS 概論

Special Number Field Sieve は、ターゲットの合成数 N が係数の小さな多項式 f (x) と整数 M により
f (M ) が N の倍数となっている場合を扱う。
f (x) の根の 1 つを íとし、K = Q(í) とする。
仮定として次を置く
è Z[í] は UFD(素元分解環) である。
N = f (M ) の大きさに応じて Z の素数の集合 F と OK の素元と単数の集合 G を適当にとる。
a; b を互いに素な有理整数で a + bM は F -smooth とする。つまり(1 Ä 1)a + bM =

Y

pe(p)

p2F

と完全に分解するものとする。かつ a + bíは G-smooth とする。つまり(1 Ä 2)a + bí=

Y

ôe(ô)

ô2G

と完全に素元分解されるものとする。
このようなペア (a; b) を #F + #G 個より多く集める。すると各べき指数を mod 2 で考えたベクトル( (e(p) mod 2)p2F ; (e(ô) mod 2)ô2G )は線形従属となり、適当に組み合せると、つぎのような関係式が出る。

(1 Ä 3)と Z で平方数になり、かつ(1 Ä 4)と OK で平方数になる。
(1 Ä 5)であったとしてこれを準同型

Y(ai + bi M ) = @Y(ai + bi í) =
Y

0

Y

p2F

†

Y

pe(p) A

e(ô)

ô

ô2G

(ai + bi í) = s(í)2 ;12!2s(x) 2 Z[x]1.5. NFS

7

û: Z[í] Ä!
g(í)

7!

Z=N Z
g(M ) mod N

で写せば
0
@

(1 Ä 6)

Y

p2F

12

pe(p) A ë s(M )2 mod Nとなり、ふるい法の目標である x2 ë y 2 mod N 型の合同式が得られる。
まとめると、SNFS の原理は、環準同型 û: Z[í] Ä!
g(í)

7!

Z=N Z
g(M ) mod N

による次の図式を 2 通りに進んで、その分解の違いを利用することと言える。この図式は Z=N Z で考えれば可換だが、Z では可換とは限らない。
a+? bí ÄÄÄÄ!
?
ûya + bMÄÄÄÄ!

OK での分解?
?
yûZ での分解そこで、するべきことは a + bíと a + bM が同時に smooth な a; b のペアをたくさん探すこととなる。
"ふるい"系の素因数分解法ではこの smooth な数 をたくさん見つけるところが実行時間の主要な部分となる。高速にするためにはこの検査の対象となる数の絶対値を小さくするのが非常に有効である。Number
Field Sieve では、a + bíと a + bM という二つの対象があって、前者は f (x) の次数の増加に比例して絶対値が増加し、後者はその逆になる。そこで両者の中間を探ると最適な次数があって（幸いにも）計算量が優れたものとなったのである。

1.5.2

GNFS 概論

簡単のため OK = Z[í] を仮定する。これが成立しない場合でも若干の補正で以下の議論はそのまま有効になる。補正の方法は後に述べる。
一般に整数環 OK では素元分解ができない。しかし素イデアル分解は可能である。
そこで OK については有理素数の集合 F と素イデアルの集合 G を適当にとる。さらに結果を平方数にするために何個かの平方剰余記号の集合 H を付け加える。
a; b を互いに素な有理整数で a + bM は F -smooth とする。つまり(2 Ä 1)a + bM =

Y

p2F

pe(p)

CHAPTER 1. 素因数分解実験プロジェクト

8であり、かつ単項イデアル < a + bí> は G-smooth とする2 。つまりY
P e(P)(2 Ä 2)< a + bí>=P2Gと完全に素イデアル分解されるものとする。このとき ü 2 H に関する値を次のようにおく。
ü(a + bí) = (Ä1)e(ü)
ただし a + bíは ü の modulus とは互いに素であるとする。このためには modulus を G に含まれる素イ
デアルで割れないようにとる必要がある3 。
このようなペア (a; b) を #F + #G + #H 個より多く集める。すると各べき指数を mod 2 で考えたベクトル( (e(p) mod 2)p2F ; (e(P) mod 2)P2G ; (e(ü))ü2H )は一次従属となり、適当に組み合せると、つぎのような関係式が出る。
Y(2 Ä 3)と Z で平方数になり、かつ(2 Ä 4)Y

0Y(ai + bi M ) = @p2F< ai + bi í>=†Ype(p) A

P2G

ë
êY
ü
(ai + bi í) = 1

12

P

e(P)

!2

と OK で平方イデアルになり、かつ(2 Ä 5)for 8ü 2 Hとなる。
Q(2 Ä 4); (2 Ä 5) 式は (ai + bi í) が高い確率で OK の平方数になっていることを示している。もし実際にY(2 Ä 6)(ai + bi í) = s(í)2 ; s(x) 2 Z[x]であったとすれば後は Special NFS の場合とまったく同様である。

以上での最大の問題点は (2-6) において平方根 s(í) の計算をいかにして記憶容量も時間も少なく済ませることができるかである。これは後に述べる。
OK がたとえ UFD であってもそのことを用いないで、この節の方法を適用するのが良い。イデアルの生成元と単数を求める必要がなく、プログラム作りは非常に簡明になる。

1.5.3

多項式の選択

ターゲットの合成数 N と多項式 f (x) および M の間には次の関係があった。
f (M ) ë 0 mod N
f (x) の次数は N が数十桁から二百桁程度ならば 3 から 5 にとるのが良い。
2 ここでは区別をはっきりさせるため単項イデアルは生成元を < > で囲んで表すことにする。
3 後述の "large prime" を用いる場合はそれらよりも大きくする。

1.6. RSA-1559係数を小さくする
f (x) にまず課せられる条件は a + bíのノルムが小さいことである。
f (x) = cd xd + cdÄ 1 xdÄ1 + ÅÅÅ+ c1 x + c0とすると
cd N (a + bí) = (Äb)d f (a=(Äb)) = cd ad + cdÄ 1 adÄ 1 (Äb) + ÅÅÅ+ c1 a(Äb)dÄ 1 + c0 (Äb)dであるのでこれを小さくするには、係数の絶対値を小さくすることが有効であろう。絶対値の積分を小さくすることでも良い4 。

Knuth-Schroeppel 関数値を大きくする
ふるいの効率は二次ふるい法と同様に Knuth-Schroeppel 関数によって推定することができる。それはX log P

P2G

P Ä1

;

ただし P はイデアル P に含まれる素数とするである。これが大きいほど smooth data を多く集められるということになる。
この値を多項式の係数の簡単な性質から判定することはおそらく不可能であろう。少なくとも今のところは多項式の分解（＝素数の素イデアル分解）から実際に計算するしかない。

適当な実根を持たせる
a + bíのノルムを小さくするには f (a=(Äb)) の絶対値を小さくすることが有効。a; b が動く範囲である[ÄHa ; Ha ] Ç [1; Hb ] で考えると、
f (x) に実根があってその中に ÜHa =Hb に近いものがあることが望ましいことになる。
より詳細で実践的な考察が
è [Brian Murphy] "Polynomial Selection for the Number Field Sieve Integer Factorisation Algorithm", Doctorial Thesis, 1999

においてなされている。このセミナーでも先に進んでからこの問題について扱う予定である。

1.6

RSA-155

August 22, 1999 に CWI のチームによって行われた RSA-155 の分解については次の文書が詳しい。
http://www.crypto-world.com/announcements/RSA155.txt
4 絶対値の積分は難しいので 2 乗の積分を用いるのが良い。

CHAPTER 1. 素因数分解実験プロジェクト

10

1.7

another C155

Simon Singh: "The Code Book"(サイモン・シン、青木薫訳「暗号解読」）の巻末付録には 10 個のいろ
いろな種類の暗号が問題として出されている5 。
最後の Stage 10 は 155 桁の RSA 暗号であった。これは Sweden のチームによって解かれた。同じ 155
桁でもこちらの方が若干小さい。
彼らは CWI のプログラムを用いた。線形代数の部分は Alpha の 4-processor machine 用に改造し 13日で解を求めた。詳しくは以下の文書を参照のこと。
http://answers.codebook.org

1.8

C158

2003 年 3 月現在の世界記録は 2002 年 1 月に行われた F. Bahr, J. Franke, T. Kleinjung による 158 桁である。これについては以下の文書を参照されたい。これ以上の詳しい報告は発表されていないようである。
http://www.crypto-world.com/announcements/c158.txt
http://www.ercim.org/publication/Ercim_News/enw49/franke.html

1.9

GNFS の実行の段階分け

1. 多項式探索
2. ふるい3. "åltering"
4. 線形代数
5. 代数的数の平方根

1.10

GNFS の実行に必要なリソース

1.10.1

ハードウェア多項式探索
通常の PC で十分。
ふるい
通常の PC を多数用意すれば良い。ただしメモリアクセスの速いものが望ましい。
"åltering"
まだ解明できていないが特別なものが必要ないことは確かである。
5 これは日本語訳が出たときにはすべて解かれていた。

1.10. GNFS の実行に必要なリソース

11

線形代数
64-bit multi CPU 機、あるいは LAN で結合された複数台 (16 台以上) の PC が必要
平方根
通常の PC で十分。

1.10.2

ソフトウェア多項式探索
現状は全数探索に近い。良い多項式を見つけるのは多分に偶然である。そのためいかに多数の多項式をチェックするか、あるいはいかに不要なものをスキップするかが重要となる。
ふるいline sieve については細かな高速化の余地を探る。
lattice sieve の実装は経験がない。この実装は重要。
遠隔サーバマシンへのデータの転送、ふるい範囲の割り当てをするネットワークプログラム { 普通のTCP/IP プログラムであり、エラー処理等を付け加えるだけではあるが、使い勝手の良いものを作るのはそれなりに手間がかかる。
"åltering"
まだ本質がつかめていない。実装もまだ。
線形代数
block Lanczos 法の実装{一応できてはいる。
マルチ CPU でのマルチ・スレッドのプログラム{ 一応できてはいる。
ネットワーク接続 PC での分散処理{ MPI などの分散処理支援ソフトの導入
平方根Montgomery の方法の実装{まだ。

1.10.3理論

1024bits RSA 暗号の実行時間の評価という点では「多項式探索」と「ふるい」が重要である。
多項式探索理論よりも高速な実装が重要である。
“ふるい”を高速化するために多項式に課す条件は現在のものがすべてかは検討の余地がある。
ふるい
lattice sieve, line sieve のふるいの範囲の最適化。両者の使い分け。

CHAPTER 1. 素因数分解実験プロジェクト

12"åltering"

線形代数
block Lanczos 法の収束を速くする方法はないか。今はほとんど全空間を埋め尽くすまで収束しないがある部分空間内に閉じこめて収束させる方法はないか。
大規模行列処理の一般論としても有用な並列分散処理法の開発。
平方根
高速化

1.11

このプロジェクトの予定

1.11.1

第 1 期 2002 年 3 月まで

基礎理論の確認のために今回も含め 4 回のセミナーを開催する。
è 第1 回

2002/1/19

数体ふるい法概論

è 第2 回

2002/2/23

代数的整数論入門

è 第3 回

2002/3/9

ふるい、行列処理

è 第4 回

2002/3/30

代数的数の平方根

1.11.2

第 2 期 2002 年 4 月から 2003 年 3 月まで

第 1 期では全体をざっと眺めただけで特に高速化を意図してはいなかったが第 2 期では各論毎に分担者を決めて世界最高速のプログラム作成を目指す。

1.11.3

第 3 期 2003 年 4 月から 2004 年 3 月まで

第 3 期6 ではすべてのプログラムをつないで全体としてのチューニングを行い 320bits から 560bits くらいまでの合成数について実際の実行時間を計測し 1024bits の実行時間を推測する。

6 第 3 期については 2003 年 3 月 31 日現在では、実行されるかどうか未定である。

Chapter 2

数体ふるい法（その１）代数的整数論入門
2002/2/23

CRYPTREC 研究会 at 立教大学 S302 教室
2003/3/31 改訂
木田 祐司

この小論では代数的整数論の中から数体ふるい法の理解に必要と思われることを簡単に解説する。しかし、実際にプログラムを作る場面では代数的整数論の理論的な面に正面からぶつかると歯が立たないことが多い。あるいは細部を完全に解明することは莫大なコストをかけることになりもする。できるだけ困難を避けて通ったり、細部が詰めきれないままでも計算を行い結果オーライと割り切ることも必要である。

2.1

代数的整数

数体ふるい法では
íを整数係数多項式 f (x) の一つの根とするとき、小さな整数 a; b に対して
a + bí
を“素因数分解”する必要がある。
この方法を述べることがこのテキストの主要な内容である。
例として次の３つを考える。
1. fa (x) = x2 Ä 2
2. fb (x) = x3 + 2
M = 243 ;N = fb (M ) = C39 = 680564733841876926926749214863536422914

3. fc (x) = 99535x5 + 219113x4 + 1139835x3 Ä 1304055x2 + 38350500x + 65696851
M = 905015890; N = fc (M ) = C50 = 60430591373189847889033809879449779100427831121351
参考書：
石田信「代数的整数論、数学全書５」森北出版、1974 年
藤崎源二郎「代数的整数論入門（上）」裳華房、1975,2001 年
13CHAPTER 2. 数体ふるい法（その１）14最小多項式と判別式

2.1.1

定義 2.1. 1 íを根とする有理数係数多項式で次数が最小のものを íの 最小多項式 あるいは 定義
多項式 という。モニック（＝最高次係数が 1）のものとして一つに決めるのが普通だがここではモニックを仮定しない。
最小多項式の次数をその数の次数 という。
最小多項式が同一な数は互いに 共役 であるという。ある数と共役な元をその数の共役元という。
pppp2 の最小多項式は x2 Ä 2、 2 の次数は 2 で、共役元は 2 自身と Ä 2 の 2 つ。
p
p
p
p
p
p
2 + 3 の最小多項式は x4 Ä 10x2 + 1、 2 + 3 の次数は 4 で、共役元は Ü 2 Ü 3 の 4
例 2.1. 3
つである。
例 2.1. 2

例 2.1. 4 íの最小多項式が f (x) = cd xd + cdÄ 1 xdÄ 1 + ÅÅÅ+ c1 x + c0 ならば a + bí(a; b 2 Q; b 6= 0) の最小多項式はg(x) = f (

xÄa
)
b

である。

定義 2.1. 5 í の共役元を í1 ; í2 ; . . . ; íd とするとき a + bí(a; b 2 Q; b 6= 0) のトレース（共役和）とノルム（共役積）を次のように定義する。
T (a + bí)
N (a + bí)= (a + bí1 ) + (a + bí2 ) + ÅÅÅ+ (a + bíd )= (a + bí1 )(a + bí2 ) ÅÅÅ(a + bíd )例 2.1. 6 íの最小多項式を f (x) = cd xd + cdÄ 1 xdÄ 1 + ÅÅÅ+ c1 x + c0 とすると
c0
cdÄ 1
T (í) = Ä;N (í) = (Ä1)dcdcdである。さらに a + bí(a; b 2 Q; b 6= 0) ならばT (a + bí) = da Ä b
N (a + bí) = (Ä1)d

cdÄ 1
cd

f (Äa=b)f (Äa=b)= (Äb)d
cd =bdcd

よって
cd N (a + bí) = cd ad + cdÄ 1 adÄ 1 (Äb) + ÅÅÅ+ cr ar (Äb)dÄ r + ÅÅÅ+ c1 a(Äb)dÄ1 + c0 (Äb)d
ノルムは a + bíの“素因数分解”の様子を Z の数で教えてくれる。
例 2.1. 7

p
N (1 + 3 Ä1) = 12 + 32 = 10 = 2 Å5pなので 1 + 3 Ä1 の“素因数分解”は 2 と 5 に関係していることがわかる。実際pp
2 = N (1 + Ä1); 5 = N (1 + 2 Ä1)でppp
1 + 3 Ä1 = Ä(1 Ä Ä1)(1 Ä 2 Ä1)

2.1. 代数的整数15

定義 2.1. 8 多項式 f (x) の 判別式 D(f ) を根の差積の 2 乗で定義する。つまり根を í1 ; í2 ; . . . ; íd
0

とするとき

D(f ) = @Y12(íi Ä íj )A1î i<jî d多項式でなく íi について定まるものと考えても良い。このときは D(íi ) と記す。
判別式は直接的には多項式が重根を持つかどうかを判別するものであるが、数論的には主にイデアルが“分岐”するかどうかを判定する。我々は整数環との違いを知るために用いる。
例 2.1. 9 f (x) = ax2 + bx + c の場合。
D(f )= (í1 Ä í2 )2= (í1 + í2 )2 Ä 4í1 í2= (Äb=a)2 Ä 4c=ab2 Ä 4ac=a2である。これはおなじみの二次方程式の判別式（の 1=a2 倍）である。
高次の多項式の場合は次の関係式を用いる。積の微分の公式によると
f 0 (x)=cd =dXY

j=1 1î iîd; i6=jであるから
f 0 (íj )=cd =Y

1î iî d; i6=jとなるので

命題 2.1. 10(x Ä íi )(íj Ä íi )1 Y 0
f (íi )
cdd i=1
d

D(f ) = (Ä1)d(dÄ 1)=2

例 2.1. 11 f (x) = xd + ax + b の場合。
Qd0
i=1 f (íi )

=
=
=
=
=

Qd
(díidÄ1 + a)Qi=1d(díid + aíi )=íiQi=1d(d(Äaíi Ä b) + aíi )=íi
Qi=1
Qd
d
i=1 ((1 Ä d)aíi Ä db)=i=1 íiN ((1 Ä d)aíi Ä db)=N íi(i は何でも同じ)である。これより
D(f ) = (Ä1)d(dÄ 1)=2 f(1 Ä d)dÄ 1 ad + dd bdÄ 1 gとなる。

CHAPTER 2. 数体ふるい法（その１）16

例 2.1. 12 f (x) = x5 + 2x4 + 3x3 + 4x2 + 5x + 6 の判別式を求める。厳密な計算よりも近似計算で逃げるのが簡明。Newton 法などで根の近似値を求めると
Ä1:49179798814

p
0:55168546346 Ü 1:25334886028 Ä1pÄ0:80578646939 Ü 1:22290471337 Ä1となる。これらを f 0 (x) に代入して積を作れば、その値はp1037231:999994567 Ä 6:32383 Å10Ä 13 Ä1である。一般に判別式は有理数であるから。この値に一番近い有理数ということでD(f ) = 1037232 = 24 33 74を得る1 。実数部が整数に近くなかったり、虚数部が 0 にあまり近くない場合は近似の精度を上げねばならない。根が代数的整数でない場合は判別式が有理整数とは限らないので分母を消す操作が必要になる。
例 2.1. 13
f (x) = 99535x5 + 219113x4 + 1139835x3 Ä 1304055x2 + 38350500x + 65696851の場合は多倍長の近似計算により995358 D(f )= 46832148147468851358232189290906934477584939381340895833= 13 É13 É17 É3797 É10779623 É398257793658417325437983476966922302931291を得る。
また van der Monde の行列式を思い出すと

命題 2.1. 14

2.1.2

å2
å
å 1
1 ÅÅÅ 1 åååååå í1 í2 ÅÅÅ íd å
å
å
2
2
2 å
D(f ) = åå í1 í2 ÅÅÅ íd åååå ÅÅÅ ÅÅÅ ÅÅÅ ÅÅÅåååå íd íd ÅÅÅ íd å
12d整数環と判別式

定義 2.1. 15 整数係数多項式の根を 代数的数 という。とくに最高次係数が 1 であるものの根を 代
数的整数 という。
1 厳密には可能性が高いとしか言えない。なお次の節の内容を先取りすれば、「f (x) の根は代数的整数であるから、それらの積和である判別式も代数的整数である。しかも判別式は有理数であるから、有理整数になる。」と言えるのでより確信は深まる。

2.1. 代数的整数

17

定義 2.1. 16 代数的数を有理数体に添加して得られる体を 代数体 という。ある代数体に含まれる
代数的整数の全体は環をなす。これをその代数体の 整数環 という。

定義 2.1. 17 代数体 K の有理数体 Q 上のベクトル空間としての次元を K の次数という。

定理 2.1. 18 代数体 K の次数 d が有限の場合、d 次の既約多項式 f (x) が存在してその一つの根íにより K = Q(í) と表される。逆に d 次の既約多項式の一つの根を添加した代数体の次数は d である。
有理数体 Q に、既約多項式 f (x) = cd xd + cdÄ 1 xdÄ 1 + ÅÅÅ+ c1 x + c0 の根 íを添加した体 Q(í) とは
Q の元と íのべき乗が作る有理式の全体のことである。これに1. 分母の有理化1dÄ 1
2. íd = ÄcÄ+ ÅÅÅ+ c1 í+ c0 ) による次数の還元
d (cdÄ 1 íを行えば
Q(í) = fa0 + a1 í+ a2 í2 + ÅÅÅ+ adÄ1 ídÄ1 j ai 2 Qgとなる。

定義 2.1. 19 K = Q(í) を d 次の代数体とするとき、その元 ã = a0 + a1 í+ a2 í2 + ÅÅÅ+ adÄ 1 ídÄ 1の K における共役元とは
a0 + a1 íi + a2 íi2 + ÅÅÅ+ adÄ 1 íidÄ 1 ;i = 1; 2; . . . ; dのこととする。ただし íi は íの共役元である。
さらに K におけるノルムをNK ã =dYÄÅ
a0 + a1 íi + a2 íi2 + ÅÅÅ+ adÄ 1 íidÄ 1i=1で定義する。
ここで ã の次数を d(ã) とすればNK ã = (N ã)d=d(ã)
である。
pp
例 2.1. 20 K = Q( 2 + 3) は 4 次の代数体であってpp
NK ( 2 + 3) =
p
NK 2
=
NK 2
=

p
p p
p
p
p
p
p
( 2 + 3)( 2 Ä 3)(Ä 2 + 3)(Ä 2 Ä 3) = 1ppp(N 2)2 = (( 2)(Ä 2))2 = 4
24 = 16

CHAPTER 2. 数体ふるい法（その１）18

定理 2.1. 21 整数環は Z 上の基底を持つ。詳しくは次の通り。
代数体 K の次数を d とすると K の d 個の代数的整数 í1 ; í2 ; . . . ; íd が存在して K の任意の代数
的整数 ã は
ã = c1 í1 + c2 í2 + ÅÅÅ+ cd íd ;ci 2 Zと表される。しかもこの表し方は一意である。
注意：íi はここでは共役元の意味ではない。
ppp
2 は 2 次の代数的数であり、Q( 2) は Q 上 2 次の代数体である。Q( 2) の整数環の基底
例 2.1. 22p
は f1; 2g である。

pp
例 2.1. 23 m が平方数でなければ m は 2 次の代数的数であり、Q( m) は Q 上 2 次の代数体である。
p
Q( m) の整数環の基底は m = k2 m0 ; (m0 は平方因子を持たない) と分けるとき m0 ë 2; 3 mod 4 ならばpp
f1; m0 g であり、m0 ë 1 mod 4 ならば f1; (1 + m0 )=2g である。

pp
例 2.1. 24 m が立方数でなければ 3 m は 3 次の代数的数であり、Q( 3 m) は Q 上 3 次の代数体である。
m = ab2 (a は平方因子を持たない) とすると整数環の基底は
a2 6ë b2 mod 32 ならばであり、
a2 ë b2 mod 32 ならば

1;

p
3

ab2 ;

p
3
a2 b

p
p
p
p
1
3
3
3
3
(1 + a ab2 + b a2 b); ab2 ; a2 b3である。
注意：上記のように整数基底が理論的に綺麗に求まることは非常に稀である。普通は計算機プログラム
によって数値計算で求めることになる。

定義 2.1. 25 f (x) を d 次既約多項式でその根 í を添加した代数体 K = Q(í) の整数基底をí1 ; í2 ; . . . ; íd とするとき体 K の 判別式 D(K) をで定義する。これは有理整数である。

ê
ê
ëë 2
(j)
D(K) = det íipp
例 2.1. 26 K = Q( 2) の整数基底は 1; 2 であるから
å2
å
å 1
p
1 å
å
å
p å = (Ä2 2)2 = 8
D(K) = å p
å 2 Ä 2 åp
p p
例 2.1. 27 K = Q( 3 2) の整数基底は 1; 3 2; 3 4 であるから
å
å 1
åp
å
D(K) = å 3 2
åp
å 34

1
p
3
2!
p
3
2! 2

å2
å
1
å
p
å
3
2! 2 å = (6!(! Ä 1))2 = Ä22 Å33
å
p
3
4! å

2.2. イデアル論の基本定理

19

定理 2.1. 28 í2 OK に対してD(í)=D(K) = (OK : Z[í])2
例 2.1. 29
f (x) = 99535x5 + 219113x4 + 1139835x3 Ä 1304055x2 + 38350500x + 65696851の場合は995358 D(f )= 46832148147468851358232189290906934477584939381340895833= 13 É13 É17 É3797 É10779623 É398257793658417325437983476966922302931291
だったので、この一つの根 íによって K = Q(í) を作ると 99535íは代数的整数であって(OK : Z[99535í])2 = D(99535í)=D(K) = 9953520 D(í)=D(K)
ここで右辺の平方因子は 9953512 132 = (56 Å13 Å176 Å11716 )2 の約数であるから (OK : Z[99535í]) は
56 Å13 Å176 Å11716 の約数である。
次に、ë= 1=íとするともちろん生成する体は等しい
K = Q(í) = Q(ë)ëの最小多項式は f (x) と係数の並びが逆になる。
g(x) = 99535 + 219113x + 1139835x2 Ä 1304055x3 + 38350500x4 + 65696851x5
すると 65696851ëは代数的整数であって656968518 D(g) = 995358 D(f )なので(OK : Z[65696851ë])2 = D(65696851ë)=D(K) = 6569685120 D(ë)=D(K)
ここで右辺の平方因子は 6569685112 132 = (116 Å13 Å196 Å3143396 )2 の約数であるから (OK : Z[65696851ë])は 116 Å13 Å196 Å3143396 の約数である。
両方を合わせると 13 以外の素数についてはどちらかの指数がその素数の倍数にならない。

2.2

イデアル論の基本定理pppたとえば Z[ 2] においては 2 = ( 2)2 だから 2 は Z[ 2] ではもはや「素数」ではない。このように素数が代数体でどのように分解するかを調べることが代数的整数論の主要な目的の一つである。
pQ( Ä5) の整数環では「素元」分解が一意ではない2 。
pp
6 = 2 Å3 = (1 + Ä5)(1 Ä Ä5)ppであって、2; 3; 1 + Ä5; 1 Ä Ä5 はこれ以上分解できないので「素元」である。
「素元」分解ではこれで行き詰まる。そこで素イデアル分解にするとすべてがうまく行く。
2 正確な用語としては素元ではなく既約元という。素元は素イデアルを生成する元として定義される。ここではしかし既約元ではつまらないので「」付きで「素元」と記しておく。

CHAPTER 2. 数体ふるい法（その１）20

定義 2.2. 1 整数環 O のイデアル A とは
(1)
(2)

A は加法に関して O の部分群である。
c 2 O; a 2 A ならば ca 2 A である。

が満たされること。

定義 2.2. 2 整数環 O のイデアル A; B に対して
(1) A + B = fa + b j a 2 A; b 2 Bg
P(2) A ÅB = f ai bi j ai 2 A; bi 2 Bg

でイデアルの和と積を定義する。これらもまたイデアルになる。
pQ( Ä5) での 6 の分解に戻る。まずI = 2O;J = 3O;K = (1 +pÄ5)O;

L = (1 Ä

p

Ä5)O

とおいて
A = I + K;

B = I + L;

C = J + K;

D =J +Lとする。するとA ÅB = 2O;p
A ÅC = (1 + Ä5)O;となる。つまり前の二つの分解はまだ途中であってC ÅD =
B ÅD =

3Op(1 Ä Ä5)O

6O = A ÅB ÅC ÅD
が完全な分解であるということになる。ただし A; B は同じイデアルである。

定義 2.2. 3 整数環 OK のイデアル X のノルムを
NX = (OK : X)
で定義する。ただし ( : ) は群の指数である。
例 2.2. 4
N(2Z) = (Z : 2Z) = #(Z=2Z) = 2p
例 2.2. 5 上の Q( Ä5) では
NI
NJ
NK
NL
NA
NB
NC
ND

=
=
=
=
=
=
=
=

(O : 2O) = 4(O : 3O) = 9
p(O : (1 + Ä5)O) = 6
p(O : (1 + Ä5)O) = 6
p(O : 2O + (1 + Ä5)O) = 2
p(O : 2O + (1 Ä Ä5)O) = 2
p(O : 3O + (1 + Ä5)O) = 3
p(O : 3O + (1 Ä Ä5)O) = 3

2.3. 素数の素イデアル分解

21

定理 2.2. 6 ノルムは乗法的である。つまりイデアル X; Y に対してN(XY ) = NX ÅNY
K の数 ã に対してそれが生成する単項イデアルのノルムは数としてのノルムの絶対値に等しい。
N(ãOK ) = jNK ãj
一般に次の定理が成立する。

定理 2.2. 7 (イデアル論の基本定理) 整数環のイデアルは有限個の素イデアルの積に必ず分解され、しかもその分解の仕方は一通りである。
必要な例は次の小節で与える。
ここで定理は整数環に対するものであって部分環やもっと大きな環では乱れが出ることになる。
ppp
例 2.2. 8 Q( 5) の整数基底は 1; (1 + 5)=2 であるが 1; 5 を基底とする部分環 R では 2 の分解がう
まく行かない。2 が生成する R のイデアル 2R を考えると
1+p
5 62 2R

かつ (1 +

p5)2 = 2(3 +p5) 2 2Rなので 2R は R の素イデアルではない。もし R でイデアル論の基本定理が成り立つならば 2R は R 全体ではないイデアルの積になる。これは計算するとありえないことがわかる。
pp5=2 を基底とする環 R は ( 5=2)2 = 5=4 なので 1=4 を含み、整数環より真に大きい。このとき 2 は R の可逆元であるから 2 に関係する素イデアルは存在しない。
例 2.2. 9 1;2.3

素数の素イデアル分解

整数環 O は Z を含んでいる。詳しくはO\Q=Zである。また O のイデアルは Z のイデアルを含んでいる。とくに素イデアルは素数の倍数の全体を含んでいる。つまりP が O の素イデアルならば P \ Z = pZ となる素数 p が存在する。
逆に、素数 p を含む素イデアルはどのようなものだろうか。これは pO を含む素イデアルということだがイデアルが“含む”ということはイデアルとして“約数”になるということと同じであることが分かる
ので
pO = P1e1 P2e2 ÅÅÅPgeg
を素イデアル分解とすると、ここに出てくる P1 ; P2 ; . . . ; Pg が素数 p を含む素イデアルのすべてである。
実際の分解を計算するには次の定理を用いる。

CHAPTER 2. 数体ふるい法（その１）22定理 2.3. 1 既約多項式 f (x) の根 íにより K = Q(í) を作り、その整数環を OK とする。また pを素数で群指数 (O : Z[í]) を割らないものとする。f (x) の mod p での既約分解を
f (x) ë p1 (x)e1 p2 (x)e2 ÅÅÅpg (x)eg mod pとするとき Pi = (p; pi (í)) とすればこれは素イデアルであって
pOK = P1e1 P2e2 ÅÅÅPgeg
となる。
p
例 2.3. 2 f (x) = x2 Ä 2 ならば OK = Z[ 2] なのですべての素数について計算できる。
8
p
mod 2
) (2) = (2; 2)2
>
x2
>
>
>
>
既約
mod 3
>
>
>
>
>
mod 5
>
< 既約
p
p
f (x) ë(x + 3)(x Ä 3) mod 7) (3) = (7; 3 + 2)(7; 3 Ä 2)>>>
既約
mod 11>>>>> 既約
mod 13>>>pp:(x + 6)(x Ä 6) mod 17) (17) = (17; 6 + 2)(17; 6 Ä 2)

どのような規則になっているのだろうか。実は次のような法則がある。
体の判別式は 8 であり、これが分解を統制する。
(1)

p j 8（つまり p = 2）ならば素イデアルの 2 乗になる。

(2)

p ë 1; 7 mod 8 ならば異なる素イデアルの積。

(3)p ë 3; 5 mod 8 ならば素イデアルのまま。

ここで

p
p
(2; 2) = ( 2);(7; 3 Üp2) = (3 Üp

2);(17; 6 Üpp2) = (1 Ü 3 2)なのでイデアルを出さなくても数で十分ではある。
p
例 2.3. 3 f (x) = x2 + 5 ならば O = Z[ Ä5] なのですべての素数について計算できる。
8
p
mod 2
) (2) = (2; 1 + Ä5)2
(x + 1)2
>
>
>
p
p
>
>
(x + 1)(x Ä 1) mod 3) (3) = (3; 1 + Ä5)(3; 1 Ä Ä5)
>
>
>
p
>
2
>
mod 5
) (5) = (5; Ä5)2
>
< x
p
p
f (x) ë(x + 3)(x Ä 3) mod 7) (7) = (7; 3 + Ä5)(7; 3 Ä Ä5)
>
>
>
>
既約
mod 11>>>>>
既約
mod 13>>:
既約
mod 17
どのような規則になっているのだろうか。実は次のような法則がある。
体の判別式は 20 であり、これが分解を統制する。
(1)

p j 20（つまり p = 2; 5）ならば素イデアルの 2 乗になる。

2.3. 素数の素イデアル分解

23

(2)

p ë 1; 3; 7; 9 mod 20 ならば異なる素イデアルの積。

(3)

p ë 11; 13; 17; 19 mod 20 ならば素イデアルのまま。

pp
ここで (5; Ä5) = ( Ä5) であるが(2; 1 +pÄ5);

(3; 1 Üp
Ä5);

(7; 3 Üp
Ä5)は単項イデアルではないので数ではうまくいかない。イデアルが必須である。
pp
ついでに書くと (41) = (6+ Ä5)(6Ä Ä5) となって単項イデアルの積になる。この体では p ë 1 mod 20
ならば異なる単項な素イデアルの積になるのである。

p
例 2.3. 4 f (x) = x3 Ä 2 ならば O = Z[ 3 2] なのですべての素数について計算できる。
p
(x)3
mod 2
) (2) = (2; 3 2)3p(x + 1)3
mod 3) (3) = (3; 1 + 3 2)3pp
p 2(x + 2)(x2 Ä 2x Ä 1)
mod 5
) (5) = (5; 2 + 3 2)(5; Ä1 Ä 2 3 2 + 3 2 )
既約

mod 7

2

(x + 4)(x Ä 4x + 5)
既約ÅÅÅ
(x + 11)(x Ä 7)(x Ä 4)

mod 11
mod 13)pp
p 2(11) = (11; 4 + 3 2)(11; 5 Ä 4 3 2 + 3 2 )mod 31)ppp(31) = (31; 11 + 3 2)(31; 7 Ä 3 2)(31; 4 Ä 3 2)

この体の判別式は 4 Å27 = 108 であるが前の二つの例と違って mod 108 で分解が決まるわけではない。この違いは方程式のガロア群が可換群かそうでないかによる。前の二つは Z=2Z であるがこの場合は対称群
S3 であって非可換である。
これらのイデアルはすべて単項である。
p
p
p
p
p
p 2
(2; 3 2) = ( 3 2); (3; 1 + 3 2) = (1 + 3 2); (5; 2 + 3 2) = (1 + 3 2 );
p
p 2
p
p 2
p
p
p 2
(5; Ä1 Ä 2 3 2 + 3 2 ) = (Ä1 Ä 2 3 2 + 3 2 ); (11; 4 + 3 2) = (Ä1 + 3 2 + 3 2 );
p
p 2
p
p 2
p
p
p 2
(11; 5 Ä 4 3 2 + 3 2 ) = (1 Ä 3 3 2 Ä 2 3 2 ); (31; 11 + 3 2) = (1 Ä 3 3 2 + 3 2 );
p
p
p 2
p
p 2
(31; 7 Ä 3 2) = (1 Ä 2 3 2 Ä 3 2 ); (31; 4 Ä 3 2) = (1 Ä 2 3 2 )pp
例 2.3. 5 f (x) = x2 Ä 5 ならば O = Z[(1 + 5)=2] なので Z[ 5] は指数 2 の部分環である。よって 2についてはこの多項式では判定できない。実際、
f (x) ë (x + 1)2 mod 2
であるが 2 は O では素イデアルである。

2.3.1

多項式 mod p の一次因子を求める

Fp = Z=pZ 係数で多項式を因数分解する。ここで 512bits 程度の GNFS を考えると p は 24 ò 26 bits
以下である。また多項式は 6 次以下である。
この処理は最初に 1 度行うだけなので、改良に力を入れる必要はない。
次の公式が基本である。
px Äx =

pÄY1
s=0(x Ä s)in Fp [x]CHAPTER 2. 数体ふるい法（その１）

24
これにより

f1 (x) = GCD(f (x); xp Ä x)
は f (x) のすべての一次因子一個ずつの積になることがわかる。次に f1 (x) を分解する。
p が小さければ3 s = 0; 1; 2; . . . ; p Ä 1 と動かして f1 (s) ë 0 mod p となるものを探せば良い。
p が大きいときは、次の公式を用いる。
xp Ä x = (x + a)((x + a)(pÄ 1)=2 + 1)((x + a)(pÄ 1)=2 Ä 1)

for a = 0; 1; 2; . . . ; p Ä 1

これにより
f11 (x) = GCD(f1 (x); (x + a)(pÄ 1)=2 + 1);

f12 (x) = f1 (x)=f11 (x)とすれば
f1 (x) = f11 (x) Åf12 (x)と分解される。この分解されたそれぞれに次の a についての計算を行うことを繰り返して完全な分解を得る。一つの a で f1 (x) の一次因子は二つのグループに分かれるので最大 6 個の一次因子を分離するには平均 3 回の計算で済む。
一般に GCD(f (x); g(x)n ) の計算は次の 2 段階で行う。
1. g(x)n mod f (x) を繰り返し 2 乗法で計算する。
2. その結果と f (x) の GCD を計算する。
例 2.3. 6
f (x) = 99535x5 + 219113x4 + 1139835x3 Ä 1304055x2 + 38350500x + 65696851
を mod p = 104743 で因数分解する。まず
f1 (x) = GCD(f (x); xp Ä x) = x3 + 103518x2 + 7541x + 39422
であるので一次因子は 3 個ある。そして
f11 (x)f12 (x)= GCD(f1 (x); x(pÄ 1)=2 + 1)
= f1 (x)=f11 (x)= x2 + 19435x + 54722= 99535(x + 84083)

次に
f111 (x)f112 (x)= GCD(f11 (x); (x + 1)(pÄ1)=2 + 1) = x + 35005= f11 (x)=f111 (x)= x + 89173

したがって

=

99535x5 + 219113x4 + 1139835x3 Ä 1304055x2 + 38350500x + 65696851

99535(x + 35005)(x + 84083)(x + 89173)

mod 104743

である。素イデアルとしては(104743; íÄ 15570); (104743; íÄ 20660); (104743; íÄ 69738)となる。104743 は前に求めた (OK : Z[99535í]) を割らないのでこれが OK における 104743 の正しい一次因子である。

3 実装によるが 100 とか 200 といった程度。

2.3. 素数の素イデアル分解

25

素イデアル分解の例

2.3.2
例 2.3. 7

f (x) = 99535x5 + 219113x4 + 1139835x3 Ä 1304055x2 + 38350500x + 65696851
において p が 99535 の約数でも 13 でもなければ f (x) mod p の因数分解から p の素イデアル分解が得られる。
o が 99535 の約数の場合は f (x) の根 íから ë= 1=íを作るとそれはg(x) = 99535 + 219113x + 1139835x2 Ä 1304055x3 + 38350500x4 + 65696851x5の根であって、g(x) mod p の一次因子を x Ä t とすれば (p; ëÄ t) が 1 次の素イデアルになる。

ここで t 6ë 0 mod p ならば (p; ëÄ t) = (p; íÄ tÄ1 ) なので、f (x) mod p の一次因子として求めることができるものである。
t ë 0 mod p ならば (p; ë) は íの式に変形できない。このとき a + bíを (p; ë) が割るのは a + bí=í(aë+ b) なので b ë 0 mod p となる。このような素イデアルはまったく別扱いしなければいけない。また p が f (x) の最高次係数も定数項も割る場合は非常に複雑になる。

2.3.3

変形ノルム

ここまで素イデアル分解の複雑な状況を説明してきたが、実は数体ふるい法のふるいの段階では a + bíの素イデアル分解を避けて通ることができる。それはふるいの段階では a + bíが factor base の素イデア
ルで完全に分解するかどうかが分かれば十分だからである。
そのために次の値を考える。ノルムに最高次係数を掛けたものである。これを 変形ノルム と呼ぶことにする4 。
cd N (a + bí) = cd ad + cdÄ 1 adÄ 1 (Äb) + ÅÅÅ+ cr ar (Äb)dÄ r + ÅÅÅ+ c1 a(Äb)dÄ1 + c0 (Äb)d
変形ノルムが素数 p で割れたとしよう。つまり、
cd ad + cdÄ 1 adÄ1 (Äb) + ÅÅÅ+ cr ar (Äb)dÄ r + ÅÅÅ+ c1 a(Äb)dÄ 1 + c0 (Äb)d ë 0 mod p
であるとする。
p 6 jb ならば mod p での b の逆数を b0 として (Äb0 )d を両辺に掛けるとcd (Äab0 )d + cdÄ 1 (Äab0 )dÄ 1 + ÅÅÅ+ cr (Äab0 )r + ÅÅÅ+ c1 (Äab0 ) + c0 ë 0 mod pとなる。これは Äab0 が f (x) ë 0 mod p の解であることを示している。つまり x + ab0 が f (x) mod p の一次因子であることを示している。したがって p の素イデアル分解を意識しないで単純に多項式の mod p
での因数分解を考えれば良い。
pjb ならば cd ad ë 0 mod p となるが a と b は互いに素であるから a は p で割れず、したがって cd がp の倍数にならねばならない。逆に言うと cd の約数となる素数 p については pjb ならば cd N (a + bí) は
必ず p で割り切れる。この p の状況を (p; 1) と表し、射影的な素イデアル あるいは 射影的な因子 と呼ぶことにする。

変形ノルムに注目するとイデアル論を用いなくても良いので簡明であるが、数体ふるい法の最後の段階
までイデアル論を避けることは今のところできない。
4 一般に N (a + bí) は整数とは限らないが c N (a + bí) は整数となる。しかしこれが何かのノルムになっているわけではない。
d1
なんとも不思議なものである。理論的には代数的整数である cd (a + bí) のノルムを扱うべきであるが変形ノルムの cdÄ倍になるdので計算的に不利である。

Chapter 3

数体ふるい法（その２）
ふるい(sieve)
2002/3/9

CRYPTREC 研究会 at 立教大学 S302 教室
2003/3/31 改訂
木田 祐司

3.1

ここでいう sieve とは

ここでの目的は1
ある範囲の整数の組 (a; b); ÄHa î a < Ha ; 0 < b î Hb ; GCD(a; b) = 1 の中からその素因数（素イデアル）分解Y
pei i
a + bM =iY(a + bí) =Pifii

があらかじめ定めた素数の集合 F と素イデアルの集合 G の元だけで行われるようなものを探し出すこと。ここで < > は単項イデアルを表す。

である。F を有理的な factor base、G を代数的な factor base という。すでに見たように G は 1 次の素イデアルのみからなる。
そのために、一定の範囲の素数を見つけ出す方法である“エラトステネスのふるい”をまねるのである。
たとえば a + bM が p の倍数ならば (a + ip) + (b + jp)M もまた p の倍数であるから、割り算を行わず
単に step p で移動することにより p の倍数を次々に見つけることができる。これは a + bíについても同様である。
1 から 100 までで 2; 3; 5 で完全に分解されるものを探すには次のようにする。
è 100 個の場所 w1 ò w100 を準備して最初は全部 1 にする。

è 2 から始めて step 2 で 2 を掛ける。
è 2 のべきについても同様にする。
è 3; 5 についても同様にする。

以上を行った後、wi = i となっていれば i は 2; 3; 5 で完全に分解されることになる。
1 前章最後の節で実際の計算では変形ノルムを扱うと書いたが、この章では理論的に簡明にするために通常のノルムで記述する。
従って一般には正確な記述ではないことに注意されたい。

27

CHAPTER 3. 数体ふるい法（その２）28

例 3.1. 1 10001 から 10100 の中で 2; 3; 5; 7; 11; 13; 17 で完全に素因数分解できるものを探す。log をとって足し算で行う。
#include <stdio.h>#include <math.h>#define Start 10001#define Ns 100#define Ps 7
#define Scale 20.0
int prime[Ps] = {2,3,5,7,11,13,17};
unsigned char work[Ns];main(){
int i, ip, p, pp;
unsigned char logp, logn;
ワークエリアを 0 でクリア

for(i=0; i<Ns; i++) work[i] = 0;
for(ip=0; ip<Ps; ip++){pp = p = prime[ip];logp = (int)(log(p) * Scale + 0.5);
while(pp < Start+Ns){
i = Start % pp; if (i != 0) i = pp - i;for(i=i; i<Ns; i+=pp) work[i] += logp;
pp *= p;}}

最初の index を計算。
step p で log を加える。
次のべき乗へ。

for(i=0; i<Ns; i++){printf("%4d", work[i]);}printf("\n");logn = (int)(log(Start) * Scale * 0.95);
0.95 は誤差の考慮。
printf("log >= %4d\n", logn);
for(i=0; i<Ns; i++){if (work[i] >= logn) printf("%5d\n", Start+i); 値が十分大きいところが解。
}}----- result ----0 36
48 14
22 14
0 109
57 14
log >=
10010
10080
10098

39 28 54
73 81 64
96 116 110
0 113 102
22 28 32

174

14
58
14
53
36

0
0
79
0
87

86
28
84
50
93

0 184
22 10351 100
0 46
44 46

22 28
39 126
0 67
66 42
0 50

57
0
44
39
0

36 32
14 76
62 32
36 11592 54

70 105 14
79
0 75
64
0 14
76 22 14
56
0 185

0 82
0 74
61 60
0 185
0 92

3.2. LINE SIEVE

3.2

29

line sieve

単純に b を 固定して a を動かす方法を line-by-line sieve あるいは単に line sieve という。
(1) sieve のワークエリアを 2Ha bytes 確保し、0 クリアする。
(2) 各 p 2 F について p の倍数に対応するところに log p を加えていく。

これは最初の位置さえ計算すれば次の番地は p を加えるだけで済む。ワークエリアの先頭は ÄHa +bMに対応するので最初に p の倍数になる番地 r はr ë Ha Ä bM mod p;0îr<pで計算できる。次の b でのスタートは ÄM mod p だけずれることに注意。
(3) すべての p 2 F について (3) を行なったのち log bM に近い値はそのままにするが、そうでない（＝
かなり小さい）値はこのテストを通らなかったので 0 クリアする。

イデアル (a + bí) の分解は次の原理によって有理整数の分解に帰着させる。
a + bíë 0 mod (p; íÄ s) () a + bs ë 0 mod p(4) 新たなワークエリアを 2Ha bytes 確保し、0 クリアする。
(5) 各 (p; íÄ s) 2 G についてその倍数に対応するところに log p を加えていく。これは最初の位置さえ計算すれば次の番地は p を加えるだけで良い。ワークエリアの先頭は a = ÄHa に対応するので最初に (p; íÄ s) の倍数となる番地 r はr ë Ha Ä bs mod p;0îr<pで計算できる。次の b でのスタートは Äs mod p だけずれることに注意。
(6) すべての (p; íÄ s) 2 G について (5) を行なったのち log jN (a + bí)j に近いものを残し、それ以外
は 0 クリアする。
(7) 両方の sieve を通ったものを実際に割り算をして確認する。イデアルの割り算の方は次の原理によりノルムの割り算で済ませる。
(p; íÄ s)e jj(a + bí) () pe jjN (a + bí)
注意 a + bí; GCD(a; b) = 1 は同一の素数 p を含む異なる素イデアル (p; íÄ s); (p; íÄ t) で同時に割れることはない。
注意

メモリは次のように使われる。

[TABLE ] 素数、素イデアルのテーブル:16 bytes 程度を最大 500 万セット
[WORK ] sieve されるエリア:数 10 メガ bytes(分割可)[TABLE] から素数や位置情報を取り出しながら [WORK] を sieve する。[WORK] が頻繁にアクセスされるのでキャッシュメモリがここに効いてほしい。
例 3.2. 1 GNFS158 での sieve 領域は Ä5 Å108 î a < 5 Å108 ;0 < b < 2 Å104 であった。

CHAPTER 3. 数体ふるい法（その２）

30

3.2.1

(1 + 1) large primes

a; b を sieve を通ったペアとする。
(8) a + bM を F の素数で素因数分解する。分解しきれない部分を R とする。
高速化の手法がいろいろ考えられている。簡単なものでは割り切れるかどうかの判定を多倍長数である a + bM 自身でなく work area 中の oãset で判定する
割り切れたときは work area の値を sieve のときとは逆に log p だけ減らすことにより試し割り算の終了を判定する、などである。
(9) N (a + bí) を G の素イデアルに含まれる素数で素因数分解する。分解しきれない部分を A とする。
上と同じような高速化が可能である。

ただし、R; A が factor base の最大の素数の 2 乗より大きいものは捨てる。そうすることにより、以下では R; A は素数として良い。
これで次のような分解が得られた。
8>< a + bMQ=>
: N (a + bí) =Q

pe(p) Rp2F

q e(q) A

q2N G(FF 型) R = 1; A = 1 の場合。
本来はこれのみを求めていた。target が大きくなるとこれだけでは十分な個数が集まらないので以下のような data も利用しなければならなくなる。
(PF 型) R > 1; A = 1 の場合。
このようなもので R が一致するものを見つけて積を作れば分解されない部分は平方数になる。平方数はこの先の処理で無視しても良いものなので、この積は (FF 型) と同様に扱うことができる。
(
Q e(p)1
a1 + b1 M=pR
Q e(q)1
N (a1 + b1 í) =
q

から

(

(

=
a2 + b2 M
N (a2 + b2 í) =(a1 + b1 M )(a2 + b2 M )N (a1 + b1 í)(a2 + b2 í)である。

Q e(p)2p
R
Q e(q)2q

Q e(p)1 +e(p)2 2pRQ e(q)1 +e(q)2=q=

R が一致するものは R について並べ替えをして見つける。
(FP 型) R = 1; A > 1 の場合。
A が一致してもノルムをとる前のイデアルが一致するとは限らない。今、a + bíは A を含むある素イデアル (A; íÄ s) で割れるが s は s = abÄ 1 mod A で決定される。これにより 2 つの a + bíが同じ素イデアルで割れるかどうかが判定できる。
(=
a1 + b1 M
N (a1 + b1 í) =Q e(p)1p
Q e(q)1q
A

3.2. LINE SIEVE(

a2 + b2 M=
N (a2 + b2 í) =1
Ä1において a1 bÄ
1 ë a2 b2 mod A ならば

Q e(p)2p
Q e(q)2
q
A

31

1 2
(a1 + b1 í)(a2 + b2 í) = factor base の素イデアルの積 Ç (A; íÄ a1 bÄ
1 )この場合は A と abÄ 1 mod A という二つをキーにして並べ替えを行うという面倒がある。
(PP 型) R > 1; A > 1 の場合。
ほとんどないが R; A; abÄ 1 mod A が一致すれば (FF 型) ができる。(PF 型) を使って R を消去す
れば (FP 型) ができる。(FP 型) を使って A を消去すれば (PF 型) ができる。これらを含めて (FP型),(PF 型) の処理を再度行えば新たな (FF 型) を作ることができる。

3.2.2(2 + 2) large primes"(1 + 1) large primes" では sieve を通ったものを素因数分解あるいは素イデアル分解して分解し切れな
かった部分をまた利用した。このとき残りは一つの素数あるいは素イデアルであった。これを 2 個ずつにするのが "(2 + 2) large primes" である。つまり
8
Q e(p)>p
R1 R2=< a + bM
p2F
Q e(q)>q
A1 A2: N (a + bí) =q2N Gという分解も利用するのである。
このときは sieve に合格する基準をずっと下げることになる。すると sieve において
è 素数べきの扱いを省略しても良い。
è 小さな素数は省略しても良い。
などの利点がある。反面
è 試し割り算をする候補が大幅に増える。

è 試し割り算の後で残った部分を二つに素因数分解しなければいけない。
という欠点もある。それぞれを軽減する必要がある。
一つ目は "(1 + 1) large primes" のときとは違って巨大で不必要な素数が大量に混じることである。有理数側でいえば F の最大素数を pmax とすると pmax < R1 î R2 < p2max であるから
p2max < R1 R2 < p4maxとなる。もちろん R1 のみのものも扱うから sieve での許容範囲は p4max 以下のすべてとなる。これは過大なので範囲を制限することが考えられる。たとえばpmax < R1 î R2 î 50pmaxとすれば、この範囲とp2max < R1 R2 î 502 p2maxの範囲を許容することになる。
二つ目は R1 ; R2 の積を R1 ; R2 に分解するという“ミニ素因数分解”を高速に実行することである。これは Rho 法 や ECM あるいはマイナーなところであるが Shanks の SQUFOF 法が有効である。

CHAPTER 3. 数体ふるい法（その２）

32

3.2.3

Free Relations

a + bíの中でとくに b = 0 の数、つまり有理整数は扱っていなかった。これは別に扱うのが適当である。
有理素数で K で一次の素イデアルの積に完全分解するものはそのまま smooth data として扱える。
pOK = (p; íÄ s1 )(p; íÄ s2 ) ÅÅÅ(p; íÄ sd )このとき両辺の素数、素イデアルが共に factor base に入っていれば a = p; b = 0 は (FF 型) のペアとなる。このような関係式（あるいはそのペア）を free relation と言う。こういう素数 p がどのくらいあるかは密度定理で調べることができる。
pf (x) = x3 + 2 つまり K = Q(Ä 3 2) の場合は #F=6 個あるので、かなりの助けになる。この場合の最小の p は 31 で、次のように分解される。
31OK = (íÄ 11)(íÄ 24)(íÄ 27)
一般には f (x) のすべての根を添加した体、最小分解体という、の次数で決まる。
定理 3.2. 2 (密度定理（の特殊な場合）)
lim

x!1

free relation を与える素数で x 以下のものの個数
1=x 以下の素数の個数
最小分解体の次数

しかし、d 次既約多項式をランダムにとるとほとんどの場合、最小分解体の次数は d! である2 。他の効率を悪くせずにこの次数を減らすことはかなり難しいと思われる。

3.3

lattice sieve

代数的な factor base に含まれない一次の素イデアル Q = (q; íÄ t) を固定して
W = f(a; b) j Ä Ha î a î Ha ; 0 < b < Hb gの中でWq = f(a; b) 2 W j a + bíë 0 mod Qg
はどのような集合となっているかを調べる。
a + bt ë 0 mod qであるから(q; 0); (Ät; 1)で生成される Z 上の rank 2 の自由加群である。
2 次元なので通常のユークリッド除算（ガウス法）で最小ベクトルを求めることができる。

定義 3.3. 1 2 次元ベクトル a = (x1 ; y1 ) の b = (x2 ; y2 ) による整数商 r(a; b) を次のように定義
する。
ì
í
ì
í
x1 x2 + y1 y2
a Åb
=
round
r(a; b) = roundjbj2
x22 + y22
2 ガロア群が Sd であるということと同じ。

3.3. LATTICE SIEVE

33

定理 3.3. 2 lattice L の基底 a; b; jaj ï jbj について
c = a Ä r(a; b)b
が jcj ï jbj となるならば b は L の最小ベクトルである。
例 3.3. 3 q = 3; t = 1 ならば基底として (3; 0); (Ä1; 1) をとれば(3; 0) = Ä2(Ä1:1) + (1; 2)となり、これ以上短くできないので終了である。
(Ä1; 1); (1; 2)が最小基底である。
例 3.3. 4 q = 104729; t = 34567 ならば次のように計算される。
(104729, 0) = (-3)(-34567,1) + (1028,3)(-34567, 1) = (-34)(1028, 3) + (385, 103)
(1028, 3) = 2(385, 103) + (258,-203)(385, 103) = 1(258, -203) + (127,306)(258, -203) は (127, 306) では短縮できない。
(258; Ä203); (127; 306)が最小基底である。
最小基底を v1 = (x1 ; y1 ); v2 = (x2 ; y2 ) とする。v1 の方が絶対値が小さいものとする。また必要ならば符号を変えることによって x1 > 0 とする。lattice L をこの基底で表す。
a + bí= cv1 + dv2
(

とすると

である。
注意

det

†

x1
x2

y1
y2

!

a

= cx1 + dx2b= cy1 + dy2= Üq であるので GCD(c; d) = 1 であっても GCD(a; b) = q となりうる。

line sieve では a; b を動かして sieve したが lattice sieve では各 Q = (q; íÄ t) について c; d を動かして sieve する。これも "(2 + 2) large primes" で行う。
ひとつの Q については多くの点の sieve を行わず、Q 自身をたくさん動かすことにする。
lattice sieve の利点は代数的数の方は必ず Q で割れるのであり、割った商はランダムであると考えられるから sieve の対象の大きさが 1=q になった効果があることである。

CHAPTER 3. 数体ふるい法（その２）34
例 3.3. 5 RSA155 では
16 Å106 < q < 308 Å106としている。素イデアル Q の個数は 15:7 Å106 である。8 Å103 Ç 5 Å103 個を sieve している。最小ベクトpルの成分を q ò 13 Å103 程度とすれば領域としては Ü52 Å106 Ç 65 Å106 程度ということになる。

a = b = 1 Å106 における代数側の sieve 対象の大きさは 2206 程度である。有理数側は 2115 程度とずっと小さい。代数側が 1=q になることによりバランスが良くなる。
GNFS158 では
24 Å106 < q < 118 Å106とし 16 Å103 Ç 8 Å103 個を sieve している。最小ベクトルの成分をは Ü64 Å106 Ç 64 Å106 程度ということになる。

pq ò 8 Å103 程度とすれば領域として

Chapter 4

Lanczos 法
4.1

Lanczos 法（標数 0 の場合）

4.1.1

記号

è(v; w) = v T w は通常の内積

è(v; w)A = v T Aw は対称行列 A による内積èL(v1 ; v2 ; . . .) は v1 ; v2 ; . . . で張られる部分空間

4.1.2

Lanczos 法の考え方（１）

我々の目的は与えられた行列 A およびベクトル c に対して
Ax = cとなる x を求めることである。
簡単のため A は正則行列であり、したがって任意の c に対して上の方程式は解を持つとする。
v1 ; v2 ; . . . ; vd
を全体空間 V = Rd の基底とする。x を求めるとはx = x1 v1 + x2 v2 + ÅÅÅ+ xd vdとなる係数 xi を求めることである。x が与えられたときに xi を決定するのは基底が直交していれば両辺の vi との内積をとれば簡単である。
今は Ax = c からそれを行いたい。vi との内積をとってみよう。
(vi ; Ax) = (vi ; c)
右辺は計算できるのでこれを利用する。左辺は(vi ; Ax) = x1 (vi ; Av1 ) + x2 (vi ; Av2 ) + ÅÅÅ+ xd (vi ; Avd )となる。ここで、行列 A が正定値対称行列ならば (v; Aw) = v T Aw を A による v と w の内積と考えて通常の内積と同様に扱うことができる。以下この内積を A-内積と呼ぶことにし (v; w)A と記す。
35

CHAPTER 4. LANCZOS 法

36

v1 ; v2 ; . . . ; vd を A-内積に関する Gram-Schmidt の直交化法により A-直交化する。それもまた v1 ; . . . ; vd
で表すことにしよう。すると上の式では i 番目の項以外は消えてしまう。
(vi ; Ax) = (vi ; x)A = xi (vi ; vi )A
つまり、
xi = (vi ; x)A =(vi ; vi )A = (vi ; c)=(vi ; vi )Aであり、結局求める解は
x=
となる。

d
X
(vi ; c)vi
(vi ; vi )A
i=1

まとめると、行列 A が正定値対称行列ならば方程式 (1) は次の手順で解ける。
è Rd の基底から A-直交基底 fv1 ; v2 ; . . . ; vd g を作る。
èx =例 4.1. 1dX(vi ; c)vi を計算する。
(vi ; vi )A
i=1

0

3
B
A=@ 2
Ä1

2
2
0

とすると標準基底から A-直交基底を作ると
v1 = (1; 0; 0)T ;

1
Ä1
C
0 A;
3

1
0
B C
c=@ 3 A4

v2 = (Ä2=3; 1; 0)T0v3 = (1; Ä1; 1)Tとなる。すると(v1 ; c)=(v1 ; v1 )A=(v2 ; c)=(v2 ; v2 )A= 3=(2=3)=
1=2(v3 ; c)=(v3 ; v3 )A

0=3

なので
x

= (9=2)v2 + (1=2)v3= (Ä5=2; 4; 1=2)Tが解である。

4.1.3

Lanczos 法の考え方（２）

前節の方法をよく調べてみると基底の A-直交化に時間がかかることがわかる。これは実質的に A の三角行列化と同等であって利点はない。
ただし、空間 W が次の条件を満たせば前節の議論をそのまま適用することができる。
(
c
2 W
これは

(

AW

= W

w1

=
c
= Awi

wi+1

で W = L(w1 ; w2 ; . . .) を作って行けば最大 d 回で増加しなくなり目的を達する。
この基底から A-直交基底を作るのは次のように簡単である。この直交化の列の長さが 2 で済むことがポ
イントである。

4.1. LANCZOS 法（標数 0 の場合）

定理 4.1. 2

8
< w1
: wi

37

= c
= AwiÄ1 Ä(wiÄ 1 ; AwiÄ1 )A(wiÄ 2 ; AwiÄ 1 )AwiÄ 1 ÄwiÄ 2(wiÄ 1 ; wiÄ 1 )A(wiÄ 2 ; wiÄ 2 )Aとして作った w1 ; w2 ; . . . は A-直交する。
証明 命題“AwiÄ 1 は wiÄ 3 以下と直交している。
”ことを示せば良い。i についての帰納法による。i = 1; 2に対しては正しい。i Ä 2 まで正しかったとして i Ä 1 のときに証明する。j ï 3 に対してT
T(wiÄ j ; AwiÄ 1 )A = wiÄj AAwiÄ 1 = (AwiÄ j ) AwiÄ1 = (AwiÄ j ; wiÄ1 )A

であり wiÄ 1 は帰納法の仮定から wiÄ2 ; wiÄ3 ; . . . と A-直交している。AwiÄ j ö L(w1 ; w2 ; . . . ; wiÄ j+1 ) であり、j ï 3 であったから命題が示された（A が対称行列であることがポイント）。

4.1.4

例
v1 = c = (0; 3; 4)Tから始めると
v2 = (2; Ä26=11; 28=33)T ;v3 = (Ä6=25; Ä2=25; 2=25)T

である。

4.1.5

Lanczos 法の実際

前節までの考察を踏まえて Lanczos 法をきちんと記述する。
A は正定値対称行列とし、これにより定義される内積を考える。
ベクトル列c; Ac; A2 c; . . . ; Ar c; . . .
を考える1 。全体空間は有限次元だからこの列はどこかで一定の空間 Wm を生成するようになる。つまり
c; Ac; A2 c; . . . ; AmÄ 1 c
までは線形独立であり、これ以降はこれらの線形結合に書けるようになる。これから Gram-Schmidt の直交化法により A-直交基底を作る。
w1 ; w2 ; . . . ; wmとする。つまり

8
< w1
: wi

=

c

=

AwiÄ 1 Ä(wiÄ1 ; AwiÄ 1 )A(wiÄ 2 ; AwiÄ 1 )AwiÄ 1 ÄwiÄ2(wiÄ 1 ; wiÄ 1 )A(wiÄ2 ; wiÄ2 )A

1 これらで生成される部分空間を Krylov 空間という。

CHAPTER 4. LANCZOS 法

38

定理 4.1. 3x=
は Ax = c をみたす。
証明 8i についてmX
(wj ; c)wj
(wj ; wj )A
j=1(wi ; Ax) = (wi ; x)AmX(wj ; c)=(wi ; wj )A(wj ; wj )A
j=1(wi ; c)=(wi ; wi )A(wi ; wi )A= (wi ; c)したがって(wi ; Ax Ä c) = 08iである。ここで Wm の作り方から
AWm ö Wm
なので Ax Ä c は Wm の元である。そして fwi ; i = 1; . . . ; mg は Wm の基底であるからそのすべてと通常の内積で直交するベクトルは 0 ベクトルである。したがって Ax = c となる。

4.2

Lanczos 法（標数 p > 0 の場合）

4.2.1

Lanczos 法（標数 p > 0 の場合）の考え方（１）Lanczos 法を標数 p > 0 の場合に適用しようとすると“絶対値= 0 のベクトル”と“0 ベクトル”が一致しないという難点に遭遇する。とくに標数= 2 の場合は非 0 ベクトルの 2 つに 1 つが絶対値= 0 である点が致命的に思える2 。
この困難を克服するには単独のベクトル、つまり 1 次元部分空間、から 2 次元以上の部分空間に対象を変えるという転換が必要であった。たとえば次のような例がヒントになる。
u = (1; 1; 0)T ; v = (1; 0; 1)T は標数= 2 では共に絶対値= 0 である。しかし内積がつくる行列は†!
†!
(u; u) (u; v)
0 1=(v; u) (v; v)
1 0であるので u; v が張る空間 U の“2 次元空間としての絶対値”は 0 ではない。さらに w = (1; 1; 1)T が張る空間 W を考えると w は u; v と“直交”するので全体空間は U と W の直和に直交分解できる。
実際、任意のベクトル r = (x; y; z)T の U -成分は u; v を並べた行列を U = (u; v) とすると
(U T U )Ä 1 U T rである。
2 逆に言うと標数が（次元に比べて）巨大な場合は“絶対値= 0 のベクトル”と“0 ベクトル”はほとんど常に一致するので標数= 0 の場合と同じに考えて実用上は問題ない。

4.2. LANCZOS 法（標数 P > 0 の場合）

39

ここから一般論。A は正則行列とする。もし W が 2 つの部分空間の直和 W = W1 + W2 になっていてそれらが A-直交していれば任意の w 2 W はw = w1 + w2 ;と書ける。W1 の基底を w11 ; w12 ; . . . ; w1r とし、
w1 =

r
X

wi 2 W i

c1j w1jj=1

とおいて(w1i ; w)A = (w1i ; w1 )A =rX

c1j (w1i ; w1j )A

j=1

で c1j を決めたい。
0

1

0

B
C B
B (w12 ; w)A C B (w12 ; w11 )A
B
C=B
B
B
ÅÅÅ C
ÅÅÅ
@
A @
(w1i ; w)A(w1r ; w11 )A(w11 ; w)A(w11 ; w11 )A

10

1

CB
C
B
C
ÅÅÅ (w12 ; w1r )A C
C B c12 C
C
B
C
ÅÅÅ
ÅÅÅ
A @ ÅÅÅ A
ÅÅÅ (w1r ; w1r )Ac1r
ÅÅÅ (w11 ; w1r )Ac11であるから、右辺の係数行列を S1 とするとき、もし S1 が正則ならば
10
10(w11 ; w)A
c11
C
B
C
B
B
C
B c12 CC = S Ä 1 B (w12 ; w)A C
B
1 B
B ÅÅÅ C
ÅÅÅ C
A
@
A
@
c1i
(w1i ; w)Aである。

ここで w11 ; w12 ; . . . ; w1r を列ベクトルとする行列を W1 とすれば以上は次のように書ける。
0
1
c11
B
C
B c12 CB
C = W1 (W1 ; W1 )Ä 1 (W1 ; w)A
w1 = W 1 B
AC@ ÅÅÅ A
c1i

ここで内積の記号を自然に行列に拡張している。たとえば (W1 ; W1 )A は行列であるから Ä1 乗は逆行列を表す。
この場合の利点は S1 ; S2 が共に正則ならば問題が二つに分割され、逆行列の計算が楽になる。さらに細分され究極の分解である 1 次元空間の直交和になればそれが一番最初の Lanczos 法の発想になる。

4.2.2

Block Lanczos 法（標数 p > 0 の場合）の考え方（１）

標数 0 の場合と同様に全体空間でなく A の作用によって部分空間を作って行くことを考えよう。
b; Ab; A2 b; . . .
今回は“絶対値=0 の非ゼロべクトル”が出てくるので、直交化が１段階ごとにできるとは限らないのである。そこで
b; Ab; A2 b; . . . ; Ae b

CHAPTER 4. LANCZOS 法

40の内積行列が正則になるまで e を増やし、次の Ae+1 b はこれを使って直交化することになる。
しかしこういう e がなければ議論は先に進まない。それで一般の解法は断念せざるを得ない。
では Ax = b という 1 次元の解を求める問題でなく、与えられた部分空間 B に対して
AX ö Bとなる部分空間 X を求める問題にしてみる。こうすることの利点は基底を作るベクトルの“絶対値”が 0でも部分空間としては A-正則でありうることである。
例 4.2. 1

0

B
B 1
A=B
B 0
@
1
0

1

0

1
0
0

0
0
1

である。これから B0 成分を消すと

となるので

1

0

C
0 C
C;
1 C
A
0
1

B
B 1
B = B0 = B
B 0
@
1
0
1
0 1
B
C
B 1 0 CB
C
AB0 = BC
@ 1 1 A
0 1
0

1

C
0 C
C
1 C
A
1
0

0

0
B
B
1
B 0
AB0 + B0 (B0 ; B0 )Ä
A (B0 ; AB0 )A = B
@ 0
0
0

1
1
B C
B 1 C
C
B1 = BB 1 C;
@ A
0

0

とすると

1
1
C
1 C
C
1 C
A
0

1
1
B C
B 0 C
C
として、 AB1 = B
B 0 C
@ A
0

0

1
0
B C
B 0 C
Ä1
Ä1
C
AB1 + B0 (B0 ; B0 )A (B0 ; AB1 )A + B1 (B1 ; B1 )A (B1 ; AB1 )A = B
B 0 C
@ A
0

を作り、B0 ; B1 成分を消して直交化すると0となって、これで解が求まる。

とすると

0
B
B
1
Ä1
B 1
X = B0 (B0 ; B0 )Ä
A (B0 ; B) + B1 (B1 ; B1 )A (B1 ; B) = B
@ 1
0

1
1
C
1 C
C
0 C
A
1

AX = B1
Ä1である。ここで幸運だったのは (B0 ; B0 )Ä
A ; (B1 ; B1 )A が存在したことである。どちらかが作れなかったならば解も得られなかったことになる。また今の場合は偶然 AX = B になったがこれも非常に幸運であった。

4.2. LANCZOS 法（標数 P > 0 の場合）

4.2.3

41

Block-Lanczos 法（標数 p > 0 の場合）の考え方

数体ふるい法では
Ax = 0となる x 6= 0 を求めることが問題である。もちろんこのとき A は正則ではない。この問題には c をいろいろ変えて b = Ac を作り、これに対し

Ay = bの解を見つける。この解から元の解が計算できる。
A(y Ä c) = 0
単独の c ではうまく進まないことはすでに述べた通りである。そこで c を複数（32 個あるいは 64 個程度）
とって単独のベクトルから部分空間に移行する。
ランダムに列ベクトルを n 個とり c1 ; c2 ; . . . ; cn とし、bi = Aci とする。
問題を b1 ; b2 ; . . . ; bn の生成する部分空間を B として
AX ö Bとなる部分空間 X 6= 0 を求めるものに変形する3 。
記号 以下 v1 ; v2 ; . . . ; vr をこの順に並べてできる行列とこれらが生成する部分空間とを同じ記号で表す。
部分空間の列の作り方は、まずW0 = Bから始めてW0 は AÄ内積に関して正則だと仮定する。さらに次々
AWi は AÄ内積に関して正則であると仮定し、AWi から W1 ; W2 ; . . . ; WiÄ 1 成分を除いて A-直交化したものを Wi+1 とする。
このプロセスを進めて行くと、有限次元なので、いつか
AWm ö W1 ＋ W2 + ÅÅÅ+ Wmとなる。つまりW = W1 + W2 + ÅÅÅ+ Wm
とおくとAW ö Wとなる。

定理 4.2. 2 一般に部分空間の直和分解 V = V1 + V2 + ÅÅÅ+ Vr で (Vi ; Vj )A = 0 if i 6= j であるとき V の列ベクトルを並べて作った行列 U は次の分解を持つa 。
U=

r
X

1
Vj (Vj ; Vj )Ä
A (Vj ; U )A

j=1

a V は定義は部分空間だが内積の式の中では基底を並べて作った行列と見ている。
j

3 もちろん C と無縁な解を得たいので X を求める段階では C のことは忘れることにする。

CHAPTER 4. LANCZOS 法

42

この方法の欠点はプロセスが長続きしないことである。AWi はすぐさま A-内積に関して正則でなくなってしまうのである。
そこで、AWi が A-正則でなくても A-正則で maxmal な列ベクトルからなる部分行列をとり、そこから Wi+1 を作る。そして Wi+1 で使われなかった列ベクトルは W (i+1) として次の i に渡し、次では必ずこれを含めた A-正則な部分行列を作ることにする。もし次で使えなかったならこのアルゴリズムは失敗であって、まったく最初からやり直すことになる4 。
W (i+1) を必ずすぐ次で使わなければいけないのは次の理由からである。

補題 4.2. 3
AWi は WiÄ 3 ; WiÄ 4 ; . . . と AÄ直交する
証明 (WiÄ3 ; AWi )A = (AWiÄ 3 ; Wi )A であって AWiÄ 3 は WiÄ2 と W (iÄ 2) に分かれた。後者は WiÄ 1 に含まれるから Wi と A-直交する。
注意 W (iÄ 1) = 0 ならば AWiÄ2 = WiÄ 1 となるので (WiÄ2 ; AWi )A = (AWiÄ 2 ; Wi )A = (WiÄ 1 ; Wi )A =0 である。したがって WiÄ 2 成分を計算する必要はなく直交化の長さは 2 で済む。

4 実験してみると途中の繰り返しで使えないことはまずない。一番最後の繰り返しで起こるのみである。このときは解はほとんど見つかっているのでそのまま進めて問題はない。

4.2. LANCZOS 法（標数 P > 0 の場合）

4.2.4

43

まとめ

n 行 m 列行列 A0 に対し A0 v = 0 となる m 次ベクトル v を（複数）求める方法を以下に記す。
1. m 次対称行列 A = AT0 A0 を考える。
2. s 個のランダムな m 次列ベクトル c1 ; c2 ; . . . ; cs から bi = Aci ; (i = 1; 2; . . . ; s) を作る。
3. 以下 AY ö B となる Y を求める行程を記述する。ただし B は b1 ; b2 ; . . . ; bs で張られた部分空間である。

4. fb1 ; b2 ; . . . ; bs g に対し、maximal な A-正則部分集合をとり、それらを並べて作る行列を W1 とする。
使われなかった列ベクトルを並べて作る行列を W (1) とする。

5. Y = W1 (W1 ; W1 )Ä1
A (W1 ; B) を計算する。
6. i 番目の Wi ; W (i) ができているときに i + 1 番目に移る操作を 7.{12. に記す。
7. AWi の列ベクトルがそれぞれ Wi ; WiÄ 1 ; WiÄ 2 と A-直交するようにする。この列ベクトルの生成する空間、あるいは並べて作る行列を Bi+1 とする。
8. Bi+1 = 0 ならば 13. へ
9. Bi+1 ; W (i) の列ベクトルの集合から maximal A-正則な部分集合をとって Wi+1 とする。このときW (i) の元を優先する。A-正則な部分集合がなければ 14. へ。
10. Bi+1 の元であって使われなかったものを並べて作る行列を W (i+1) とする。
1
11. Y に Wi+1 (Wi+1 ; Wi+1 )Ä
A (Wi+1 ; B) を加える。

12. i を 1 増やして 6. へ戻る。
13. Y Ä C の s 個のベクトルが作る部分空間の元で A0 v = 0 となるものが解となって終了。それを見つけるには A0 (Y Ä C) に列についての基本変形を施して 0 ベクトルの個数を最大にする。同時にY Ä C に同じ変形を施せば 0 ベクトルに対応する列ベクトルが解である。ただし C は c1 ; c2 ; . . . ; cs
を並べて作った行列である。

14. 異常終了である。幸運な場合は Y Ä C の s 個のベクトルが作る部分空間の元で A0 v = 0 となるものがあることがある。それを見つけるには A0 (Y Ä C) に列についての基本変形を施して 0 ベクトルの個数を最大にする。同時に Y Ä C に同じ変形を施せば 0 ベクトルに対応する列ベクトルが解である。十分な個数の解が得られない場合は 2. からやり直し。

注意 1.

A を作らないのは A0 が sparse であっても A は sparse とは限らないからである。とくに A0に dense な列がひとつでもあると A は非常に dense なものとなる。なお A による変換は A0 ; AT0 による変換を続けて行う。A0 ; AT0 のどちらをメモリに置くかで速度が違うことがある。NFS の場合は AT0 を置くのが正解であるようだ。これは素元分解の要素をそのまま並べたものなのでその意味でも都合が良い。
注意 13. Av = 0 だが A0 v 6= 0 ということは A0 のランクが n より小さい時に起こりうる。これを避けるには m を n より大き目にとるのが簡便。NFS の場合は sieve を少し先まで行って 5% Ä 10% 程度多めにデータを集めておけば良い。A0 が確定している場合は 2. からやり直すしかないだろう。
注意 14. 普通はこの型の終了となるので“異常”終了というのは適当ではないかもしれない。20 個以上の解が得られることが多い。

CHAPTER 4. LANCZOS 法

44

4.2.5

高速化

Lanczos 法の律速段階は行列×ベクトルではなくベクトルとベクトルの内積の計算にある。
そこで必要な内積をすべて直接計算するのではなく、できるだけ他の内積などから導き出すことが必要になる。

Chapter 5

数体ふるい法（その３）代数的数の平方根
2002/3/30

CRYPTREC 研究会 at 立教大学 S302 教室
2003/3/31 改訂
木田 祐司

5.1

平方イデアルから平方数へ

Lanczos 法などにより
ã=Y(ai + bi í)i2Iの生成するイデアル < ã > が平方イデアルになるような i の集合 I を見つけることができる。
しかしまだ “平方イデアルである単項イデアル”と“単項イデアルの平方” には違いがある。
ここで Adleman は平方剰余記号を用いて gap を埋めることを考えついた。
è [L.M. Adleman] "Factoring Numbers Using Singular Integers", 23rd STOC(1991) の予稿
K = Q(í) の素イデアルで 1 次のもの P = (p; íÄ s) をとる。ただし p はどの a + bíをも割らないような大きなものとする。このとき a + bíが mod P で平方数であることは a + bs が mod p で平方数である
ことと同じである。
つまり a + bíが K で平方数であるためには a + bs が mod p の平方剰余でなければならない。あるいは a + bs が mod p の平方剰余であれば a + bíが K で平方数である可能性が高まるともいえる。
厳密にはSK = fx 2 K j < x > は平方イデアル gとすると SK =SK \ K 2 の rank は高々 単数群の 2-rank+イデアル類群の 2-rank であることが証明できる。
つまりこの剰余群の生成系になるような複数の P に対して ã 2 K が平方剰余であれば ã は K の平方数である。生成系になることを確かめるのは難しいから余分にとることで代替する。単数群の 2-rank+イ
デアル類群の 2-rank の 2 倍程度を Adleman は提案している。実際の GNFS での計算では多項式の次数が 5 であれば 10 個もあれば十分である。大して手間が変わらないので 32-bit CPU ならば 32 個 にすれば良い。
45

CHAPTER 5. 数体ふるい法（その３）46

そこで最初の解 ã が 32 個の 1 次素イデアルに関して平方剰余になれば平方数であることはほとんど確実である。もし駄目ならば複数の解 ã を組み合わせて 32 個の 1 次素イデアルに対して平方剰余になるものを探せば良い。これはせいぜい 32 次行列の処理なのでまったく簡単である。
素イデアルは 31 個として、あとの 1 個は積の個数mod 2 として積の個数が偶数になるようにすることもある。
例 5.1. 1
C60 = 259405968614692311540344402656970765595208324844841957314041
f (x) = 316526201x5 + 274735005x4 + 5618090324x3 + 6994621459x2 + 6749441074x + 2378868742
m= 15230496453

として GNFS を行ったときの例。以下これを GNFS60 として引用する。
Lanczos 法で得られた 29 個の解に 23 個の 1 次素イデアルによる平方剰余記号と偶数個数判定部分を計算したもの。
解 1 : 000110110101000000110001
解 2 : 011110001100010100010000
解 3 : 000110110101000000110001
解 4 : 011000111001010100100001
解 5 : 011110001100010100010000
解 6 : 000000000000000000000000
解 7 : 011110001100010100010000
解 8 : 000110110101000000110001
解 9 : 011000111001010100100001
解 10 : 000000000000000000000000
解 11 : 001001010011111000010000
解 12 : 011000111001010100100001
解 13 : 001001010011111000010000
解 14 : 010111011111101100000000
解 15 : 000000000000000000000000
解 16 : 011110001100010100010000
解 17 : 000000000000000000000000
解 18 : 011000111001010100100001
解 19 : 010111011111101100000000
解 20 : 001001010011111000010000
解 21 : 010111011111101100000000
解 22 : 010001101010101100110001
解 23 : 010001101010101100110001
解 24 : 010001101010101100110001
解 25 : 010001101010101100110001
解 26 : 000110110101000000110001
解 27 : 001001010011111000010000
解 28 : 010001101010101100110001
解 29 : 001001010011111000010000
この中で組み合わせて 0 になるものを Gauss 消去で探すと独立なものが 26 組あった。

5.2

どういう数の平方根か
この節での課題は
ã=が平方数であることがわかっているときにY(ai + bi í)ã = å2となる å 2 Z[í] を求めることである。

5.3. 一般論：HENSEL LIFT を用いる

47

整数環が UFD の場合は単数と素元によって既約分解し、各々のべき指数を半分にしたべき乗の積を作れば良い。
例 5.2. 1 前節の GNFS60 の場合の例
ã = (Ä101418 + í)(Ä5598 + í)(Ä343 + í)(Ä173 + í)(Ä135 + í)
(67 + í)(318 + í)(3625 + í)(Ä33 + 2í)(Ä21 + 2í)ÅÅÅ(Ä13582 + 57í)(51371 + 11855í)(37656 + 59923í)(Ä25772 + 23449í)(977 + 35646í)(Ä70601 + 85108í)(Ä65263 + 21034í)(Ä96403 + 57785í)(10792 + 67í)(94926 + 18839í)は 48980 個の積であって、その生成する単項イデアルの素イデアル分解は分かっている。
204< ã >= P116588 P213398 P313272 ÅÅÅP38093
P38094
P38095(large primes)2

ここでP1 = (2; í); P2 = (3; íÄ 2); P3 = (5; íÄ 1)
ÅÅÅP38093 = (453461; íÄ 370232); P38094 = (453527; íÄ 293393); P38095 = (453527; íÄ 328256)
である。
したがって

であり

p
1
0
2
< ã > = P18294 P26699 P36636 ÅÅÅP38093
P38094
P38095(large primes)pjN ãj = jN åj = 28294 36699 56636 ÅÅÅ4534611 4535270 4535272 N (large primes)

である。

5.3

一般論：Hensel lift を用いる

NFS とは無関係に、一般に、既約多項式 f (x) のひとつの根 íから定まる代数体 K = Q(í) において
平方数
ã = adÄ1 ídÄ1 + adÄ2 ídÄ2 + ÅÅÅ+ a1 í+ a0 ; ai 2 Q
に対してその平方根 å を
å = bdÄ 1 ídÄ 1 + bdÄ 2 ídÄ 2 + ÅÅÅ+ b1 í+ b0 ;bi 2 Q

計算する方法を考える。
条件 f (x) が mod q で既約となる素数 q が存在する。
この条件を満たさない多項式が稀に存在する。SNFS では多項式が決まっているのでこの条件を満たさない場合がありうるが GNFS ならばいくらでも多項式を変えて条件を満たすようにすることができる。
奇素数 q を f (x) が mod q で既約で、かつ ã は q では割れないものとする。すると q は K でも素数である。
最初の計算が容易なように小さな素数にとる。まず
é02 ã ë 1 mod q

CHAPTER 5. 数体ふるい法（その３）48となる é0 2 Z[í] を求める。つまり ã の逆数の mod q での平方根である。逆数にするのは次の段階のHensel lift における逆数計算を避けるためである。
例 5.3. 1 f (x) = x3 + 2x2 + 3x + 4 とする。

ã = 61í2 + 218í+ 396の平方根を求めたい。
q = 3 としよう。r; s; t; u を 0; 1; ÅÅÅ; q Ä 1 で動かしてÅ2
Ä 2
rí + sí+ t (í2 + í) ë 1 mod qとなるものを探すのだが、代数的数 íを x mod f (x) と同一視すれば

Ä 2
Å2
rx + sx + t (x2 + x) ë 1 mod (q; f (x))

となるものを探すことになる。これは高々 q 3 回のループであるから工夫を凝らす必要はない。
解はすぐに見つかって é= í2 + 1 である。
2

これから始めて modulus を q 2 ; q 2 ; . . . と上げて行く。

5.3.1

Hensel lift

命題 5.3. 2
éj 2 ã ë 1mod < q >2のとき
éj+1 = éj + éjj

1 Ä éj2 ã
j+1
mod < q >2
2

j

j+1

とすれば (éj は mod < q >2 で、ã は mod < q >2で計算する)j+1

2
ã ë 1mod < q >2
éj+1

である。
k

Hensel lift を繰り返して q 2 が十分大きくなればkék2 ã ë 1mod < q >2よりk(ék ã)2 ë ãmod < q >2kkとなって ék ã の係数を [ Äq 2 =2; q 2 =2 ) でとったものが求める平方根（のひとつ）になる。
例 5.3. 3 今までの計算を続けると
mod 32 = 9 では
é1 = 4í2 + 6í+ 4であり、このとき
é1 ã ë 4í2 + 4íÄ 3 mod 32

5.4. 中国の剰余定理を用いる

49

となる。
mod 34 = 81 では
é2 = 13í2 Ä 12í+ 13
であり、このとき
é2 ã ë Ä5í2 + 4í+ 6 mod 34である。
これより Ä5í2 + 4í+ 6 が解らしいことがわかる。試してみると実際にそうである。

5.4

中国の剰余定理を用いる

簡単のため íは代数的整数であるとする。
NFS の場合に戻ると ã は小さな数の多数の積になっていた。これを前節の方法で処理しようとすると積を展開しなければいけない。それは非常に大きくなって計算が不可能になる。このような時のいつもの手段である中国の剰余定理を適用してみる。つまり、複数の modulus を用いて間接的に計算するのである。
q を有理素数で K = Q(í) においても q が生成する単項イデアルは素イデアルであるものとする。こういうものを複数用意する。
ã=Y(ai + bi í) = gdÄ 1 ídÄ 1 + ÅÅÅ+ g1 í+ g0 ;i2I

gi 2 Zの gi は巨大であってもã ë gq;dÄ 1 ídÄ 1 + ÅÅÅ+ gq;1 í+ gq;0 mod < q >の gq;i は非常に小さい。
q を十分な個数だけ準備すれば gi は gq;i mod q の集まりで間接的に表現される。
このときã ë (åq )2 mod < q >となる åq は簡単に計算できる。ã = å2 とすると
åë Üåq mod < q >である。しかしこの正負が q によってまちまちであって決めることができない。それは次のような有理整数の平方根の場合と同様である。
例 5.4. 1

であるが

である。

p

841 = 29 であって

8
2>
< (Ü1)
841 ë
(Ü1)2
>
:
(Ü1)2
8
>
< Ä1
29 ë
Ä1
>
:
1

mod 3
mod 5
mod 7

mod 3
mod 5
mod 7

CHAPTER 5. 数体ふるい法（その３）50

Couveignes の方法

5.5

è [Jean-Marc Couveignes] "Computing a square root for the number åeld sieve", in Lenstra andLenstra(Eds.) The development of the number åels sieve, Lecture Notes in Math. 1554, pp 95{102による方法を解説する。この方法では以下の仮定は必須である。
仮定

次数 d は奇数である。

前節では
åë Üåq mod < q >となる Ü が各 q ごとに異なることが障害であった。
しかし、上の仮定をおけばN (Äå) = (Ä1)d N (å) = ÄN (å)
であるから二つの平方根 Üå はそのノルムで区別できる。そこでノルムが b =p
N (ã) であるものを å としてこれを mod q で定める、というのが Couveignes のアイディアである。
前節にならって ã の逆数の平方根 éを求めることから始めるが奇数次なので前節のように総当りで探すのではなくもっとスマートに答えを見つけることができる。
命題 5.5. 1(1+q+q2 +ÅÅÅ+q dÄ 1 )(qÄ 2)Ä 1
2

é= ã

Åb mod < q >とおくと(éã)2 ë ã mod < q >かつN (éã) ë b mod qである。
たくさんの q で計算するよりも Hensel lift でいくらか q のべきを上げて使う方が効率が良いことが多い。しかしべき指数を上げすぎると中国の剰余定理を用いた意味がなくなってしまう。
例 5.5. 2 f (x) = x3 + 2x2 + 3x + 4 とする。
ã = 61í2 + 218í+ 396の平方根を求めたい。
N ã = 27984100
なので1 b = 5290 である。これより
å = éã = 2í2 + 2í mod < 3 >である。
mod 11 ではå = éã = 5í2 Ä 4í+ 5 mod < 11 >1 この場合はノルムを計算するのが面倒であるが NFS の場合は簡単に求まる。

5.5. COUVEIGNES の方法

51

である。
よって å = aí2 + bí+ c とおいて
a

ë

b

ë

c

ë

8
>
< a
b
>
:
c

を解けば

(

2

( 5
2

mod 3
mod 11mod 3( Ä4 mod 11
0 mod 35

mod 11

ë 5 mod 33
ë Ä4 mod 33
ë Ä6 mod 33となる。すると 5í2 Ä 4íÄ 6 が候補になる。計算すると確かに解である。

5.5.1

中国の剰余定理の変形

素因数分解で必要になる値は，ターゲットの数 N を法とした値であることが多い。そのため中国の剰余定理も実際の値そのものではなく mod N の値を求めるものに変形しておくと巨大な数をそのまま扱う必要がなくなるというメリットが出てくる。
sY
問題 m1 ; m2 ; . . . ; ms は二つずつ互いに素な自然数とし，M =mi とする。
Ä0:49M < x < 0:49M にある x が2

8>
x1 mod m1>>>< x mod m
2
2
xë
>
ÅÅÅ
>
>
>
: x mod mssi=1を満たしているときに 0 < N < M なる N に対して x mod N を計算せよ。
通常の解法にならえば
Mi = M=mi ; ai = 1=Mi mod mi
とおいて3
z=

s
X

ai xi Mi

i=1

とすれば

x ë z mod Mとなるのであった。これから Ä0:49M < x < 0:49M となる x を定めて mod N で落とせば良い。問題はM のオーダーでなく N のオーダーの計算で済ませたいということ。
2 0:49 は誤差を見込んでいる。本来は 0:5 である。

3 a のための M は modm で計算すれば良いが、次の z のための M は modN の値であることに注意。つまり二通りに計iiii
算しなければいけない。

CHAPTER 5. 数体ふるい法（その３）52
x = z Ä rM; r 2 Z とすると

Ä0:49 <zÄ r < 0:49
M†z
) であるからより r = round( Mr = round

s
X
ai xi

mi

i=1

!

となり，mi 程度の大きさの実数の s 個の和であるから倍精度程度の計算で十分である。これで x = z Ä rMが確定する。この式の各項を mod N で計算すれば良い。

5.5.2

高速化
ã=

r
Y

(ai + bi í)i=1の右辺の積を二つに分ける
ãodd

=

ãeven

=

r
Y

(ai + bi í)i=1; i oddrY(ai + bi í)i=1; i even

そして

ãodd
ãeven
を考える。ここで c は両辺を代数的整数にするために掛ける数である。係数を小さくするという点では代数的数をとるべきであるがなかなか難しい。有理整数にとれば簡単ではある。
そこでç2 = ã
ã = c2となる ç を計算して
ç= çãeven =cとおけば
ç2 = ã
である。
簡単のため奇数番目と偶数番目に分けたが、目的は分子・分母の相殺にあるのだから large primes が一致するぺアは分子・分母に分かれるようにしたい。それにはあらかじめ ai + bi íを large primes が消し合うペアが続き番号になるようにしておけば良い。
例 5.5. 3 GNFS60 の場合の例
ã = (Ä101418 + í) ÅÅÅ(94926 + 18839í);(48980 個の積)

に対して
2
0
4
< ã >= P116588 P213398 P313272 ÅÅÅP38093
P38094
P38095(large primes)2

であったが

ãodd
Ä2
0
0
> = P136 P2Ä 130 P310 ÅÅÅP38093
P38094
P38095ãeven
となって大幅にべき指数が小さくなっている。また large primes 部が消えるようにも並べ替えている ((1+1)
large primes ではこれが可能)。
<

5.6. MONTGOMERY の方法

5.6

53

Montgomery の方法

è [Peter L. Montgomery] "Square Roots of Product of Algebraic Numbers", Proceedings of Symposia
in Applied Mathematics 48(1994), 567{571.

è [Phong Nguyen] "A Montgomery-Like Square Root for the Number Field Sieve", in ANT III,
Lecture Notes in Computer Sciences 1423(1998), 151{168.
の簡単な紹介をする。話の都合上記号も変更している。
NFS の場合は各 ai + bi íが生成する単項イデアルの素イデアル分解はわかっているから容易に
ã=の生成する単項イデアルの平方根イデアル

Y(ai + bi í)p< ã > はわかる。かつその素因子は具体的に書けている。

例 5.6. 1 GNFS60 の場合の例では ã は 48980 個の積であって、
1
02
P38094
P38095(large primes)< å >= P18294 P26699 P36636 ÅÅÅP38093であった。ここで P1 = (2; í); P2 = (3; íÄ 2); . . . である。
前節のように積を分けると
<

2
ãodd
P 36 P 10 P4380 ÅÅÅP38089>= 1 1303 134
2ãeven
P2 P5 ÅÅÅP38093と簡単になる（このときの ai + bi íの分子・分母への割り振り方も重要な問題である）。
そこで問題をこの平方根イデアル
P118 P35 P4190 ÅÅÅP38089
P265 P567 ÅÅÅP38093の生成元、これも å と書くことにする、を求めることにする。
一気に求めるのは無理なので段階的に行う。まず分子の一部 I をノルムがある適当な大きさ（100 桁程度）になるだけ取り出す。たとえば I1 = P118 P35 としよう。
å1 2 I1 とすると
< å1 >= I1 ÅH1という“誤差”イデアル H1 が出てくる。これを小さくするために LLL-algorithm を用いてできるだけshort なものを見つける。すると<å

1
P4190 ÅÅÅP38089>=
1
å1
H1 P265 P567 ÅÅÅP38093となる。次は分母の一部、たとえば H1 P265 を単項イデアルに置き換える。
<å

H2 P4190 ÅÅÅP38089
å2
>=
1
å1
P567 ÅÅÅP38093

これを繰り返す。最初にあった素イデアルを全部使い果たせば終了である。右辺の分子・分母のノルムの積がその前よりも常に小さくできたとすると最後に残る誤差イデアル H はノルムが非常に小さい。
このとき
å2 å4 ÅÅÅ2< ã() >= H Ü 2
å1 å3 ÅÅÅ54

CHAPTER 5. 数体ふるい法（その３）である。
ここで左辺は“小さな”平方数であるが多くの数の積であるので最終的には小さくても展開することは困難である。そこで適当な素数を法にして中国の剰余定理で計算することになる。
実際には、いろいろ注意しなければいけないことがある。たとえば最後の式の左辺はノルムが小さな数であるが、それは必ずしも“小さな”数であることを意味しない。たとえば単数の巨大なべきかもしれない。これを避けるためにこの数のすべての共役の絶対値が小さくなるような制約をつけた LLL-algorithmを実行することになる。