ecm - Online nel Cloud

PROGRAMMA:

NOME

ecm - fattorizzazione di interi usando ECM, P-1 o P+1

SINOSSI

ECM [Opzioni] B1 [SI2 min-B2max | B2]

DESCRIZIONE

ecm è un programma di fattorizzazione di interi che utilizza il metodo della curva ellittica (ECM), il metodo P-1,
o il metodo P+1. Le sezioni seguenti descrivono i parametri relativi a questi
algoritmi.

STEP 1 E STEP 2 LIMITE PARAMETRI

B1
B1 è il limite del passaggio 1. È un parametro obbligatorio. Può essere dato sia in intero
formato (ad esempio 3000000) o in formato a virgola mobile (3000000.0 o 3e6). Il
il più grande possibile B1 il valore è 9007199254740996 per P-1 e ULONG_MAX o
9007199254740996 (il più piccolo dei due) per ECM e P+1. Tutti i primi 2 <= p <= B1 sono
elaborato nel passaggio 1.

B2
B2 è il passaggio 2 vincolato. È facoltativo: se omesso, viene calcolato un valore predefinito da
B1, che dovrebbe essere vicino all'ottimale. Piace B1, può essere dato sia in intero che in
formato a virgola mobile. Il più grande valore possibile di B2 è approssimativamente 9e23, ma
dipende dal numero di blocchi k se specifichi il -k opzione. Tutti i numeri primi B1 <= p <=
B2 vengono elaborati nel passaggio 2. Se B2 < B1, non viene eseguito il passaggio 2.

SI2 min-B2max
in alternativa si può usare il SI2 min-B2max forma, il che significa che tutti i numeri primi SI2 min <= p
<= B2max dovrebbe essere processato. Così specificando B2 corrisponde solo a B1-B2. I valori
of SI2 min ed B2max possono essere arbitrariamente grandi, ma la loro differenza non deve superare
circa 9e23, soggetto al numero di blocchi k.

Factoring METODO

-pm1
Eseguire P-1 invece del metodo predefinito (ECM).

-pp1
Eseguire P+1 invece del metodo predefinito (ECM).

GRUPPO E INIZIALE POINT PARAMETRI

-x0 x
[ECM, P-1, P+1] Usa x (intero a precisione arbitraria o razionale) come punto iniziale. Per
esempio, -x0 1/3 è valido. Se non dato, x è generato dal valore sigma per ECM,
o a caso per P-1 e P+1.

-sigma s
[ECM] Usa s (intero a precisione arbitraria) come generatore di curve. Se omesso, s is
generato in modo casuale.

-A a
[ECM] Usa a (intero a precisione arbitraria) come parametro della curva. Se omesso, è?
generato dal valore sigma.

-partire val
[ECM, P-1, P+1] Moltiplicare il punto iniziale per val, che può qualsiasi espressione valida,
possibilmente contenente il carattere speciale N come segnaposto per l'input corrente
numero. Esempio:

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

STEP 2 PARAMETRI

-k k
[ECM, P-1, P+1] Esegui k blocchi nel passaggio 2. Per un dato B2 valore, crescente k
riduce l'utilizzo della memoria del passaggio 2, a scapito di più tempo della CPU.

-file ad albero filetto
Memorizza alcune tabelle di dati in file su disco per ridurre la quantità di memoria occupata in
passaggio 2, a spese dell'I/O del disco. I dati verranno scritti su file filetto. 1, filetto.2 ecc.
Non funziona con la fase 2 veloce per P+1 e P-1.

-Power n
[ECM, P-1] Usa x^n per l'estensione di Brent-Suyama (-Power 1 disabilita Brent-Suyama's
estensione). Il polinomio predefinito viene scelto a seconda del metodo e di B2. Per P-1
e P+1, disabilita lo stadio veloce 2. Per P-1, n deve essere pari.

-Dickson n
[ECM, P-1] Usa grado-n Polinomio di Dickson per l'estensione di Brent-Suyama. Per P-1 e
P+1, disabilita lo stadio veloce 2. Come per -Power, n deve essere pari per P-1.

-max n
Utilizzare al massimo n megabyte di memoria nella fase 2.

-nt, -no-ntt
Abilita o disabilita il codice della Trasformata Teorica dei Numeri per l'aritmetica polinomiale in
fase 2. Con NTT, dF viene scelto per essere una potenza di 2 ed è limitato dal numero
primi adatti che si adattano a una parola macchina (che è una limitazione solo su 32 bit
sistemi). La variante -no-ntt utilizza più memoria, ma è più veloce di NTT con large
inserire i numeri. Per impostazione predefinita, NTT viene utilizzato per P-1, P+1 e per ECM su numeri di dimensione a
la maggior parte delle 30 parole macchina.

