ecm - クラウド上のオンライン

プログラム：

NAME

ecm - ECM、P-1 または P+1 を使用した整数因数分解

SYNOPSIS

Ecm [オプション] B1 [B2分-B2max | B2]

DESCRIPTION

ecm は、楕円曲線法 (ECM)、P-1 法、
またはP+1法。 次のセクションでは、これらに関連するパラメータについて説明します。
アルゴリズム

STEP 1 そして STEP 2 バウンド パラメーター

B1
B1 ステップ 1 の境界です。 これは必須のパラメータです。 整数で与えることができます
形式 (3000000 など) または浮動小数点形式 (3000000.0 または 3e6) です。 の
可能な限り最大 B1 P-9007199254740996 の値は 1、ULONG_MAX または
ECM および P+9007199254740996 の場合は 1 (小さい方)。 すべての素数 2 <= p <= B1 　
ステップ1で処理されます。

B2
B2 ステップ 2 のバウンドです。 これはオプションです。省略した場合、デフォルト値は以下から計算されます。
B1これは最適に近いはずです。 好き B1、整数または次のいずれかで指定できます。
浮動小数点形式。 可能な最大値 B2 およそ9e23ですが、
ブロックの数によって異なります k を指定すると -k オプション。 すべての素数 B1 <= p <=
B2 ステップ 2 で処理されます。 B2 < B1の場合、ステップ 2 は実行されません。

B2分-B2max
あるいは、 B2分-B2max 形式、つまりすべての素数 B2分 <= p
<= B2max 処理する必要があります。 したがって、指定する B2 にのみ対応します B1-B2。 その価値
of B2分 & B2max 任意に大きくてもかまいませんが、その差は超えてはなりません
約 9e23 (ブロック数による) k.

ファクタリング METHOD

-pm1
デフォルトの方法 (ECM) の代わりに P-1 を実行します。

-pp1
デフォルトの方法 (ECM) の代わりに P+1 を実行します。

GROUP そして 初期 POINT パラメーター

-x0 x
[ECM、P-1、P+1] 使用 x (任意精度の整数または有理数) を初期点として使用します。 ために
例、 -x0 1/3 有効です。 与えられなかったら、 x ECM のシグマ値から生成されます。
または P-1 と P+1 についてはランダムです。

-シグマ s
【ECM】使用 s (任意精度の整数) をカーブジェネレータとして使用します。 省略した場合は、 s is
ランダムに生成されます。

-A a
【ECM】使用 a (任意精度の整数) をカーブパラメータとして使用します。 省略した場合は、
シグマ値から生成されます。

-行く ヴァル
[ECM、P-1、P+1] 初期点を で乗算します。 ヴァル、任意の有効な式を使用できます。
現在の入力のプレースホルダーとして特殊文字 N が含まれる可能性があります
番号。 例：

ecm -pp1 -go "N^2-1" 1e6 < 複合2000

STEP 2 パラメーター

-k k
[ECM、P-1、P+1] 実行 k ステップ 2 のブロック。 B2 値、増加 k
CPU 時間は増加しますが、ステップ 2 のメモリ使用量は減少します。

-ツリーファイル file
データの一部のテーブルをディスク ファイルに保存して、ディスクで占有されるメモリの量を削減します。
ステップ 2 では、ディスク I/O が犠牲になります。 データはファイルに書き込まれます file.1、 file.2など。
P+2 および P-1 の高速ステージ 1 では機能しません。

