素因数分解の最近の記事

R271 陥落

| コメント(0)

素因数分解されていないレピュニットの中でこれまで最小だった R271 の残り 214 桁の合成数が、94 桁の素数と 121 桁の素数の積に分解されました。

多項式選択に 20 CPU 年、篩に 1,500 CPU 年、線形代数に 155 CPU 年かかったらしい。よい多項式を引き当てる運と、よいパラメータを決める経験と、特に線形代数のステップを実装する技術と、たくさんの計算機を長期間に渡って動員する力 (実績とかお金とか権力とか) がないときっと無理。

ECM の世界記録

| コメント(0)

先日、"7" の後ろに "1" が 341 個並んだ数 (64·10341-1)/9 の残りの 296 桁の合成数 から ECM で 68 桁の素因数が見つかり、50 largest factors found by ECM のトップが 3 年ぶりに更新されました。発見したのは分散コンピューティングプロジェクトの yoyo@home に参加している Lazarus-uk さん です。Factorizations of near-repdigit-related numbers で扱っている数 (レピュニットを除く) から ECM の世界記録が出たのは 2003 年に Robert Backstrom さんが発見した 58 桁の素因数以来 6 年ぶりです。

a^2+b^2 の因数分解

| コメント(0)

「a2+b2 は因数分解できるわけがないから a2-b2 の間違いだろう」と思った人は頭をモミモミして柔らかくしましょうね。a2+b2 だってちゃんと分解できるんですよ。

a2+b2=(a-√2ab+b)(a+√2ab+b)

ほらできた。

・・・はいそこ、ズルイとか言わない。

この分解の仕組みを知っていると、例えば 2501, 25000001, 250000000001,… のように 25 と 1 の間に 0 を 4n+1 個挟んだ数は決して素数にならないことがすぐにわかります。

25·104n+2+1=(5·102n+1)2+12
-=(5·102n+1+1)2-2·5·102n+1·1
-=(5·102n+1+1)2-10·102n+1
-=(5·102n+1+1)2-102n+2
-=(5·102n+1+1)2-(10n+1)2
-=(5·102n+1+1-10n+1)(5·102n+1+1+10n+1)
-=(5·102n+1-10n+1+1)(5·102n+1+10n+1+1)

題意から n は 0 以上の整数ですから 5·102n+1±10n+1+1 は 1 よりも大きい整数です。25·104n+2+1 は少なくとも 2 つの素因数を持つことになるので素数にはなりません。

10^393+1 が素因数分解された

| コメント(0)

Serge Batalov さんと Bruce Dodson さんが Jason Papadopoulos さんのプログラムを利用して 10393+1 の残り 253 桁の合成数を 119 桁の素数と 134 桁の素数の積に分解することに成功しました。

2009 年 1 月 11 日 (日)

| コメント(0)

素因数分解のページ人工衛星のページの更新プログラムが新しい PC に移行しました。風雲 1 号 C のデブリの表示が復活しました。

2009 年 1 月 5 日 (月)

| コメント(0)

あけましておめでとうございます。マザーボードが壊れてしまったメインの PC の復旧は諦めて、新しい機械が届くまで動作が不安定な古い PC (Pentium 3, Windows 98 SE) でしのいでいます。今日、素因数分解のページを更新しました。常連さんの多くが外国の方なので英語で書いてありますが、それぞれの合成数に対応した投稿と予約のページは「Japanese」と書かれたボタンをクリックすると日本語表示になります。興味のある方はウォンテッドリストからおひとつどうぞ。

素因数分解

| コメント(0)

素因数分解表の投稿と予約のページを更新しました。変更箇所は分解方法の説明と所要時間の目安、多項式の生成アルゴリズム、SNFS 法のパラメータ、ECM の残りの回数の計算方法などです。

Msieve 1.38

| コメント(0)

Jason Papadopoulos さんによる素因数分解プログラム Msieve のバージョン 1.38 が公開されました。「make x86 ECM=1」(64 ビット環境のときは「make x86_64 ECM=1」) で make して「./msieve -e -p -q -v " 分解したい数を表す式 "」でサクサク分解できます。-e は ECM 強化、-p は優先度を下げる、-q はログファイル出力なし、-v はログを画面に出力。デフォルトは 2 次ふるい法ですが大きい数のとき -n をつけると NFS 法になります。

使用例
~/msieve-1.38> ./msieve -e -p -q -v "10^63-9"


Msieve v. 1.38
Thu Sep 25 23:16:51 2008
random seeds: 998761c2 82edcf23
factoring 999999999999999999999999999999999999999999999999999999999999991 (63 digits)
searching for 15-digit factors
commencing quadratic sieve (63-digit input)
using multiplier of 1
using 64kb Pentium 4 sieve core
sieve interval: 6 blocks of size 65536
processing polynomials in batches of 17
using a sieve bound of 105107 (5000 primes)
using large prime bound of 5255350 (22 bits)
using trial factoring cutoff of 22 bits
polynomial 'A' values have 8 factors

sieving in progress (press Ctrl-C to pause)
5179 relations (2292 full + 2887 combined from 24324 partial), need 5096
5179 relations (2292 full + 2887 combined from 24324 partial), need 5096
sieving complete, commencing postprocessing
begin with 26616 relations
reduce to 7680 relations in 2 passes
attempting to read 7680 relations
recovered 7680 relations
recovered 5992 polynomials
attempting to build 5179 cycles
found 5179 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 2292
   length 2 : 2887
largest cycle: 2 relations
matrix is 5000 x 5179 (0.6 MB) with weight 142670 (27.55/col)
sparse part has weight 142670 (27.55/col)
filtering completed in 3 passes
matrix is 4677 x 4741 (0.6 MB) with weight 128749 (27.16/col)
sparse part has weight 128749 (27.16/col)
commencing Lanczos iteration
memory use: 0.8 MB
lanczos halted after 75 iterations (dim = 4674)
recovered 63 nontrivial dependencies
prp32 factor: 14499216344898896752959323769763
prp32 factor: 68969244696581083712684424134557
elapsed time 00:00:30

~/msieve-1.38> 

Aurifeuillian Factorization

| コメント(0)

レピュニットの素因数分解で使う円分数 Phi_n(10) の素因数分解表に出てくる L と M の分解。n = 20 の円分多項式は Phi_20(x) = x8 - x6 + x4 - x2 + 1 = (x4 + 5x3 + 7x2 + 5x + 1)2 - 10x (x3 + 2x2 + 2x + 1)2と書けるので、x = 10 のとき平方の差の形になって差と和の積に分解できる。x が大きくても作れるので調子に乗って 180 まで作ったのだけれど、次に 190 まで伸ばそうとしたら返ってこなくなった。なんでかなぁ。

このアーカイブについて

このページには、過去に書かれた記事のうち素因数分解カテゴリに属しているものが含まれています。

次のカテゴリは素数です。

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

月別 アーカイブ

ウェブページ

Powered by Movable Type 6.3.3