USCITA

-q
Modalità silenziosa. Le fattorizzazioni trovate vengono stampate sullo standard output, con i fattori
separati da spazi bianchi, una riga per numero di input (se non è stato trovato alcun fattore, il
il numero di input viene semplicemente copiato).

-v
Modalità dettagliata. Maggiori informazioni vengono stampate, altro -v le opzioni aumentano la verbosità. Insieme a
prima -v, il tipo di moltiplicazione modulare utilizzata, il valore iniziale x0, i parametri del passaggio 2
e progresso, e curve attese e tempo per trovare fattori di diverse dimensioni per ECM
sono stampati. Insieme a -v -v, il valore A per ECM e residui alla fine del passaggio 1 e
vengono stampati il ​​passaggio 2. Di più -v stampa i dati interni per il debug.

- timestamp
Stampa un timestamp ogni volta che viene elaborata una nuova curva ECM o una corsa P+1 o P-1.

MODULAR ARITMETICA VERSIONI

Sono disponibili diversi algoritmi per la moltiplicazione modulare. Il programma cerca di trovare il
il migliore per ogni ingresso; si può forzare un dato metodo con le seguenti opzioni.

-mpzmod
Usa la funzione mpz_mod di GMP (sub-quadratica per input di grandi dimensioni, ma induce un sovraccarico
per i piccoli).

-moduln
Usa la moltiplicazione di Montgomery (versione quadratica). Di solito il metodo migliore per i piccoli
ingresso.

-rosso
Usa la moltiplicazione di Montgomery (versione subquadratica). Teoricamente ottimale per
grande ingresso.

-nobase2
Disabilita il codice speciale base 2 (che viene utilizzato quando il numero di input è un fattore elevato di
2^n+1 o 2^n-1, vedi -v).

-base2 n
Forza l'uso del codice speciale in base 2, il numero di input deve dividere 2^n+1 se n > 0, o 2^|n| -1
if n <0.

RISORSE I / O

Le seguenti opzioni consentono di eseguire il passaggio 1 e il passaggio 2 separatamente, su
macchine diverse, in momenti diversi, o utilizzando software diversi (in particolare, George
Il programma Prime95/mprime di Woltman può produrre un output del passaggio 1 adatto per la ripresa con
GMP-ECM). Può anche essere utile suddividere la fase 2 in più esecuzioni, utilizzando il tasto B2min-B2max
opzione.

-ing filetto
Prendi input da file filetto invece che dall'input standard.

-Salva filetto
Salva il risultato del passaggio 1 in filetto. Se filetto esiste, viene generato un errore. Esempio: eseguire
solo il passaggio 1 con B1=1000000 sul numero composto nel file "c155" e salvarlo
risultato nel file "pippo", usa

ecm -save foo 1e6 1 < c155

-salva filetto
Come -Salva, ma si aggiunge ai file esistenti.

-curriculum vitae filetto
Riprendi residui da filetto, legge dallo standard input se filetto è "-". Esempio: to
eseguire il passaggio 2 seguendo il calcolo del passaggio 1 sopra, utilizzare

ecm -resume foo 1e6

-chkpoint filetto
Scrivi periodicamente il residuo corrente nella fase 1 in filetto. In caso di mancanza di corrente,
ecc., il calcolo può essere continuato con il -curriculum vitae opzione.

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

CICLO CONTINUO MODE

La “modalità loop” (opzione -c n) permette di eseguire più curve su ogni numero di ingresso. Il
le seguenti opzioni ne controllano il comportamento.