パワー n
[ECM、P-1] x^ を使用します。n Brent-Suyama の拡張 (パワー 1 ブレント・須山運動を無効にする
拡大）。 デフォルトの多項式は、メソッドと B2 に応じて選択されます。 P-1用
および P+1、高速ステージ 2 を無効にします。P-1 の場合、 n 均等でなければなりません。

-ディクソン n
[ECM、P-1] 使用度-n Brent-Suyama の拡張に対する Dickson の多項式。 P-1と
P+1、高速ステージ 2 を無効にします。 パワー, n P-1 については偶数である必要があります。

-最大メモリ n
せいぜい使用 n ステージ 2 ではメガバイトのメモリ。

-ntt, -no-ntt
多項式演算の数論変換コードを有効または無効にします。
ステージ 2. NTT では、dF は 2 のべき乗となるように選択され、次の数によって制限されます。
機械語に適合する適切な素数 (これは 32 ビットのみの制限です)
システム）。 -no-ntt バリアントはより多くのメモリを使用しますが、大容量メモリを使用すると NTT よりも高速になります。
数字を入力します。 デフォルトでは、NTT は P-1、P+1、およびサイズ番号の ECM に使用されます。
ほとんどの 30 の機械語。

出力

-q
静かモード。 見つかった因数分解は、因数とともに標準出力に出力されます。
空白で区切られ、入力数値ごとに XNUMX 行になります (因子が見つからなかった場合は、
入力された番号は単純にコピーされます)。

-v
詳細モード。 より多くの情報が印刷され、さらに多くの情報が印刷されます。 -v オプションを使用すると冗長性が増します。 と
XNUMXつ -v、使用される剰余乗算の種類、初期 x0 値、ステップ 2 パラメータ
ECM のさまざまなサイズの因子を見つけるための進行状況、予想される曲線と時間
が印刷されています。 と -v -v、ステップ 1 の終了時の ECM と残基の A 値、および
ステップ2が印刷されます。 もっと -v デバッグ用に内部データを出力します。

-タイムスタンプ
新しい ECM カーブまたは P+1 または P-1 実行が処理されるたびにタイムスタンプを印刷します。

モジュラー 算術 OPTIONS

モジュラー乗算にはいくつかのアルゴリズムが使用できます。 プログラムは、
各入力に最適なもの。 次のオプションを使用して、特定のメソッドを強制できます。

-mpzmod
GMP の mpz_mod 関数を使用します (大きな入力の場合は二次関数ですが、ある程度のオーバーヘッドが発生します)
小さいもの用）。

-モドマルン
モンゴメリの乗算 (二次バージョン) を使用します。 通常、小規模な場合に最適な方法
入力。

-redc
モンゴメリの乗算 (二次二次バージョン) を使用します。 理論的には最適
大きな入力。

-nobase2
特別なbase-2コードを無効にします(入力数値が大きな係数である場合に使用されます)。
2^n+1 または 2^n-1、を参照してください。 -v).

-base2 n
特殊な基数 2 コードを強制的に使用します。入力数値は 2^ で除算する必要があります。n+1 の場合 n > 0、または 2^|n| -1
if n <0。

FILE I / O

次のオプションを使用すると、ステップ 1 とステップ 2 を別々に実行できます。
異なるマシン、異なる時間、または異なるソフトウェア (特に George
Woltman の Prime95/mprime プログラムは、再開に適したステップ 1 の出力を生成できます。
GMP-ECM）。 また、ステップ 2 を複数の実行に分割することも便利です。 B2min-B2max
オプションを選択します。

-inp file
ファイルから入力を取得する file 標準入力からではなく。

-保存する file
ステップ 1 の結果を保存します file。 場合 file 存在する場合、エラーが発生します。 例: 実行する
ステップ1のみ B1ファイル「c1000000」内の合成数の =155 を保存します。
結果としてファイル「foo」が生成されるので、使用します

ecm -save foo 1e6 1 < c155

-保存 file
いいね -保存するただし、既存のファイルに追加されます。

-履歴書 file
からの残基を再開します file、次の場合は標準入力から読み取ります。 file は "-"。 例: に
上記のステップ 2 の計算に続いてステップ 1 を実行するには、次を使用します。

ecm -resume foo 1e6

-チェックポイント file
ステージ 1 の現在の剰余を定期的に書き込みます。 file。 停電の場合は、
など、計算は次のように続行できます。 -履歴書 オプションを選択します。

ecm -chkpnt foo -pm1 1e10 <largenumber.txt

ループ モード

「ループモード」（オプション） -c n) を使用すると、各入力数値に対して複数の曲線を実行できます。 の
次のオプションはその動作を制御します。

-c n
実行する n 各入力番号に対して実行されます (デフォルトは XNUMX)。 このオプションは主に次の場合に役立ちます。
P+1 (たとえば、 n=3) または ECM の場合、ここで n 予想される数に設定できます
曲線を使用して、指定されたステップ 1 の範囲で d 桁の係数を見つけます。 このオプションは互換性がありません
　 -履歴書、 -シグマ、 -x0。 贈る -c 0 係数が次の値になるまで無限ループが生成されます。
発見した。

-1
ループモードでは、要因が見つかったときに停止します。 デフォルトでは、
余因子が素数であるか、指定された回数の実行が行われます。

-b
幅優先処理: ループ モードでは、入力数値ごとに XNUMX つのカーブを実行し、次に
それぞれに XNUMX 番目のカーブなど。 これはデフォルトのモードです。 -inp.

