ecm - Online sa Cloud

PROGRAMA:

NAME

ecm - integer factorization gamit ang ECM, P-1 o P+1

SINOPSIS

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

DESCRIPTION

Ang ecm ay isang integer factoring program gamit ang Elliptic Curve Method (ECM), ang P-1 na paraan,
o ang P+1 na paraan. Ang mga sumusunod na seksyon ay naglalarawan ng mga parameter na nauugnay sa mga ito
algorithm.

HAKBANG 1 AT HAKBANG 2 BALIKAN MGA PARAMETERS

B1
B1 ay ang hakbang 1 nakatali. Ito ay isang ipinag-uutos na parameter. Maaari itong ibigay sa alinman sa integer
format (halimbawa 3000000) o sa floating-point na format (3000000.0 o 3e6). Ang
pinakamalaking posible B1 ang value ay 9007199254740996 para sa P-1, at ULONG_MAX o
9007199254740996 (alinman ang mas maliit) para sa ECM at P+1. Lahat ng prime 2 <= p <= B1 ay
naproseso sa hakbang 1.

B2
B2 ay ang hakbang 2 nakatali. Ito ay opsyonal: kung aalisin, ang isang default na halaga ay kinukuwenta mula sa
B1, na dapat ay malapit sa pinakamainam. Gusto B1, maaari itong ibigay alinman sa integer o in
floating-point na format. Ang pinakamalaking posibleng halaga ng B2 ay humigit-kumulang 9e23, ngunit
depende sa bilang ng mga bloke k kung tinukoy mo ang -k opsyon. Lahat ng primes B1 <= p <=
B2 ay naproseso sa hakbang 2. Kung B2 < B1, walang hakbang 2 na isinasagawa.

B2min-B2max
Bilang kahalili ay maaaring gamitin ng isa ang B2min-B2max form, na nangangahulugan na ang lahat ng primes B2min <= p
<= B2max dapat iproseso. Kaya tinukoy B2 tumutugma lamang sa B1-B2. Ang mga halaga
of B2min at B2max maaaring di-makatwirang malaki, ngunit ang kanilang pagkakaiba ay hindi dapat lumampas
humigit-kumulang 9e23, napapailalim sa bilang ng mga bloke k.

FACTORING Pamamaraan

-pm1
Magsagawa ng P-1 sa halip na ang default na paraan (ECM).

-pp1
Magsagawa ng P+1 sa halip na ang default na paraan (ECM).

GROUP AT Inisyal PUNTO MGA PARAMETERS

-x0 x
[ECM, P-1, P+1] Gamitin x (arbitrary-precision integer o rational) bilang paunang punto. Para sa
Halimbawa, -x0 1/3 ay pwede. Kung hindi ibinigay, x ay nabuo mula sa halaga ng sigma para sa ECM,
o nang random para sa P-1 at P+1.

-sigma s
[ECM] Gamitin s (arbitrary-precision integer) bilang curve generator. Kung aalisin, s is
nabuo nang random.

-A a
[ECM] Gamitin a (arbitrary-precision integer) bilang parameter ng curve. Kung aalisin, di ba
nabuo mula sa halaga ng sigma.

-punta Val
[ECM, P-1, P+1] I-multiply ang inisyal na punto sa Val, na maaaring anumang wastong pagpapahayag,
posibleng naglalaman ng espesyal na karakter N bilang place holder para sa kasalukuyang input
numero. Halimbawa:

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

HAKBANG 2 MGA PARAMETERS

-k k
[ECM, P-1, P+1] Magsagawa k bloke sa hakbang 2. Para sa isang ibinigay B2 halaga, pagtaas k
binabawasan ang paggamit ng memory ng hakbang 2, sa gastos ng mas maraming oras ng cpu.

-treefile file
Nag-iimbak ng ilang mga talahanayan ng data sa mga file ng disk upang bawasan ang dami ng memorya na inookupahan
hakbang 2, sa kapinsalaan ng disk I/O. Isusulat ang data sa mga file file.1, file.2 atbp.
Hindi gumagana sa mabilis na yugto 2 para sa P+1 at P-1.

-Kapangyarihan n
[ECM, P-1] Gamitin ang x^n para sa extension ni Brent-Suyama (-Kapangyarihan 1 hindi pinapagana ang kay Brent-Suyama
extension). Ang default na polynomial ay pinili depende sa paraan at B2. Para sa P-1
at P+1, hindi pinapagana ang mabilis na yugto 2. Para sa P-1, n dapat maging pantay.

-dickson n
[ECM, P-1] Gumamit ng degree-n Dickson's polynomial para sa extension ni Brent-Suyama. Para sa P-1 at
P+1, hindi pinapagana ang mabilis na yugto 2. Tulad ng para sa -Kapangyarihan, n dapat kahit para sa P-1.

-maxmem n
Gamitin sa pinakamaraming n megabytes ng memorya sa yugto 2.

-ntt, -hindi-ntt
Paganahin o huwag paganahin ang Number-Theoretic Transform code para sa polynomial arithmetic in
yugto 2. Sa NTT, pinili ang dF na maging isang kapangyarihan ng 2, at nililimitahan ng bilang
angkop na mga prime na akma sa isang machine word (na isang limitasyon lamang sa 32 bit
mga sistema). Ang -no-ntt na variant ay gumagamit ng mas maraming memory, ngunit mas mabilis kaysa sa NTT na may malaki
mga numero ng input. Bilang default, ginagamit ang NTT para sa P-1, P+1 at para sa ECM sa mga bilang ng laki sa
karamihan sa 30 machine words.

oUTPUT

-q
Tahimik na mode. Ang mga nahanap na factorization ay naka-print sa karaniwang output, na may mga kadahilanan
pinaghihiwalay ng mga puting espasyo, isang linya sa bawat numero ng input (kung walang nakitang salik, ang
ang numero ng input ay kinopya lamang).

-v
Verbose mode. Higit pang impormasyon ang nakalimbag, higit pa -v pinapataas ng mga opsyon ang verbosity. Sa
isa -v, ang uri ng modular multiplication na ginamit, paunang x0 na halaga, hakbang 2 mga parameter
at pag-unlad, at inaasahang mga kurba at oras upang mahanap ang mga salik na may iba't ibang laki para sa ECM
ay nakalimbag. Sa -v -v, ang halaga ng A para sa ECM at mga nalalabi sa dulo ng hakbang 1 at
hakbang 2 ay naka-print. Higit pa -v mag-print ng panloob na data para sa pag-debug.

-timestamp
Mag-print ng time stamp sa tuwing may pinoprosesong bagong ECM curve o P+1 o P-1 run.

MODULAR ARITMETIKO Opsyon

Maraming mga algorithm ang magagamit para sa modular multiplication. Sinusubukan ng programa na hanapin ang
pinakamahusay para sa bawat input; maaaring pilitin ng isa ang isang ibinigay na pamamaraan sa mga sumusunod na opsyon.

-mpzmod
Gumamit ng mpz_mod function ng GMP (sub-quadratic para sa malalaking input, ngunit nag-uudyok ng ilang overhead
para sa maliliit).

-modmuln
Gamitin ang multiplication ni Montgomery (quadratic version). Karaniwan ang pinakamahusay na paraan para sa maliit
input.

-redc
Gamitin ang multiplikasyon ni Montgomery (sub-quadratic na bersyon). Theoretically pinakamainam para sa
malaking input.

-nobase2
Huwag paganahin ang espesyal na base-2 code (na ginagamit kapag ang input number ay isang malaking factor ng
2^n+1 o 2^n-1, tingnan -v).

-base2 n
Sapilitang paggamit ng espesyal na base-2 code, ang input number ay dapat hatiin sa 2^n+1 kung n > 0, o 2^|n|-1
if n < 0.

FILE I / O

Ang mga sumusunod na opsyon ay nagbibigay-daan sa isa na magsagawa ng hakbang 1 at hakbang 2 nang hiwalay, alinman sa
iba't ibang makina, sa iba't ibang panahon, o paggamit ng iba't ibang software (sa partikular, George
Ang Prime95/mprime program ng Woltman ay maaaring gumawa ng hakbang 1 na output na angkop para sa pagpapatuloy sa
GMP-ECM). Maaari rin itong maging kapaki-pakinabang na hatiin ang hakbang 2 sa ilang mga pagtakbo, gamit ang B2min-B2max
pagpipilian.

-inp file
Kumuha ng input mula sa file file sa halip na mula sa karaniwang input.

-iligtas file
I-save ang resulta ng hakbang 1 sa file. Kung file umiiral, ang isang error ay nakataas. Halimbawa: upang gumanap
hakbang 1 lamang sa B1=1000000 sa composite number sa file na "c155" at i-save ito
magresulta sa file na "foo", gamitin

ecm -save foo 1e6 1 < c155

-savea file
katulad -iligtas, ngunit idinaragdag sa mga kasalukuyang file.

-ipagpatuloy file
Ipagpatuloy ang mga nalalabi mula sa file, nagbabasa mula sa karaniwang input kung file ay "-". Halimbawa: sa
gawin ang hakbang 2 kasunod ng itaas na hakbang 1 pagkalkula, gamitin

ecm -resume foo 1e6

-chkpoint file
Pana-panahong isulat ang kasalukuyang nalalabi sa yugto 1 hanggang file. Sa kaso ng pagkawala ng kuryente,
atbp., ang pagtutuos ay maaaring ipagpatuloy sa -ipagpatuloy pagpipilian.

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

LOOP MODE

Ang "loop mode" (opsyon -c n) ay nagbibigay-daan sa isa na magpatakbo ng ilang mga kurba sa bawat numero ng pag-input. Ang
kinokontrol ng mga sumusunod na opsyon ang pag-uugali nito.

-c n
Magsagawa n tumatakbo sa bawat input number (ang default ay isa). Ang pagpipiliang ito ay pangunahing kapaki-pakinabang para sa
P+1 (halimbawa sa n=3) o para sa ECM, kung saan n maaaring itakda sa inaasahang bilang ng
curves upang makahanap ng d-digit na factor na may ibinigay na hakbang 1 na nakatali. Ang pagpipiliang ito ay hindi tugma
sa -ipagpatuloy, -sigma, -x0. Pagbibigay -c 0 gumagawa ng isang walang katapusang loop hanggang sa ang isang kadahilanan ay
natagpuan.

-isa
Sa loop mode, huminto kapag may nakitang salik; ang default ay magpatuloy hanggang sa
cofactor ay prime o ang tinukoy na bilang ng mga run ay tapos na.

-b
Breadth-first processing: sa loop mode, magpatakbo ng isang curve para sa bawat input number, pagkatapos ay a
pangalawang kurba para sa bawat isa, at iba pa. Ito ang default na mode na may -inp.

-d
Depth-first processing: sa loop mode, tumakbo n mga kurba para sa unang numero, pagkatapos n curves
para sa pangalawa at iba pa. Ito ang default na mode na may karaniwang input.

-ve n
Sa loop mode, sa pangalawa at kasunod na pagtakbo, maglalabas lamang ng mga expression na mayroon sa
pinaka- n mga karakter. Default ay -ve 0.

-i n
Sa loop mode, dagdagan B1 by n pagkatapos ng bawat kurba.

-I n
Sa loop mode, multiply B1 sa pamamagitan ng isang kadahilanan depende sa n pagkatapos ng bawat kurba. Ang default ay isa
na dapat ay pinakamainam sa isang makina, habang -I 10 maaaring gamitin kapag sinusubukan
i-factor ang parehong numero nang sabay-sabay sa 10 magkaparehong makina.

KABIBI COMMAND Pagpapatupad

Ang mga optin na ito ay nagbibigay-daan para sa pagpapatupad ng mga shell command upang madagdagan ang pagpapagana sa GMP-ECM.

-prpcmd cmd
Isagawa ang utos cmd upang subukan ang primality kung ang mga kadahilanan at cofactor sa halip na GMP-ECM's
sariling function. Ang numerong susuriin ay ipinapasa sa pamamagitan ng stdin. Ang isang exit code na 0 ay
binibigyang kahulugan bilang "marahil prime", isang non-zero exit code bilang "composite".

