2011年12月3日土曜日

素因数探し

11月6日の本ブログにある自転車チェーンの篩を作ったのはHenry Lehmerだ. その父親のNorman LehmerもCalifornia大学Berkeley校の数学の教授であった. 父のLehmerが素因数探しの道具として, Factor Stencilを考案したという話がある.

それがどういうものかが分かってきた. 今回はその話をしよう.

aが素数pの平方剰余であるとは, x2=a mod pとなる何かのxがあることなのは周知のとおり. こういうa(≠0)の時, Legendreの記法で(a/p)=+1とする. (htmlなので, 分子分母が横並びだが, 通常は上下に書く.)

xがないときは, aを平方非剰余といい, (a/p)=-1とする.

p=7の時, 剰余は(0,1,2,4), 非剰余は(3,5,6)である. ここで, 0を除外し, 非剰余同士を掛けると, 3*3=2 mod 7, 3*5=1 mod 7, 5*5=4 mod 7のように剰余になり, 剰余と非剰余を掛けると2*3=6 mod 7のように非剰余のまま, 剰余同士を掛けると4*4=2 mod 7で剰余であり, +1と-1で掛算になる.

ところで, ある整数Nを素因数分解する場合, 任意の整数aについて, a2-N=Rは, Nがpで割れるなら, mod pで考えると, Nの項はないのと同じだから, Rはこのpの平方剰余になる.

aを√Nの程度にとると, Rは小さくなり, 平方剰余の乗算に規則でもっと分解すると, さらに小さい剰余か非剰余が得られ, それから素因数の形が決るという.

たとえば, 平方剰余に-1があるなら, すなわちp-1なら, 素因数は4n+1, 2があるなら, 素因数は8n±1の形, というふうに, 素因数はlinear formになっている. それを組み合せて, 素因数の探索の範囲を狭めたい. ところが, 平方剰余が段々大きくなってくると, linear formの形も複雑になり, 式の形を決めにくくなる. Normanの論文によると, Rが113と199の場合, formの形は11088にもなるそうだ.

そこで, 各平方剰余について, 候補になる素数の表をあらかじめ作っておこうというのが, この発想である.

小さい範囲で, テストしてみよう. 下がその剰余(縦方向)と素数(横方向)の表である. 10月26日のブログの図の素数のところを抜き出したものと思えばよい.

3 5 7111317192329313741434753596167717379838997
-1 X X X X X X X X X X X
2 X X X X X X X X X X X
3 X X X X X X X X X X X
5 X X X X X X X X X X
7 X X X X X X X X X
11 X X X X X X X X X X
13 X X X X X X X X
17 X X X X X X X X X
19 X X X X X X X X X X

Normanの素数表には1があるというので, この左に1と2の列があるかも知れないが, 除数としては不要なので, とりあえず3からの表だ. 7の下を見ると, 2と11にXがあり, 2と11=4 mod 7が平方剰余であることを示す. 他の素数についても同じだ. たとえば,

(quadres 97)=>(0 1 2 3 4 6 8 9 11 12 16 18 22 24 25 27 31 32
33 35 36 43 44 47 48 49 50 53 54 61 62 64 65 66 70 72 73 75
79 81 85 86 88 89 91 93 94 95 96)

のうち, 19までの素数, 2,3,11と, 96(= -1 mod 97)があるから-1とにXがある.

また, 横向きに眺めると, -1の行は, 5,13,17,29,37,41,53,61,73,89,97で, すべて4n+1. 2の行の7,23,31,47,71,79は8n-1, 17,41,73,89,97は8n+1である.

さて, これを使い, N=2279(=43x53) の素因数を探してみる. (sqrt N) => 47.738873049120045 だから, aを48から順に増やしながら, a2-Nを計算し, その素因数分解もしておく.

(map (lambda (a) (factorize (- (* a a) n))) (a2b 48 80))
=> ((5 5) (61 2) (17 13) (23 7 2) (17 5 5) (53 5 2) (13 7 7)
(373 2) (857) (97 5 2) (31 7 5) (601 2) (1321) (103 7 2)
(313 5) (13 13 5 2) (79 23) (139 7 2) (67 31) (17 13 5 2)
(67 7 5) (73 17 2) (2621) (1381 2) (83 7 5) (61 5 5 2)
(139 23) (239 7 2) (269 13) (73 5 5 2) (761 5) (283 7 2))

ここに並んでいるのは, 掛けると+1になるもの同士である. (5 5)からは, 5が+1かも, -1かも知れないということが分かるだけだ. (61 2)では, 61が上の表の剰余にないから, 無視. (17 13)は, とりあえず13と17は+1と+1か, -1と-1が分かっただけ. その次の(17 5 5)はラッキーだ. 5と5は打ち消すから, 17が+1と判明した. したがって, (17 13)から, 13も+1と決る.

(13 7 7)からも13が剰余と確信出来る. さらに進むと, (13 13 5 2)や(17 13 5 2)から, 2と5は+1同士か-1同士か, いずれにしろ同じ仲間ということが分かるが, 役にたつかどうかは不明.

しかし, 13と17が得られたので, 13と17の行にXのある素数を探すと, ブラボー! 43と53が見つかった. ついでだが, 43と53の列では, 2と5は空白で, 同じ組なことが示せる. いまは1組だけが見つかったが, 通常は候補がたくさん得られ, 実際に割ってみる必要がある.

Norman Lehmerが1914年に出版したFactor Stencilは, 剰余が±238まで, 素数が48593までの素数表であって, 各剰余ごとに1枚で, Xの代りに素数の位置に孔をあけてある. 今の例では13と17の紙を取り出してきて重ねると, 条件に合う素数のところから光が洩れる仕掛けであった. 当時としては大変な労作であった. いまでは, MacBookで簡単に実験が出来, ありがたい時代だ.

0 件のコメント: