2004年7月アーカイブ

MS04-025

| コメント(0)

修正プログラムの内容

MS04-025 : Internet Explorer の重要な更新

Internet Explorer 用の累積的なセキュリティ更新プログラム (867801)

最大深刻度

緊急

影響を受けるソフトウェア

Microsoft Internet Explorer 5.01

Microsoft Internet Explorer 5.5

Microsoft Internet Explorer 6

絵でみるセキュリティ情報

絵でみるセキュリティ情報 MS04-025 (Microsoft Security、7 月 31 日)

詳細情報

Internet Explorer 用の累積的なセキュリティ更新プログラム (867801) (MS04-025) (Microsoft TechNet、7 月 31 日)

ダウンロードおよびインストール

インストール後、再起動が必要。

Windows Update (Microsoft)

関連記事

マイクロソフト、修正ソフト提供 閲覧ソフト欠陥で (asahi.com : 経済、7 月 31 日)

GGNFS-0.50.2

| コメント(0)

数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS-0.50.2 が公開されました。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

メモ

GGNFS-0.50.* で途中まで columns 0 という表示が続くのは、デフォルトで getdeps の処理の一部を省略して全体の所要時間を短くする工夫が施されているためです。そのまま続行して問題ありません。なお、Changelog に書かれているように GGNFS-0.50.2 では getdeps に -forceCC を指定することでこの機能を解除することができます。

71, 701, 7001, 70001, 700001, ...

| コメント(0)

数列 7·10n+1 = { 71, 701, 7001, 70001, 700001, ... } (n≤100) の素因数分解表を追加しました。未分解の合成数はありません。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

Factorizations of 700...001

GGNFS-0.50.1

| コメント(0)

数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS-0.50.1 が公開されました。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

GGNFS-0.50.0

| コメント(0)

数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS-0.50.0 が公開されました。数日前に Chris Monico さんと「GGNFS が分解のついでに因数の PRP チェックをしてくれると後でそれを分解し忘れることが減ってよいかも」という話をしたのですが、今回他の更新と併せて早速採用してくださった模様。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

Near-repdigit Palindrome の場合

| コメント(0)

GGNFS で素因数分解するときに多項式をいつも 5 次にしていたのですが、中央の 1 桁だけ数字が異なる Near-repdigit Palindrome な数は 4 次のほうが都合がよいので 4 次で分解してみました。

GGNFS の結果
-versiontarget<digits>
factor
polyskewRLIM
ALIM
LPBR
LPBA
MFBR
MFBA
RLAMBDA
ALAMBDA
QSTEPtotal time
actual time
230.42.0(1093+45·1046-1)/9 <93>
P39 · P54
10·(1023)4+45·(1023)2-11300000
300000
25
25
38
38
1.6
1.6
100000.4 hours
1.4 hours

(1093+45·1046-1)/9 = (1)466(1)46<93> = C93

C93 = P39 · P54

P39 = 363639540323592843973557326487709158203<39>

P54 = 305552886279188406342444476482262011754545879096939237<54>

87, 877, 8777, 87777, 877777, ...

| コメント(0)

数列 (79·10n-7)/9 = { 87, 877, 8777, 87777, 877777, ... } の素因数分解表を n≤150 まで伸ばしました。未分解の合成数が 20 個残っています。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

Factorizations of 877...77

どーなつ

| コメント(0)

たべたい。

ソースコード。

d を定数として { p1, p1+d, p1+2d, ..., p1+(n-1)d } がすべて素数になるような数列は Prime Arithmetic Progression(等差数列をなす素数)と呼ばれています。2004 年 7 月 24 日、56211383760397+44546738095860*k が k=0,1,...,22 についてすべて素数になることが Markus Frind さんのチームによって発見され、等差数列をなす素数の項数の世界記録が 23 項になりました。22 項から成る等差数列をなす素数は 1993 年に発見されており、11 年ぶりに項数の世界記録が更新されました。

23 primes in arithmetic progression

Prime Arithmetic Progression -- from MathWorld (MathWorld)

Pollard の p-1 法(続き)

| コメント(0)

