ecm - Online di Cloud

PROGRAM:

NAMA

ecm - faktorisasi bilangan bulat menggunakan ECM, P-1 atau P+1

RINGKASAN

ECM [Pilihan] B1 [B2 menit-B2maks | B2]

DESKRIPSI

ecm adalah program pemfaktoran bilangan bulat menggunakan Elliptic Curve Method (ECM), metode P-1,
atau metode P+1. Bagian berikut menjelaskan parameter yang relevan dengan ini:
algoritma.

LANGKAH 1 DAN LANGKAH 2 MELOMPAT PARAMETER

B1
B1 adalah langkah 1 terikat. Ini adalah parameter wajib. Itu dapat diberikan baik dalam bilangan bulat
format (misalnya 3000000) atau dalam format floating-point (3000000.0 atau 3e6). NS
terbesar mungkin B1 nilainya adalah 9007199254740996 untuk P-1, dan ULONG_MAX atau
9007199254740996 (mana yang lebih kecil) untuk ECM dan P+1. Semua bilangan prima 2 <= p <= B1 adalah
diproses pada langkah 1.

B2
B2 adalah langkah 2 terikat. Ini opsional: jika dihilangkan, nilai default dihitung dari
B1, yang harus mendekati optimal. Suka B1, dapat diberikan dalam bilangan bulat atau dalam
format titik-mengambang. Nilai terbesar yang mungkin dari B2 kira-kira 9e23, tapi
tergantung pada jumlah blok k jika Anda menentukan -k pilihan. Semua bilangan prima B1 <= p <=
B2 diproses pada langkah 2. Jika B2 < B1, tidak ada langkah 2 yang dilakukan.

B2 menit-B2maks
sebagai alternatif, seseorang dapat menggunakan B2 menit-B2maks bentuk, yang berarti bahwa semua bilangan prima B2 menit <= p
<= B2maks harus diproses. Dengan demikian menentukan B2 hanya sesuai dengan B1-B2. Nilai
of B2 menit dan B2maks mungkin besar secara sewenang-wenang, tetapi perbedaannya tidak boleh melebihi
sekitar 9e23, tergantung pada jumlah blok k.

FAKTOR METODE

-pm1
Lakukan P-1 sebagai ganti metode default (ECM).

-pp1
Lakukan P+1 alih-alih metode default (ECM).

GROUP DAN AWAL POINT PARAMETER

-x0 x
[ECM, P-1, P+1] Gunakan x (bilangan bulat presisi arbitrer atau rasional) sebagai titik awal. Untuk
contoh, -x0 1/3 adalah benar. Jika tidak diberikan, x dihasilkan dari nilai sigma untuk ECM,
atau secara acak untuk P-1 dan P+1.

-sigma s
[ECM] Gunakan s (integer presisi sewenang-wenang) sebagai generator kurva. Jika dihilangkan, s is
dihasilkan secara acak.

-A a
[ECM] Gunakan a (integer presisi arbitrer) sebagai parameter kurva. Jika dihilangkan, apakah itu?
dihasilkan dari nilai sigma.

-Pergilah val
[ECM, P-1, P+1] Kalikan titik awal dengan val, yang dapat setiap ekspresi yang valid,
mungkin berisi karakter khusus N sebagai tempat untuk input saat ini
nomor. Contoh:

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

LANGKAH 2 PARAMETER

-k k
[ECM, P-1, P+1] Lakukan k blok pada langkah 2. Untuk diberikan B2 nilai, meningkat k
mengurangi penggunaan memori langkah 2, dengan mengorbankan lebih banyak waktu cpu.

-file pohon fillet
Menyimpan beberapa tabel data dalam file disk untuk mengurangi jumlah memori yang digunakan
langkah 2, dengan mengorbankan disk I/O. Data akan ditulis ke file fillet.1, fillet.2 dll.
Tidak bekerja dengan tahap 2 cepat untuk P+1 dan P-1.

-Listrik n
[ECM, P-1] Gunakan x^n untuk perpanjangan Brent-Suyama (-Listrik 1 menonaktifkan Brent-Suyama
perpanjangan). Polinomial default dipilih tergantung pada metode dan B2. Untuk P-1
dan P+1, menonaktifkan tahap cepat 2. Untuk P-1, n harus genap.

-dikson n
[ECM, P-1] Gunakan derajat-n Polinomial Dickson untuk ekstensi Brent-Suyama. Untuk P-1 dan
P+1, menonaktifkan tahap cepat 2. Sukai -Listrik, n harus genap untuk P-1.

-maksimal n
Gunakan paling banyak n megabyte memori di tahap 2.