-d
深さ優先処理: ループモードで実行 n 最初の数値の曲線、その後 n 曲線
XNUMX番目以降も同様です。 これは標準入力を使用するデフォルトのモードです。

-ve n
ループ モードの場合、XNUMX 回目以降の実行では、at を持つ式のみを出力します。
最も n 文字。 デフォルトは -ve 0.

-i n
ループモードではインクリメントします B1 by n 各カーブの後。

-I n
ループモードでは乗算します B1 に応じた係数で n 各カーブの後。 デフォルトは XNUMX つです
これは XNUMX つのマシン上で最適であるはずですが、 -I 10 しようとするときに使用できます
10 台の同一マシン上で同時に同じ数値を因数分解します。

SHELL COMMAND 実行

これらのオプチンにより、GMP-ECM の機能を補足するシェル コマンドを実行できます。

-prpcmd CMD
コマンドを実行する CMD GMP-ECM の代わりに因子と余因子の素数性をテストする
独自の機能。 テストする数値は標準入力経由で渡されます。 終了コード 0 は、
「おそらく素数」として解釈され、ゼロ以外の終了コードは「複合」として解釈されます。

-faccmd CMD
コマンドを実行します CMD P-1、P+1、または ECM によって因子が見つかるたびに。 入力された番号、
因子と余因子は標準入力を介してそれぞれ XNUMX 行で渡されます。 これは次のように使用できます。
新しい要素を自動的にメールで送信します。

ecm -faccmd 'mail -s “$HOSTNAME が要因を見つけました”
[メール保護]' 11e6 < カニンガム.in

-idlecmd CMD
コマンドを実行します CMD 各 ECM 曲線の前に、数値に対する P-1 または P+1 の試行が開始されます。
終了ステータスが CMD ゼロ以外の場合、GMP-ECM は直ちに終了します。それ以外の場合は、
通常通り継続します。 GMP-ECM が停止している間、 CMD 実行し、
たとえば、システムがビジー状態である間、GMP-ECM はスリープします。

雑則

-n
プログラムを「nice」モード (通常の優先度よりも低い) で実行します。

-nn
プログラムを「非常に良い」モード (アイドル優先) で実行します。

-B2スケール f
デフォルトのステップ 2 の範囲を乗算します B2 浮動小数点値による f。 例： -B2スケール
0.5 デフォルトを分割します B2 2によります。

・ステージ1回 n
Add n ステージ1まであと数秒。 これは、正確な予想時間を取得するのに役立ちます。 -v if
ステージ 1 の一部は別の実行で実行されました。

-cofdec
(式が使用されている場合でも) XNUMX 進数での余因子出力を強制します。

-h, - 助けて
ecm の使用法、パラメータ、コマンド ライン オプションの簡単な説明を表示します。

-printconfig
コンパイルに使用された構成パラメータを出力して終了します。

入力 構文

入力数値にはいくつかの形式があります。

123456789 のような生の XNUMX 進数。

ファイルにはコメントを入れることができます。「//」以降は、最後まですべて無視されます。
ライン。

ラインの続き。 行がバックスラッシュ文字「\」で終わる場合、それは次のようにみなされます。
次の行に続けます。

一般的な算術式を使用できます。 例： 3*5+2^10.

階乗: 例 53！.

多因子: 例 15！3 means 15*12*9*6*3.

原始的な例 11＃ means 2*3*5*7*11.

縮約原数: 例 17 5＃ means 5*7*11*13*17.

関数: 現在、利用可能な関数は次のとおりです。 ファイ(x,n).

EXIT ステータス

終了ステータスは、最後の ECM カーブまたはプログラムの P-1/P+1 試行の結果を反映します。
実行されました。 個々のビットは、具体的には次のような特定のイベントを示します。

ビット0
プログラムが正常に終了した場合は 0、エラーが発生した場合は 1

ビット1
適切な係数が見つからなかった場合は 0、それ以外の場合は 1

ビット2
因子が合成の場合は 0、因子が確率素数の場合は 1

ビット3
余因子が合成の場合は 0、余因子が確率素数の場合は 1

したがって、次の終了ステータス値が発生する可能性があります。

0
プログラムは正常終了、要因は見つかりませんでした

1
エラー

2
複合因子が見つかりました、補因子は複合です

6
おそらく素因数が見つかりました、補因子は複合です

8
入力番号が見つかりました

10
複合因子が見つかりました。補因子は素数である可能性があります

14
推定素因数が見つかりました。補因子は推定素数です

onworks.net サービスを使用してオンラインで ecm を使用する