-c n
Eseguire n viene eseguito su ciascun numero di input (l'impostazione predefinita è uno). Questa opzione è utile principalmente per
P+1 (ad esempio con n=3) o per ECM, dove n potrebbe essere impostato sul numero previsto di
curve per trovare un fattore d-digit con un dato limite del passaggio 1. Questa opzione non è compatibile
con -riprendere, -sigma, -x0. Dando -c 0 produce un ciclo infinito finché un fattore è
trovato.

-uno
In modalità loop, fermati quando viene trovato un fattore; l'impostazione predefinita è continuare fino al
cofactor è primo o viene eseguito il numero specificato di esecuzioni.

-b
Elaborazione in ampiezza: in modalità loop, eseguire una curva per ogni numero di input, quindi a
seconda curva per ognuna, e così via. Questa è la modalità predefinita con -ing.

-d
Elaborazione in profondità: in modalità loop, run n curve per il primo numero, quindi n curve
per il secondo e così via. Questa è la modalità predefinita con input standard.

-e n
In modalità loop, nella seconda e nelle successive esecuzioni, emette solo espressioni che hanno at
maggior parte n caratteri. L'impostazione predefinita è -e 0.

-i n
In modalità loop, incrementa B1 by n dopo ogni curva.

-I n
In modalità loop, moltiplica B1 di un fattore dipendente da n dopo ogni curva. Il valore predefinito è uno
che dovrebbe essere ottimale su una macchina, mentre -I 10 potrebbe essere usato quando si cerca di
fattorizzare lo stesso numero contemporaneamente su 10 macchine identiche.

SHELL COMANDO ESECUZIONE

Questi optin consentono l'esecuzione di comandi shell per integrare le funzionalità di GMP-ECM.

-prpccmd cmd
Esegui comando cmd per testare la primalità se fattori e cofattori invece di GMP-ECM's
proprie funzioni. Il numero da testare viene passato tramite stdin. Un codice di uscita di 0 è
interpretato come "probabilmente primo", un codice di uscita diverso da zero come "composito".

-facc cmd
Esegue il comando cmd ogni volta che un fattore viene trovato da P-1, P+1 o ECM. Il numero di ingresso,
fattore e cofattore vengono passati tramite stdin, ciascuno su una riga. Questo potrebbe essere usato ad esempio per
inviare automaticamente nuovi fattori:

ecm -faccmd 'mail -s “$HOSTNAME ha trovato un fattore”
[email protected]' 11e6 < cunningham.in

-idlecmd cmd
Esegue il comando cmd prima di ogni curva ECM, viene avviato il tentativo P-1 o P+1 su un numero.
Se lo stato di uscita di cmd è diverso da zero, GMP-ECM termina immediatamente, altrimenti è
continua normalmente. GMP-ECM viene interrotto mentre cmd corre, offrendo un modo per lasciare
GMP-ECM dorme ad esempio mentre il sistema è occupato.

VARIE

-n
Esegui il programma in modalità "nice" (sotto la priorità normale).

-nn
Esegui il programma in modalità "molto bello" (priorità inattiva).

-scala B2 f
Moltiplica il limite del passaggio 2 predefinito B2 dal valore in virgola mobile f. Esempio: -scala B2
0.5 divide l'impostazione predefinita B2 by 2.

-stage1time n
Aggiungi n secondi alla fase 1 volta. Questo è utile per ottenere l'orario previsto corretto con -v if
parte della fase 1 è stata eseguita in un'altra corsa.

-cofdec
Forza l'output del cofattore in decimale (anche se vengono utilizzate le espressioni).

-h, --Aiuto
Visualizza una breve descrizione dell'utilizzo di ecm, dei parametri e delle opzioni della riga di comando.

-printconfig
Stampa i parametri di configurazione utilizzati per la compilazione ed esce.

INGRESSO SINTASSI

I numeri di input possono avere diverse forme:

Numeri decimali grezzi come 123456789.

I commenti possono essere inseriti nel file: tutto ciò che segue “//” viene ignorato, fino alla fine di
linea.

Continuazione della linea. Se una riga termina con un carattere barra rovesciata "\", è considerata
continuare sulla riga successiva.

Si possono usare espressioni aritmetiche comuni. Esempio: 3*5+2^10.

Fattoriale: esempio 53!.

Multifattoriale: esempio 15! 3 means 15*12*9*6*3.

Primoriale: esempio 11 # means 2*3*5*7*11.

Primoriale ridotto: esempio 17 # 5 means 5*7*11*13*17.

Funzioni: attualmente l'unica funzione disponibile è Fi(x,n).

EXIT STATUS

Lo stato di uscita riflette il risultato dell'ultima curva ECM o P-1/P+1 tentativo di programma
eseguita. I singoli bit indicano eventi particolari, in particolare:

bit 0
0 se normale terminazione del programma, 1 se si è verificato un errore

bit 1
0 se non è stato trovato alcun fattore proprio, 1 altrimenti

bit 2
0 se il fattore è composto, 1 se il fattore è un probabile primo

bit 3
0 se il cofattore è composto, 1 se il cofattore è un probabile primo

Pertanto, possono verificarsi i seguenti valori di stato di uscita:

0
Terminazione normale del programma, nessun fattore trovato

1
Errore

2
Fattore composto trovato, il cofattore è composto

6
Probabile fattore primo trovato, il cofattore è composto

8
Numero inserito trovato

10
Fattore composto trovato, il cofattore è un probabile primo

14
Probabile fattore primo trovato, il cofattore è un probabile primo

Usa ecm online utilizzando i servizi onworks.net