-tidak, -tidak-ntt
Mengaktifkan atau menonaktifkan kode Transformasi Teori-Nomor untuk aritmatika polinomial dalam
tahap 2. Dengan NTT, dF dipilih menjadi pangkat 2, dan dibatasi oleh angka
bilangan prima yang cocok yang sesuai dengan kata mesin (yang merupakan batasan hanya pada 32 bit
sistem). Varian -no-ntt menggunakan lebih banyak memori, tetapi lebih cepat daripada NTT dengan besar
angka masukan. Secara default, NTT digunakan untuk P-1, P+1 dan untuk ECM pada nomor ukuran di
paling banyak 30 kata mesin.

KELUARAN

-q
Modus tenang. Faktorisasi yang ditemukan dicetak pada keluaran standar, dengan faktor
dipisahkan oleh spasi putih, satu baris per nomor input (jika tidak ada faktor yang ditemukan,
nomor input hanya disalin).

-v
Modus verbose. Lebih banyak informasi dicetak, lebih banyak -v pilihan meningkatkan verbositas. Dengan
satu -v, jenis perkalian modular yang digunakan, nilai x0 awal, parameter langkah 2
dan kemajuan, dan kurva yang diharapkan dan waktu untuk menemukan faktor dengan ukuran berbeda untuk ECM
dicetak. Dengan -v -v, nilai A untuk ECM dan residu pada akhir langkah 1 dan
langkah 2 dicetak. Lagi -v mencetak data internal untuk debugging.

-cap waktu
Cetak stempel waktu setiap kali kurva ECM baru atau proses P+1 atau P-1 diproses.

MODULER HITUNG PILIHAN

Beberapa algoritma tersedia untuk perkalian modular. Program mencoba untuk menemukan
yang terbaik untuk setiap input; seseorang dapat memaksa metode yang diberikan dengan opsi berikut.

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

-modmuln
Gunakan perkalian Montgomery (versi kuadrat). Biasanya metode terbaik untuk yang kecil
memasukkan.

-merah
Gunakan perkalian Montgomery (versi sub-kuadrat). Secara teoritis optimal untuk
masukan besar.

-nobase2
Nonaktifkan kode basis-2 khusus (yang digunakan ketika nomor input merupakan faktor besar dari
2^n+1 atau 2^n-1, lihat -v).

-basis2 n
Paksa penggunaan kode basis-2 khusus, nomor input harus dibagi 2^n+1 jika n > 0, atau 2^|n|-1
if n <0.

FILE I / O

Opsi berikut memungkinkan seseorang untuk melakukan langkah 1 dan langkah 2 secara terpisah, baik di
mesin yang berbeda, pada waktu yang berbeda, atau menggunakan perangkat lunak yang berbeda (khususnya, George
Program Prime95/mprime Woltman dapat menghasilkan output langkah 1 yang cocok untuk dilanjutkan dengan
GMP-ECM). Ini juga berguna untuk membagi langkah 2 menjadi beberapa proses, dengan menggunakan B2min-B2maks
.

-masuk fillet
Ambil masukan dari file fillet bukan dari input standar.

-menyimpan fillet
Simpan hasil langkah 1 di fillet. Jika fillet ada, kesalahan dimunculkan. Contoh: untuk melakukan
hanya langkah 1 dengan B1=1000000 pada nomor komposit dalam file "c155" dan simpan
menghasilkan file "foo", gunakan

ecm -simpan foo 1e6 1 < c155

-selamatkan fillet
Seperti -menyimpan, tetapi menambahkan ke file yang ada.

-lanjut fillet
Lanjutkan residu dari fillet, membaca dari input standar jika fillet adalah "-". Contoh: ke
lakukan langkah 2 mengikuti perhitungan langkah 1 di atas, gunakan

ecm -lanjutkan foo 1e6

-chkpoint fillet
Secara berkala tulis residu saat ini di tahap 1 ke fillet. Dalam kasus kegagalan daya,
dll., perhitungan dapat dilanjutkan dengan -lanjut .

ecm -chkpnt foo -pm1 1e10 < angka besar.txt

LOOP MODE

"Mode loop" (opsi -c n) memungkinkan seseorang untuk menjalankan beberapa kurva pada setiap nomor input. NS
pilihan berikut mengontrol perilakunya.

-c n
Melakukan n berjalan pada setiap nomor input (default adalah satu). Opsi ini terutama berguna untuk
P+1 (misalnya dengan n=3) atau untuk ECM, di mana n dapat diatur ke jumlah yang diharapkan dari
kurva untuk menemukan faktor d-digit dengan langkah 1 yang diberikan terikat. Opsi ini tidak kompatibel
dengan -melanjutkan, -sigma, -x0. Memberi -c 0 menghasilkan loop tak terbatas sampai faktor adalah
ditemukan.

-satu
Dalam mode loop, berhenti ketika faktor ditemukan; defaultnya adalah melanjutkan sampai
kofaktor adalah prima atau jumlah run yang ditentukan selesai.

-b
Pemrosesan luas-pertama: dalam mode loop, jalankan satu kurva untuk setiap nomor input, lalu a
kurva kedua untuk masing-masing, dan seterusnya. Ini adalah mode default dengan -masuk.