-faccmd cmd
Nagsasagawa ng utos cmd sa tuwing ang isang salik ay makikita ng P-1, P+1 o ECM. Ang input number,
Ang factor at cofactor ay ipinapasa sa pamamagitan ng stdin, bawat isa sa isang linya. Ito ay maaaring gamitin ie sa
awtomatikong magpadala ng mga bagong kadahilanan:

ecm -faccmd 'mail -s "Nakahanap ng salik si $HOSTNAME"
[protektado ng email]' 11e6 < cunningham.in

-idlecmd cmd
Nagsasagawa ng utos cmd bago ang bawat kurba ng ECM, simulan ang P-1 o P+1 na pagtatangka sa isang numero.
Kung ang exit status ng cmd ay non-zero, ang GMP-ECM ay nagwawakas kaagad, kung hindi man ito
nagpapatuloy ng normal. Ang GMP-ECM ay huminto habang cmd tumatakbo, nag-aalok ng isang paraan para sa pagpapaalam
Ang GMP-ECM ay natutulog halimbawa habang ang system ay abala.

IBA PA

-n
Patakbuhin ang programa sa "maganda" na mode (sa ibaba ng normal na priyoridad).

-nn
Patakbuhin ang programa sa "napakaganda" na mode (idle priority).

-B2scale f
I-multiply ang default na hakbang 2 na nakatali B2 sa pamamagitan ng floating-point na halaga f. Halimbawa: -B2scale
0.5 hinahati ang default B2 sa pamamagitan 2.

-stage1time n
Idagdag n segundo hanggang yugto 1 oras. Ito ay kapaki-pakinabang upang makakuha ng tamang inaasahang oras -v if
bahagi ng stage 1 ay ginawa sa isa pang run.

-cofdec
Pilitin ang output ng cofactor sa decimal (kahit na ginamit ang mga expression).

-h, - Tumulong
Magpakita ng maikling paglalarawan ng paggamit ng ecm, mga parameter at mga opsyon sa command line.

-printconfig
Nagpi-print ng mga parameter ng configuration na ginagamit para sa compilation at paglabas.

INPUT SINTAX

Ang mga numero ng input ay maaaring magkaroon ng ilang mga form:

Mga raw decimal na numero tulad ng 123456789.

Maaaring maglagay ng mga komento sa file: lahat pagkatapos ng "//" ay hindi pinansin, hanggang sa katapusan ng
linya.

Pagpapatuloy ng linya. Kung ang isang linya ay nagtatapos sa isang backslash na character na "\", ito ay itinuturing na
magpatuloy sa susunod na linya.

Maaaring gamitin ang mga karaniwang aritmetika na expression. Halimbawa: 3*5+2^10.

Factorial: halimbawa 53!.

Multi-factorial: halimbawa 15! 3 means 15*12*9*6*3.

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

Nabawasang primorial: halimbawa 17 # 5 means 5*7*11*13*17.

Mga Pag-andar: sa kasalukuyan, ang tanging magagamit na function ay Phi(x,n).

EXIT STATUS

Ang exit status ay sumasalamin sa resulta ng huling ECM curve o P-1/P+1 na pagtatangka sa programa
gumanap. Ang mga indibidwal na bit ay nagpapahiwatig ng mga partikular na kaganapan, partikular na:

Bit 0
0 kung normal na pagwawakas ng programa, 1 kung may naganap na error

Bit 1
0 kung walang nakitang tamang salik, 1 kung hindi

Bit 2
0 kung ang factor ay composite, 1 kung ang factor ay isang probable prime

Bit 3
0 kung ang cofactor ay composite, 1 kung ang cofactor ay isang probable prime

Kaya, maaaring mangyari ang mga sumusunod na exit status value:

0
Normal na pagwawakas ng programa, walang nakitang salik

1
pagkakamali

2
Nahanap ang composite factor, ang cofactor ay composite

6
Malamang prime factor natagpuan, cofactor ay composite

8
Nakita ang numero ng input

10
Nahanap ang composite factor, ang cofactor ay isang probable prime

14
May nakitang probable prime factor, cofactor is a probable prime

Gamitin ang ecm online gamit ang mga serbisyo ng onworks.net