きのうのコードで Pollard の p-1 法を遂行している箇所はこれだけです。素数を 2 から順にピックアップし、cq の q に素数を掛ける代わりに cq を n を法として素数乗して毎回 gcd(cq-1, n) を計算しています。p-1 が小さい素因数を複数持っていた場合に備えて 10 以下の素数は 8 個まで、100 以下の素数は 4 個まで、1000 以下の素数は 2 個まで受け付けるようにしてあります。このような細かいところはてきとうなので万全ではなく、gcd が n になってしまって分解できない場合もあります。小さい素因数を見逃すことのないように最初に n が素数で直接割り切れる場合を除外しているので理論的には必ず止まるはずですが、きのうの例のような都合のよいターゲットでなければ大きな素因数が見つかるまでに膨大な(あるいは非現実的な)時間がかかってしまいます。なお、このコードでは多倍長整数演算のために GMP(The GNU MP Bignum Library)を利用しています。

Pollard の p-1 法

| コメント(0)

たまには初心に帰って初歩的な素因数分解アルゴリズムを見直してみるのもよいかも知れない。

フェルマーの小定理より、任意の素数 p について

gcd(c,p)=1 ならば cp-1≡1 (mod p)

が成り立つ。未知の素数 p を合成数 n の求めるべき素因数とすると、もしも q が p-1 の倍数ならば

cq≡1 (mod n)

が成り立つ。このとき

gcd(cq-1, n)

を計算すると p が求まる可能性がある。ここで p が未知なので p-1 の倍数 q を直接決定することはできないが、例えば p-1 の素因数がすべて十分に小さくて重複がなければ q として素数階乗を順に試すことで q が p-1 の倍数となって p が見つかることがある。Pollard の p-1 法は p-1 が小さい素数の積で構成されている場合に n の素因数 p を発見できる可能性が高い。

以下はてきとうに書いたサンプルコードと出力結果です。初歩的なアルゴリズムと大雑把なプログラムですが 411...11<119> の 30 桁の素因数が 33 秒で見つかっています。

59, 599, 5999, 59999, 599999, ...

| コメント(0)

6·10n-1 = { 59, 599, 5999, 59999, 599999, ... } の素因数分解表が n≤150 まで完成しました。最後まで残っていた 6·10149-1 も含めて難易度の高いターゲットの多くが、Chris Monico さんが自ら開発した GGNFS を用いて分解されました。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

Factorizations of 599...99

とんでもない報告は…

| コメント(0)

GMP-ECM で 64 桁もある因数が見つかったというものでした。しかし残念ながら素数ではなかったため、世界記録の更新とはなりませんでした。残念。

東京で観測史上最高気温

| コメント(0)

冷房で冷えた身体をお風呂で温めて体温調節機能を回復させましょー。

東京猛暑: 都心で最高の39.5度 学校は夏休みに (MSN-Mainichi INTERACTIVE 今日の話題、7 月 20 日)

ワンクリック気象情報サイト [tenki.jp] (tenki.jp)…アメダスのデータとか

GGNFS の結果(続き)

| コメント(0)

GGNFS による分解の結果の続きです。今回はいずれも 10n-3 のテーブルの未公開部分に残っていた合成数をターゲットにしています。前回の結果で total time と actual time の差が極端に大きいように思えたということを書きましたが、その結果を見てくださった Chris Monico さんから「QSTEP をあと 3~4 倍大きくすべし」との助言をいただきました。QSTEP はサンプルと比較して大きめにとっていたつもりだったのですが、実は小さすぎたようです。QSTEP を増やす前の 7 番の結果は total time と actual time が倍近くも離れているのに対して、その後の結果は比較的近い時間を示しています。なお、10 番の actual time の 13.5 時間にはテレビ番組を DVD 画質で録画していた時間なども含まれているのであまり参考になりません。

GGNFS の結果
-versiontarget<digits>
factor
polyskewRLIM
ALIM
LPBR
LPBA
MFBR
MFBA
RLAMBDA
ALAMBDA
QSTEPtotal time
actual time
70.41.410125-3 = 99...997<125>
224027 · P47 · P74
(1025)5-32500000
500000
25
25
38
38
1.7
1.7
500003.8 hours
7.4 hours
80.42.010116-3 = 99...997<116>
563 · 1321 · 8774317 · P46 · P59
10·(1023)5-31600000
600000
25
25
40
40
1.5
1.5
2000003.2 hours
4.5 hours
90.42.010118-3 = 99...997<118>
13 · 8461 · 89293 · P50 · P60
1000·(1023)5-31700000
700000
25
25
40
40
1.5
1.5
3000002.9 hours
3.5 hours
100.42.010135-3 = 99...997<135>
P52 · P84
(1027)5-32800000
800000
25
25
42
42
1.8
1.8
20000010.1 hours
13.5 hours

