ecm - Dalam talian di Awan

JADUAL:

NAMA

ecm - pemfaktoran integer menggunakan ECM, P-1 atau P+1

SINOPSIS

ecm [pilihan] B1 [B2min-B2max | B2]

DESCRIPTION

ecm ialah program pemfaktoran integer menggunakan Kaedah Lengkung Eliptik (ECM), kaedah P-1,
atau kaedah P+1. Bahagian berikut menerangkan parameter yang berkaitan dengan ini
algoritma.

LANGKAH 1 DAN LANGKAH 2 TERIKAT PARAMETER

B1
B1 adalah langkah 1 terikat. Ia adalah parameter wajib. Ia boleh diberikan sama ada dalam integer
format (contohnya 3000000) atau dalam format titik terapung (3000000.0 atau 3e6). The
terbesar mungkin B1 nilai ialah 9007199254740996 untuk P-1 dan ULONG_MAX atau
9007199254740996 (yang mana lebih kecil) untuk ECM dan P+1. Semua nombor perdana 2 <= p <= B1 adalah
diproses dalam langkah 1.

B2
B2 adalah langkah 2 terikat. Ia adalah pilihan: jika ditinggalkan, nilai lalai dikira daripada
B1, yang sepatutnya hampir optimum. Suka B1, ia boleh diberikan sama ada dalam integer atau in
format titik terapung. Nilai terbesar yang mungkin bagi B2 adalah lebih kurang 9e23, tetapi
bergantung kepada bilangan blok k jika anda nyatakan -k pilihan. Semua bilangan prima B1 <= p <=
B2 diproses dalam langkah 2. Jika B2 < B1, tiada langkah 2 dilakukan.

B2min-B2max
sebagai alternatif seseorang boleh menggunakan B2min-B2max bentuk, yang bermaksud bahawa semua nombor perdana B2min <= hlm
<= B2max harus diproses. Dengan itu menyatakan B2 hanya sepadan dengan B1-B2. Nilai-nilai
of B2min and B2max mungkin besar sewenang-wenangnya, tetapi perbezaannya tidak boleh melebihi
kira-kira 9e23, tertakluk kepada bilangan blok k.

PEMfaktoran KAEDAH

-pm1
Lakukan P-1 dan bukannya kaedah lalai (ECM).

-pp1
Lakukan P+1 dan bukannya kaedah lalai (ECM).

KUMPULAN DAN Awal TITIK PARAMETER

-x0 x
[ECM, P-1, P+1] Gunakan x (integer ketepatan-arbitrari atau rasional) sebagai titik awal. Untuk
contohnya, -x0 1/3 ianya sah. Jika tidak diberi, x dijana daripada nilai sigma untuk ECM,
atau secara rawak untuk P-1 dan P+1.

-sigma s
[ECM] Gunakan s (integer ketepatan arbitrari) sebagai penjana lengkung. Jika ditinggalkan, s is
dijana secara rawak.

-A a
[ECM] Gunakan a (integer ketepatan arbitrari) sebagai parameter lengkung. Jika ditinggalkan, adakah ia
dihasilkan daripada nilai sigma.

-pergi val
[ECM, P-1, P+1] Darab titik awal dengan val, yang boleh mana-mana ungkapan yang sah,
mungkin mengandungi aksara khas N sebagai pemegang tempat untuk input semasa
nombor. Contoh:

ecm -pp1 -go "N^2-1" 1e6 < composite2000

LANGKAH 2 PARAMETER

-k k
[ECM, P-1, P+1] Laksanakan k blok dalam langkah 2. Untuk yang diberikan B2 nilai, meningkat k
mengurangkan penggunaan memori pada langkah 2, dengan mengorbankan lebih banyak masa cpu.

-fail pokok fail
Menyimpan beberapa jadual data dalam fail cakera untuk mengurangkan jumlah memori yang diduduki
langkah 2, dengan mengorbankan cakera I/O. Data akan ditulis ke fail fail.1, fail.2 dll.
Tidak berfungsi dengan peringkat cepat 2 untuk P+1 dan P-1.

Kuasa n
[ECM, P-1] Gunakan x^n untuk sambungan Brent-Suyama (Kuasa 1 melumpuhkan Brent-Suyama
sambungan). Polinomial lalai dipilih bergantung pada kaedah dan B2. Untuk P-1
dan P+1, melumpuhkan peringkat pantas 2. Untuk P-1, n mesti sekata.

-dickson n
[ECM, P-1] Gunakan ijazah-n Polinomial Dickson untuk sambungan Brent-Suyama. Untuk P-1 dan
P+1, melumpuhkan peringkat pantas 2. Suka untuk Kuasa, n mestilah genap untuk P-1.

-maxmem n
Gunakan paling banyak n megabait memori dalam peringkat 2.

-ntt, -tidak-ntt
Dayakan atau lumpuhkan kod Transformasi Teori-Nombor untuk aritmetik polinomial dalam
peringkat 2. Dengan NTT, dF dipilih untuk menjadi kuasa 2, dan dihadkan oleh nombor
nombor perdana yang sesuai yang dimuatkan dalam perkataan mesin (yang merupakan had hanya pada 32 bit
sistem). Varian -no-ntt menggunakan lebih banyak memori, tetapi lebih pantas daripada NTT dengan besar
nombor input. Secara lalai, NTT digunakan untuk P-1, P+1 dan untuk ECM pada nombor saiz di
kebanyakan 30 perkataan mesin.

OUTPUT

-q
Mod senyap. Pemfaktoran yang ditemui dicetak pada output standard, dengan faktor
dipisahkan oleh ruang putih, satu baris setiap nombor input (jika tiada faktor ditemui,
nombor input hanya disalin).

-v
Mod bertele-tele. Lebih banyak maklumat dicetak, lebih banyak lagi -v pilihan meningkatkan verbositi. Dengan
1 -v, jenis pendaraban modular yang digunakan, nilai x0 awal, parameter langkah 2
dan kemajuan, dan jangkaan lengkung dan masa untuk mencari faktor saiz yang berbeza untuk ECM
dicetak. Dengan -v -v, nilai A untuk ECM dan sisa pada akhir langkah 1 dan
langkah 2 dicetak. Lagi -v mencetak data dalaman untuk penyahpepijatan.

-cap masa
Cetak cap masa setiap kali lengkung ECM baharu atau larian P+1 atau P-1 diproses.

MODULAR ARITMETIK PILIHAN

Beberapa algoritma tersedia untuk pendaraban modular. Program ini cuba mencari
yang terbaik untuk setiap input; seseorang boleh memaksa kaedah yang diberikan dengan pilihan berikut.

-mpzmod
Gunakan fungsi mpz_mod GMP (sub-kuadrat untuk input besar, tetapi mendorong beberapa overhed
untuk yang kecil).

-modmuln
Gunakan pendaraban Montgomery (versi kuadratik). Biasanya kaedah terbaik untuk kecil
input.

-redc
Gunakan pendaraban Montgomery (versi sub-kuadrat). Secara teorinya optimum untuk
input yang besar.

-nobase2
Lumpuhkan kod asas-2 khas (yang digunakan apabila nombor input adalah faktor besar bagi
2^n+1 atau 2^n-1, lihat -v).

-asas2 n
Paksa menggunakan kod asas-2 khas, nombor input mesti membahagi 2^n+1 jika n > 0, atau 2^|n|-1
if n <0.

FAIL I / O

Pilihan berikut membolehkan seseorang melakukan langkah 1 dan langkah 2 secara berasingan, sama ada pada
mesin yang berbeza, pada masa yang berbeza, atau menggunakan perisian yang berbeza (khususnya, George
Program Prime95/mprime Woltman boleh menghasilkan output langkah 1 yang sesuai untuk menyambung semula dengan
GMP-ECM). Ia juga berguna untuk membahagikan langkah 2 kepada beberapa larian, menggunakan B2min-B2maks
pilihan.

-dalam p fail
Ambil input daripada fail fail bukannya daripada input standard.

-jimat fail
Simpan hasil langkah 1 dalam fail. Jika fail wujud, ralat ditimbulkan. Contoh: untuk melaksanakan
hanya langkah 1 dengan B1=1000000 pada nombor komposit dalam fail "c155" dan simpan nombor itu
mengakibatkan fail "foo", gunakan

ecm -save foo 1e6 1 < c155

-savea fail
suka -jimat, tetapi ditambah pada fail sedia ada.

-sambung semula fail
Sambung semula sisa daripada fail, dibaca daripada input standard jika fail ialah "-". Contoh: kepada
lakukan langkah 2 mengikut pengiraan langkah 1 di atas, gunakan

ecm -resume foo 1e6

-chkpoint fail
Tulis baki semasa secara berkala dalam peringkat 1 hingga fail. Sekiranya berlaku kegagalan kuasa,
dll., pengiraan boleh diteruskan dengan -sambung semula pilihan.

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

LOOP MODE

"Mod gelung" (pilihan -c n) membolehkan seseorang menjalankan beberapa lengkung pada setiap nombor input. The
pilihan berikut mengawal tingkah lakunya.

-c n
Melaksanakan n berjalan pada setiap nombor input (lalai ialah satu). Pilihan ini berguna terutamanya untuk
P+1 (contohnya dengan n=3) atau untuk ECM, di mana n boleh ditetapkan kepada bilangan yang dijangkakan
lengkung untuk mencari faktor d-digit dengan langkah 1 terikat. Pilihan ini tidak serasi
bersama -sambung semula, -sigma, -x0. Memberi -c 0 menghasilkan gelung tak terhingga sehingga faktor adalah
dijumpai.

-satu
Dalam mod gelung, berhenti apabila faktor ditemui; lalai adalah untuk meneruskan sehingga
cofactor ialah perdana atau bilangan larian yang ditentukan telah dilakukan.

-b
Pemprosesan luas pertama: dalam mod gelung, jalankan satu lengkung untuk setiap nombor input, kemudian a
lengkung kedua untuk setiap satu, dan seterusnya. Ini ialah mod lalai dengan -dalam p.

-d
Pemprosesan mendalam-pertama: dalam mod gelung, jalankan n lengkung untuk nombor pertama, kemudian n keluk
untuk yang kedua dan seterusnya. Ini ialah mod lalai dengan input standard.

-ve n
Dalam mod gelung, dalam larian kedua dan seterusnya, keluarkan hanya ungkapan yang mempunyai at
yang paling n watak. Lalai ialah -ve 0.

-i n
Dalam mod gelung, kenaikan B1 by n selepas setiap lengkung.

-I n
Dalam mod gelung, darab B1 oleh faktor bergantung kepada n selepas setiap lengkung. Lalai ialah satu
yang sepatutnya optimum pada satu mesin, manakala -I 10 boleh digunakan apabila cuba
faktorkan nombor yang sama serentak pada 10 mesin yang serupa.

SHELL COMMAND PERLAKSANAAN

Optin ini membenarkan untuk melaksanakan perintah shell untuk menambah fungsi kepada GMP-ECM.

-prpcmd cmd
Laksanakan arahan cmd untuk menguji keutamaan jika faktor dan kofaktor dan bukannya GMP-ECM
fungsi sendiri. Nombor untuk diuji diluluskan melalui stdin. Kod keluar 0 ialah
ditafsirkan sebagai "mungkin perdana", kod keluar bukan sifar sebagai "komposit".