-d
Pemrosesan mendalam-pertama: dalam mode loop, jalankan n kurva untuk angka pertama, maka n kurva
untuk yang kedua dan seterusnya. Ini adalah mode default dengan input standar.

-ve n
Dalam mode loop, pada run kedua dan berikutnya, hanya keluaran ekspresi yang memiliki at
paling n karakter. Standarnya adalah -ve 0.

-i n
Dalam mode loop, kenaikan B1 by n setelah setiap kurva.

-I n
Dalam mode loop, kalikan B1 oleh faktor tergantung pada n setelah setiap kurva. Standarnya adalah satu
yang seharusnya optimal pada satu mesin, sedangkan -I 10 dapat digunakan saat mencoba
faktorkan angka yang sama secara bersamaan pada 10 mesin yang identik.

SHELL COMMAND EKSEKUSI

Optin ini memungkinkan eksekusi perintah shell untuk melengkapi fungsionalitas ke GMP-ECM.

-prpcmd cmd
Jalankan perintah cmd untuk menguji primality jika faktor dan kofaktor bukan GMP-ECM's
fungsi sendiri. Nomor yang akan diuji dilewatkan melalui stdin. Kode keluar 0 adalah
ditafsirkan sebagai "mungkin prima", kode keluar bukan nol sebagai "komposit".

-faccmd cmd
Menjalankan perintah cmd setiap kali faktor ditemukan oleh P-1, P+1 atau ECM. Nomor masukan,
faktor dan kofaktor dilewatkan melalui stdin, masing-masing pada satu baris. Ini bisa digunakan yaitu untuk
mengirimkan faktor baru secara otomatis:

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

-cmd menganggur cmd
Menjalankan perintah cmd sebelum setiap kurva ECM, percobaan P-1 atau P+1 pada sebuah angka dimulai.
Jika status keluar dari cmd bukan nol, GMP-ECM segera berakhir, jika tidak maka
berlanjut secara normal. GMP-ECM dihentikan saat cmd berlari, menawarkan cara untuk membiarkan
GMP-ECM tidur misalnya saat sistem sedang sibuk.

LAIN-LAIN

-n
Jalankan program dalam mode "bagus" (di bawah prioritas normal).

-nn
Jalankan program dalam mode "sangat bagus" (prioritas menganggur).

-skala B2 f
Kalikan langkah default 2 terikat B2 dengan nilai floating-point f. Contoh: -skala B2
0.5 membagi default B2 oleh 2.

-tahap1waktu n
Add n detik ke tahap 1 kali. Ini berguna untuk mendapatkan waktu yang diharapkan dengan benar dengan -v if
bagian dari tahap 1 dilakukan di run lain.

-cofdec
Paksa keluaran kofaktor dalam desimal (bahkan jika ekspresi digunakan).

-h, --membantu
Tampilkan deskripsi singkat tentang penggunaan ecm, parameter, dan opsi baris perintah.

-cetakkonfigurasi
Mencetak parameter konfigurasi yang digunakan untuk kompilasi dan keluar.

INPUT SINTAKSIS

Nomor input dapat memiliki beberapa bentuk:

Angka desimal mentah seperti 123456789.

Komentar dapat ditempatkan di file: semuanya setelah "//" diabaikan, hingga akhir
line.

Kelanjutan baris. Jika garis diakhiri dengan karakter garis miring terbalik “\”, itu dianggap
lanjutkan ke baris berikutnya.

Ekspresi aritmatika umum dapat digunakan. Contoh: 3*5+2^10.

Faktorial: contoh 53!.

Multi-faktorial: contoh 15! 3 means 15*12*9*6*3.

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

Dikurangi primorial: contoh 17 # 5 means 5*7*11*13*17.

Fungsi: saat ini, satu-satunya fungsi yang tersedia adalah Phi(x,n).

EXIT STATUS

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

Sedikit 0
0 jika penghentian program normal, 1 jika terjadi kesalahan

Sedikit 1
0 jika tidak ada faktor yang tepat ditemukan, 1 sebaliknya

Sedikit 2
0 jika faktornya komposit, 1 jika faktornya kemungkinan prima

Sedikit 3
0 jika kofaktor adalah komposit, 1 jika kofaktor adalah kemungkinan prima

Dengan demikian, nilai status keluar berikut dapat terjadi:

0
Penghentian program normal, tidak ada faktor yang ditemukan

1
error

2
Faktor komposit ditemukan, kofaktor adalah komposit

6
Faktor prima yang mungkin ditemukan, kofaktor adalah komposit

8
Nomor masukan ditemukan

10
Faktor komposit ditemukan, kofaktor adalah kemungkinan prima

14
Faktor prima yang mungkin ditemukan, kofaktor adalah kemungkinan prima

Gunakan ecm online menggunakan layanan onworks.net