ぴぎゃ

| コメント(0)

素因数分解に参加してくださっている方からまたとんでもない報告が。データが残っているとよいのですが…。

コンビニ

| コメント(0)

自宅から最寄りのコンビニが潰れていた。ただでさえ少ないコンビニが潰れるということはやはりコンビニが繁盛しない土地柄なのだろうか。一応都内なのに。まあ、そういう私もサイクリングに行くときの補給基地にしていただけなのでなくなってもあまり困らないのだが。

GGNFS-0.42.0

| コメント(0)

Chris Monico さんによる数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS-0.42.0 が公開されました。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

素因数分解のページには GGNFS による成果が続々と寄せられてきています。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

GGNFS の結果

| コメント(0)

特に大きなターゲットというわけではありませんが、GGNFS でいくつか続けて結果を出せたのでまとめておきます。動作環境は Pentium 4 (3.06GHz) + Windows XP + Cygwin です。total time は summary.txt が示した所要時間で、actual time は ggnfs.log に記録された時刻をもとにして計算した実際の所要時間です。CPU 時間と実時間には差があるものですが、その差が極端に大きいように思えたので併記しました。

GGNFS の結果
-versiontarget<digits>
factor
polyskewRLIM
ALIM
LPBR
LPBA
MFBR
MFBA
RLAMBDA
ALAMBDA
QSTEPtotal time
actual time
10.41.2(8·10114-53)/9 = 88...883<114>
P34 · C81
(2·1023)5-212052000000
2000000
26
26
42
42
1.3
1.3
200007.1 hours
13.3 hours
20.41.3(5·10120+31)/9 = 55...559<120>
P49 · P72
5·(1024)5+313500000
500000
24
24
38
38
1.6
1.6
500003.2 hours
5.3 hours
30.41.3(7·10120+11)/9 = 77...779<120>
P32 · P88
7·(1024)5+112500000
500000
25
25
38
38
1.7
1.7
500002.5 hours
4.4 hours
40.41.310117-3 = 99...997<117>
P55 · P63
100·(1023)5-31400000
400000
25
25
38
38
1.5
1.5
500002.7 hours
6.0 hours
50.41.410109-3 = 99...997<109>
7 · P38 · P71
(1022)5-303500000
500000
25
25
38
38
1.5
1.5
500001.1 hours
1.9 hours
60.41.410115-3 = 99...997<115>
7 · 149 · 16427 · P40 · P69
(1023)5-32500000
500000
25
25
38
38
1.4
1.4
500001.7 hours
3.3 hours

2 番目以降の結果は skew と RLAMBDA/ALAMBDA だけ「少し走らせて total yield の 10 行目が大きくなるパラメータを探す」という安直な方法で調節してあります(本来ならば sec/rel が小さい値で安定するところを探すべきなのでしょう)。他のパラメータはてきとうです。パラメータの意味を理解して調節すればもっと短い時間で分解できるのだろうと思いますが、GGNFS 自体がとてつもなく速いので、調節しなくてもそれなりの速さで分解できてしまうようです。

GGNFS-0.41.4

| コメント(0)

毎日更新されてる感じ。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

GGNFS-0.41.3

| コメント(0)

Chris Monico さんによる数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS-0.41.3 が公開されました。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

以下修正

GGNFS-0.41.3 を用いて 120 桁の合成数を 3.2 時間で素因数分解することができました。120 桁を 3.2 時間ならばかなりよい結果だと思いますが、Chris Monico さんによると GGNFS の性能を十分に引き出せば 120 桁くらいの合成数をおよそ 2 時間で分解できる可能性があるそうなので、パラメータの調節の仕方をさらに研究する必要があります。

(5·10120+31)/9 = 55...559<120> = C120

C120 = P49 · P72

P49 = 2127666489834611980661167828223343389502794179267<49>

P72 = 261110262444721806325168353526635035696487002455697756234202026774456077<72>

最初に書いた 7 時間余りという結果は直前に GGNFS-0.41.2 で分解した 114 桁の合成数のときのものでした。