-faccmd cmd
Melaksanakan arahan cmd apabila sesuatu faktor ditemui oleh P-1, P+1 atau ECM. Nombor input,
faktor dan kofaktor dihantar melalui stdin, setiap satu pada satu baris. Ini boleh digunakan iaitu untuk
hantar faktor baharu secara automatik:

ecm -faccmd 'mail -s “$HOSTNAME menemui faktor”
[e-mel dilindungi]' 11e6 < cunningham.in

-idlecmd cmd
Melaksanakan arahan cmd sebelum setiap lengkung ECM, percubaan P-1 atau P+1 pada nombor dimulakan.
Jika status keluar daripada cmd bukan sifar, GMP-ECM ditamatkan serta-merta, jika tidak
berterusan seperti biasa. GMP-ECM dihentikan sementara cmd berjalan, menawarkan cara untuk membiarkan
GMP-ECM tidur contohnya semasa sistem sibuk.

PELBAGAI

-n
Jalankan program dalam mod "bagus" (di bawah keutamaan biasa).

-nn
Jalankan program dalam mod "sangat bagus" (keutamaan terbiar).

-Skala B2 f
Darab langkah lalai 2 terikat B2 dengan nilai titik terapung f. Contoh: -Skala B2
0.5 membahagikan lalai B2 oleh 2.

-peringkat1masa n
Tambah n saat ke peringkat 1 masa. Ini berguna untuk mendapatkan masa yang dijangkakan dengan betul -v if
sebahagian daripada peringkat 1 telah dilakukan dalam larian yang lain.

-cofdec
Paksa keluaran kofaktor dalam perpuluhan (walaupun ungkapan digunakan).

-h, - membantu
Paparkan penerangan ringkas tentang penggunaan ecm, parameter dan pilihan baris arahan.

-printconfig
Mencetak parameter konfigurasi yang digunakan untuk penyusunan dan keluar.

INPUT SISTEM

Nombor input boleh mempunyai beberapa bentuk:

Nombor perpuluhan mentah seperti 123456789.

Komen boleh diletakkan dalam fail: segala-galanya selepas "//" diabaikan, sehingga penghujung
line.

Sambungan talian. Jika baris berakhir dengan aksara sengkang ke belakang "\", ia dianggap sebagai
teruskan pada baris seterusnya.

Ungkapan aritmetik biasa boleh digunakan. Contoh: 3*5+2^10.

Faktorial: contoh 53!.

Pelbagai faktor: contoh 15! 3 means 15*12*9*6*3.

Primorial: contoh 11 # means 2*3*5*7*11.

Primorial dikurangkan: contoh 17 # 5 means 5*7*11*13*17.

Fungsi: pada masa ini, satu-satunya fungsi yang tersedia ialah Phi(x,n).

EXIT STATUS

Status keluar mencerminkan hasil keluk ECM terakhir atau percubaan P-1/P+1 program
dilakukan. Bit individu menandakan peristiwa tertentu, khususnya:

Bit 0
0 jika penamatan program biasa, 1 jika ralat berlaku

Bit 1
0 jika tiada faktor wajar ditemui, 1 sebaliknya

Bit 2
0 jika faktor adalah komposit, 1 jika faktor ialah perdana berkemungkinan

Bit 3
0 jika kofaktor adalah komposit, 1 jika kofaktor ialah perdana berkemungkinan

Oleh itu, nilai status keluar berikut mungkin berlaku:

0
Penamatan program biasa, tiada faktor ditemui

1
ralat

2
Faktor komposit ditemui, kofaktor adalah komposit

6
Kemungkinan faktor perdana ditemui, kofaktor adalah komposit

8
Nombor input ditemui

10
Faktor komposit ditemui, kofaktor ialah perdana berkemungkinan

14
Faktor perdana berkemungkinan ditemui, kofaktor ialah perdana berkemungkinan

Gunakan ecm dalam talian menggunakan perkhidmatan onworks.net