(8·10114-53)/9 = 88...883<114> = C114

C114 = P34 · P38 · P44

P34 = 1011528898734447400210111073544323<34>

P38 = 10598242759881902413936852172705829271<38>

P44 = 82915422806132866288534004585777894097788951<44>

999999999999999799...99

| コメント(0)

999999999999999799...99 の形の素数の探索は現在知られている最大の Near-repdigit な素数を超える 11 万桁台にさしかかったところでとりあえず終了しました。結局素数は 1 個も発見されませんでした。

GGNFS v.0.41.2

| コメント(0)

Chris Monico さんによる数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS v.0.41.2 が公開されました。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

GGNFS v.0.41.1

| コメント(0)

Chris Monico さんによる数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS v.0.41.1 が公開されました。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

MS04-018~MS04-024, KB842773

| コメント(0)

999999999999999799...99

| コメント(0)

おととい書いた 999999999999999799...99 という形の素数が見つからないという話ですが、探索範囲が明日には 10 万桁に達する見込みです。しかし、今のところ予想通り素数は 1 つも見つかっていません。桁数が増えると素数が出現する確率が低くなると同時に素数判定にかかる時間が増大してゆくので、発見はますます困難になってゆきます。

GGNFS v.0.41.0

| コメント(0)

Chris Monico さんによる数体ふるい法を用いた素因数分解プログラムの最新版 GGNFS v.0.41.0 が公開されました。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

999999999999999799...99

| コメント(0)

いろいろな Near-repdigit な数列を調べていて面白いものを見つけました。

9999999999999997

99999999999999979

999999999999999799

9999999999999997999

99999999999999979999

999999999999999799999

9999999999999997999999

99999999999999979999999

:

だいぶ先のほうまで探してみたのですが、この数列には素数が見当たりません。「すべての要素が合成数であるとは限らない(はずの)数列で素数が 1 つも見つからない」というケースに初めて遭遇しました。素因数分解のページに掲載している Room for prime numbers(周期的に現れる素因数で割り切れない要素の割合の上限)の値は 1.31576% と極端に小さくなっています。最小の素数を見つけることができたらそれはそれで面白そうなのでもう少し探索を続けてみます。たぶん見つからないと思いますが…。

GGNFS version 0.40.3

| コメント(0)

Cygwin 上で make がなかなか最後まで通らなくてソースをあちこち書き換えちゃったけど大丈夫かなぁ。

899...99, 99...991, 799...99

| コメント(0)

9·10n-1, 10n-9, 8·10n-1 の素因数分解表が n≤150 まで完成しました。最後まで残っていた合成数は Tetsuya Kobayashi さんによって分解されました。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

私の素因数分解のページに GGNFS の試し斬りにちょうどよさそうなサイズの合成数がごろごろしているためか、GGNFS の作者の Chris Monico さんご本人からメールをいただいてしまいました。GGNFS について素因数分解結果を寄せてくださっている方から使い方を教えていただいてもなおパラメータの選び方がしっくりこなくて説明を書けずにいた私は恐縮してしまったのですが、私がぐずぐずしている間にも GGNFS はバージョンアップが続けられており、その実力を大いに発揮しつつあるようです。過去の分解を模倣したケースでおそらくベストケースに近い記録なのだろうと思いますが、それにしても 144 桁の合成数を数体ふるい法で分解するの 33 時間しかかからなかったというのは半端な速さではありません。私はちゃんと理解できていないのですが Jens Franke's lattice siever の効果によるところが大きいとのことです。これはもう頑張って使いこなすしか…。

GGNFS - A Number Field Sieve implementation (Chris Monico さん)

Factorizations of near-repdigit numbers(STUDIO KAMADA)

99999998&middot;10^19552-1

| コメント(0)

最近見つけた Near-repdigit な素数。19560 桁しかなく、自己記録は更新したものの Near-repdigit な素数の Top20 には程遠い。Near-repdigit という限られた範囲で新たな巨大素数を見つけるには、相当な強運か化け物のようなマシンパワーのいずれかが必要なのかも知れない。

100...007, 100...009, 400...001

| コメント(0)

素因数分解のページに 100...007, 100...009, 400...001 のテーブルを追加しました。公開した n≤100 の範囲については分解が完了しているので合成数の増加はありません。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

メモ

4·104k+1 = (2·102k-2·10k+1)(2·102k+2·10k+1)

100...003, 166...667, 300...001

| コメント(0)

素因数分解のページに D(R)wE の形の quasi-repdigit な数列のテーブルをいくつか追加しました。今回追加したテーブルは 100...003, 166...667, 300...001 の 3 つです。いずれも他の Near-repdigit な数列と代数的に関連があり、公開した n≤100 の範囲については分解が完了しているので合成数の増加はありません。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

"7773" の右側に "7" を並べた Near-repdigit な数はほとんど合成数だ。この形の最小の PRP は 1338 桁もある。その値を式で書くと (69964·101334-7)/9 となる。時間がかかりそうなので証明していないがおそらくこれがこの形で最小の素数だろう。自明でない Near-repdigit な数列で先頭から 1000 項以上も合成数が続くのは珍しい。

Room for prime numbers

| コメント(0)

素因数分解表に Room for prime numbers という情報を追加しました。この情報は Near-repdigit や Plateau and Depression の数列に周期的に現れる小さな素因数で割り切れない項の割合の上限を示しています。例えば33...331の Room for prime numbers は 70.8725% となっており、この数列には素数が出現しやすいことがわかります。また、944...449955...559の 0% という値はこれらの数列がすべて合成数であることを意味しています。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

7, 27, 227, 2227, 22227, ...

| コメント(0)

数列 (2·10n+43)/9 = { 7, 27, 227, 2227, 22227, ... } の素因数分解表を n≤150 まで伸ばしました。未分解の合成数は 20 個です。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

Factorizations of 22...227

IE の ADODB.stream オブジェクトに関するセキュリティホールの修正プログラムが出ています。Windows Update で更新できます。

説明

870669 - How to disable the ADODB.Stream object from Internet Explorer (Microsoft Support、7 月 3 日)→@nifty 翻訳

インストール

Windows Update (Microsoft)

土星のわっか

| コメント(0)

カッシーニが土星周回軌道に投入された直後に撮影した土星のリングの画像が公開されています。画像にはリングの密度の違いによって生じる縞模様の一部が写っています。探査機がリングを横切った直後に撮影したため相対速度が速すぎて連続撮影が間に合わず画像を補間できなかった部分があるとのことで、公開された画像はすだれ状になっています。

Cassini-Huygens: Multimedia-Images-Latest Images (NASA JPL)

[1] [2] [3] [4] [5] [6]

First pictures from Saturn orbit show rich ring detail (Spaceflight Now、7 月 1 日)→@nifty 翻訳

61, 611, 6111, 61111, 611111, ...

| コメント(0)

数列 (55·10n-1)/9 = { 61, 611, 6111, 61111, 611111, ... } の素因数分解表を n≤150 まで伸ばしました。未分解の合成数は 20 個です。

Factorizations of near-repdigit numbers(STUDIO KAMADA)

Factorizations of 611...11

カッシーニ

| コメント(0)

カッシーニは予定通り土星軌道に投入されました。

Cassini successfully arrives at Saturn (Spaceflight Now、6 月 30 日)→@nifty 翻訳

土星探査機カッシーニ

| コメント(0)

遥か土星へ向かって 7 年近い宇宙の旅を続けてきた探査機カッシーニが SOI(Saturn Orbit Insersion、土星軌道投入)という重要な局面に差し掛かっています。SOI のための噴射は日本時間のきょう 11:36 から 13:12 までの 96 分間の予定です。土星に接近する探査機はボイジャー 2 号以来 23 年ぶりということで、多くの成果が期待されています。

カッシー二探査機、いよいよ土星へ到着 (国立天文台 アストロ・トピックス (22)、6 月 30 日)

最新情報

Mission Status Center (Spaceflight Now、最新)→ @nifty 翻訳

軌道投入スケジュール(JST-EDT=13)

Cassini Saturn Orbit Insertion timeline (Spaceflight Now、6 月 29 日)

オフィシャル

Cassini-Huygens Home (NASA JPL)

このアーカイブについて

このページには、2004年7月に書かれた記事が新しい順に公開されています。

前のアーカイブは2004年6月です。

次のアーカイブは2004年8月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ

ウェブページ

Powered by Movable Type 6.3.3