ecm – Online in der Cloud

PROGRAMM:

NAME/FUNKTION

ecm – Ganzzahlfaktorisierung mit ECM, P-1 oder P+1

ZUSAMMENFASSUNG

ECM [Optionen] B1 [B2min-B2max | B2]

BESCHREIBUNG

ecm ist ein Ganzzahlfaktorisierungsprogramm, das die Elliptic Curve Method (ECM), die P-1-Methode, verwendet.
oder die P+1-Methode. In den folgenden Abschnitten werden die hierfür relevanten Parameter beschrieben
Algorithmen.

STEP 1 UND STEP 2 GEBUNDEN PARAMETER

B1
B1 ist die Schritt-1-Grenze. Es handelt sich um einen obligatorischen Parameter. Es kann entweder als Ganzzahl angegeben werden
Format (z. B. 3000000) oder im Gleitkommaformat (3000000.0 oder 3e6). Der
größtmögliche B1 Der Wert ist 9007199254740996 für P-1 und ULONG_MAX oder
9007199254740996 (je nachdem, welcher Wert kleiner ist) für ECM und P+1. Alle Primzahlen 2 <= p <= B1 sind
in Schritt 1 verarbeitet.

B2
B2 ist der Schritt 2 gebunden. Es ist optional: Wenn es weggelassen wird, wird ein Standardwert berechnet
B1, was nahezu optimal sein sollte. Wie B1, es kann entweder als Ganzzahl oder in angegeben werden
Gleitkommaformat. Der größtmögliche Wert von B2 ist ungefähr 9e23, aber
hängt von der Anzahl der Blöcke ab k wenn Sie das angeben -k Möglichkeit. Alles Primzahlen B1 <= p <=
B2 werden in Schritt 2 bearbeitet. Wenn B2 < B1, wird kein Schritt 2 durchgeführt.

B2min-B2max
Alternativ kann man auch die verwenden B2min-B2max Form, was bedeutet, dass alle Primzahlen B2min <= S
<= B2max verarbeitet werden sollen. So spezifizieren B2 entspricht nur B1-B2. Die Werte
of B2min und B2max können beliebig groß sein, ihre Differenz darf jedoch nicht überschritten werden
ca. 9e23, abhängig von der Anzahl der Blöcke k.

FAKTORIERUNG METHODE

-pm1
Führen Sie P-1 anstelle der Standardmethode (ECM) durch.

-pp1
Führen Sie P+1 anstelle der Standardmethode (ECM) aus.

UND URSPRÜNGLICHE POINT PARAMETER

-x0 x
[ECM, P-1, P+1] Verwendung x (ganzzahlige oder rationale Zahl mit beliebiger Genauigkeit) als Ausgangspunkt. Für
Beispiel -x0 1/3 ist gültig. Falls nicht angegeben, x wird aus dem Sigma-Wert für ECM generiert,
oder zufällig für P-1 und P+1.

-Sigma s
[ECM] Verwendung s (Ganzzahl beliebiger Genauigkeit) als Kurvengenerator. Wenn weggelassen, s is
zufällig generiert.

-A a
[ECM] Verwendung a (Ganzzahl beliebiger Genauigkeit) als Kurvenparameter. Wenn weggelassen, ist es das
wird aus dem Sigma-Wert generiert.

-gehen Welle
[ECM, P-1, P+1] Multiplizieren Sie den Anfangspunkt mit Welle, was jeder gültige Ausdruck sein kann,
Enthält möglicherweise das Sonderzeichen N als Platzhalter für die aktuelle Eingabe
Nummer. Beispiel:

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

STEP 2 PARAMETER

-k k
[ECM, P-1, P+1] Ausführen k Blöcke in Schritt 2. Für eine gegebene B2 Wert, zunehmend k
Verringert die Speichernutzung von Schritt 2 auf Kosten einer höheren CPU-Zeit.

-Baumdatei Datei
Speichert einige Datentabellen in Festplattendateien, um den belegten Speicher zu reduzieren
Schritt 2, auf Kosten der Festplatten-E/A. Die Daten werden in Dateien geschrieben Datei. 1, Datei.2 usw.
Funktioniert nicht mit Schnellstufe 2 für P+1 und P-1.

-Macht n
[ECM, P-1] Verwenden Sie x^n für Brent-Suyamas Erweiterung (-Macht 1 deaktiviert Brent-Suyamas
Verlängerung). Das Standardpolynom wird abhängig von der Methode und B2 ausgewählt. Für P-1
und P+1, deaktiviert die schnelle Stufe 2. Für P-1, n muss eben sein.

-Dickson n
[ECM, P-1] Grad verwendenn Dicksons Polynom für die Brent-Suyama-Erweiterung. Für P-1 und
P+1, deaktiviert die schnelle Stufe 2. Wie für -Macht, n muss für P-1 gerade sein.

-maxim n
Höchstens verwenden n Megabyte Speicher in Stufe 2.

-ntt, -nein-ntt
Aktivieren oder deaktivieren Sie den zahlentheoretischen Transformationscode für Polynomarithmetik in
Stufe 2. Bei NTT wird dF als Potenz von 2 gewählt und durch die Zahl begrenzt
geeignete Primzahlen, die in ein Maschinenwort passen (was nur bei 32 Bit eine Einschränkung darstellt).
Systeme). Die Variante -no-ntt verbraucht mehr Speicher, ist aber schneller als NTT mit Large
Zahlen eingeben. Standardmäßig wird NTT für P-1, P+1 und für ECM bei Zahlen der Größe at verwendet
die meisten 30 Maschinenwörter.

AUSGABE

-q
Ruhemodus. Gefundene Faktorisierungen werden auf der Standardausgabe mit Faktoren gedruckt
durch Leerzeichen getrennt, eine Zeile pro Eingabenummer (wenn kein Faktor gefunden wurde, wird die
Eingabenummer wird einfach kopiert).

-v
Ausführlicher Modus. Weitere Informationen sind abgedruckt, mehr -v Optionen erhöhen die Ausführlichkeit. Mit
dank One -v, die Art der verwendeten modularen Multiplikation, der anfängliche x0-Wert, Schritt-2-Parameter
und Fortschritt sowie erwartete Kurven und Zeit, um Faktoren unterschiedlicher Größe für ECM zu finden
werden gedruckt. Mit -v -v, der A-Wert für ECM und Rückstände am Ende von Schritt 1 und
Schritt 2 werden gedruckt. Mehr -v Drucken Sie interne Daten zum Debuggen.

-Zeitstempel
Drucken Sie einen Zeitstempel, wenn eine neue ECM-Kurve oder ein P+1- oder P-1-Lauf verarbeitet wird.

MODULAR ARITHMETIK OPTIONAL

Für die modulare Multiplikation stehen mehrere Algorithmen zur Verfügung. Das Programm versucht, das zu finden
die beste für jede Eingabe; Mit den folgenden Optionen kann man eine bestimmte Methode erzwingen.

-mpzmod
Verwenden Sie die mpz_mod-Funktion von GMP (subquadratisch für große Eingaben, verursacht jedoch einen gewissen Overhead
für die Kleinen).

-modmuln
Verwenden Sie die Montgomery-Multiplikation (quadratische Version). Normalerweise die beste Methode für kleine
Eingang.

-redc
Verwenden Sie die Montgomery-Multiplikation (subquadratische Version). Theoretisch optimal für
großer Input.

-nobase2
Deaktivieren Sie den speziellen Basis-2-Code (der verwendet wird, wenn die Eingabezahl einen großen Faktor von hat).
2^n+1 oder 2^n-1, siehe -v).

-base2 n
Erzwingen Sie die Verwendung eines speziellen Basis-2-Codes. Die eingegebene Zahl muss durch 2^ geteilt werdenn+1 wenn n > 0 oder 2^|n| -1
if n <0.

FILE I / O

Mit den folgenden Optionen können Sie Schritt 1 und Schritt 2 getrennt ausführen
verschiedene Maschinen, zu unterschiedlichen Zeiten oder mit unterschiedlicher Software (insbesondere George
Woltmans Prime95/mprime-Programm kann eine Ausgabe für Schritt 1 erzeugen, die zum Fortsetzen geeignet ist
GMP-ECM). Es kann auch sinnvoll sein, Schritt 2 mithilfe von in mehrere Durchgänge aufzuteilen B2min-B2max
.

-inp Datei
Übernehmen Sie die Eingabe aus der Datei Datei statt von der Standardeingabe.

-speichern Datei
Speichern Sie das Ergebnis von Schritt 1 in Datei. Wenn Datei existiert, wird ein Fehler ausgelöst. Beispiel: durchführen
nur Schritt 1 mit B1=1000000 für die zusammengesetzte Zahl in der Datei „c155“ und speichern Sie sie
Ergebnis in der Datei „foo“, verwenden

ecm -save foo 1e6 1 < c155

-speichere ein Datei
Like -speichern, wird aber an vorhandene Dateien angehängt.

-fortsetzen Datei
Rückstände abtragen Datei, liest von der Standardeingabe, wenn Datei Ist "-". Beispiel: zu
Führen Sie Schritt 2 nach der obigen Berechnung von Schritt 1 aus und verwenden Sie

ecm -resume foo 1e6

-chkpoint Datei
Schreiben Sie regelmäßig den aktuellen Rest in Stufe 1 auf Datei. Im Falle eines Stromausfalls
usw. kann die Berechnung mit dem fortgesetzt werden -fortsetzen .

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

LOOP MODE

Der „Loop-Modus“ (Option -c n) ermöglicht es, mehrere Kurven für jede Eingabezahl auszuführen. Der
Die folgenden Optionen steuern das Verhalten.

-c n
Ausführen n Läuft auf jeder Eingabenummer (Standard ist eins). Diese Option ist hauptsächlich nützlich für
P+1 (zum Beispiel mit n=3) oder für ECM, wo n konnte auf die erwartete Anzahl eingestellt werden
Kurven, um einen d-stelligen Faktor mit einer gegebenen Schritt-1-Grenze zu finden. Diese Option ist nicht kompatibel
mit -wieder aufnehmen, -Sigma, -x0. Geben -c 0 erzeugt eine Endlosschleife, bis ein Faktor vorhanden ist
gefunden.

-ein
Stoppen Sie im Schleifenmodus, wenn ein Faktor gefunden wird. Die Standardeinstellung ist, bis zum fortzufahren
Cofaktor ist eine Primzahl oder die angegebene Anzahl von Durchläufen wird durchgeführt.

-b
Breitenorientierte Verarbeitung: Führen Sie im Schleifenmodus eine Kurve für jede Eingabezahl aus, dann a
zweite Kurve für jede, und so weiter. Dies ist der Standardmodus mit -inp.

-d
Tiefenverarbeitung: Im Schleifenmodus ausführen n Kurven für die erste Zahl also n Kurven
für den zweiten und so weiter. Dies ist der Standardmodus mit Standardeingabe.

-ve n
Im Schleifenmodus werden im zweiten und folgenden Durchlauf nur Ausdrücke ausgegeben, die at haben
vor allem warme n Figuren. Standard ist -ve 0.

-i n
Im Schleifenmodus erhöhen B1 by n nach jeder Kurve.

-I n
Multiplizieren Sie im Schleifenmodus B1 um einen Faktor abhängig von n nach jeder Kurve. Der Standardwert ist eins
was auf einer Maschine optimal sein sollte, while -I 10 könnte beim Versuch verwendet werden
Faktorisieren Sie die gleiche Zahl gleichzeitig auf 10 identischen Maschinen.

SHELL COMMAND EXECUTION

Diese Optionen ermöglichen die Ausführung von Shell-Befehlen zur Ergänzung der Funktionalität von GMP-ECM.

-prpcmd cmd
Befehl ausführen cmd um die Primalität von Faktoren und Cofaktoren anstelle von GMP-ECMs zu testen
eigene Funktionen. Die zu testende Nummer wird per stdin übergeben. Ein Exit-Code von 0 ist
wird als „wahrscheinlich prim“ interpretiert, ein Exit-Code ungleich Null als „zusammengesetzt“.

-faccmd cmd
Führt Befehl aus cmd immer dann, wenn ein Faktor durch P-1, P+1 oder ECM gefunden wird. Die eingegebene Nummer,
Faktor und Cofaktor werden über stdin jeweils in einer Zeile übergeben. Dies könnte z. B. genutzt werden
Neue Faktoren automatisch verschicken:

ecm -faccmd 'mail -s „$HOSTNAME hat einen Faktor gefunden“
[E-Mail geschützt] ' 11e6 < cunningham.in

-idlecmd cmd
Führt Befehl aus cmd Vor jeder ECM-Kurve wird ein P-1- oder P+1-Versuch für eine Zahl gestartet.
Wenn der Exit-Status von cmd ungleich Null ist, terminiert GMP-ECM sofort, andernfalls
geht normal weiter. GMP-ECM wird währenddessen gestoppt cmd läuft und bietet eine Möglichkeit zum Vermieten
GMP-ECM schläft beispielsweise, während das System sonst ausgelastet ist.

SONSTIGES

-n
Führen Sie das Programm im „schönen“ Modus aus (unter der normalen Priorität).

-nn
Führen Sie das Programm im Modus „sehr schön“ aus (Priorität „Leerlauf“).

-B2-Skala f
Multiplizieren Sie die Standardgrenze für Schritt 2 B2 durch den Gleitkommawert f. Beispiel: -B2-Skala
0.5 teilt die Vorgabe B2 von 2.

-stage1time n
Speichern n Sekunden bis Stufe 1 Mal. Dies ist nützlich, um die korrekte erwartete Zeit zu ermitteln -v if
Ein Teil von Stufe 1 wurde in einem anderen Durchgang durchgeführt.

-cofdec
Cofaktor-Ausgabe in Dezimalzahl erzwingen (auch wenn Ausdrücke verwendet werden).

-h, --help
Zeigt eine kurze Beschreibung der ECM-Nutzung, Parameter und Befehlszeilenoptionen an.

-printconfig
Druckt Konfigurationsparameter, die für die Kompilierung und Exits verwendet werden.

SPEISUNG SYNTAX

Die eingegebenen Zahlen können verschiedene Formen haben:

Rohe Dezimalzahlen wie 123456789.

Kommentare können in die Datei eingefügt werden: Alles nach „//“ wird ignoriert, bis zum Ende von
Linie.

Fortsetzung der Zeile. Wenn eine Zeile mit einem Backslash-Zeichen „\“ endet, wird davon ausgegangen, dass dies der Fall ist
Fahren Sie mit der nächsten Zeile fort.

Es können gängige arithmetische Ausdrücke verwendet werden. Beispiel: 3*5+2^10.

Fakultät: Beispiel 53!.

Multifaktoriell: Beispiel 15! 3 means 15*12*9*6*3.

Ursprünglich: Beispiel 11 # means 2*3*5*7*11.

Reduziertes Urwort: Beispiel 17 # 5 means 5*7*11*13*17.

Funktionen: Derzeit ist die einzige verfügbare Funktion Phi(x,n).

EXIT STATUS

Der Exit-Status spiegelt das Ergebnis des letzten ECM-Kurven- oder P-1/P+1-Versuchs des Programms wider
durchgeführt. Einzelne Bits kennzeichnen bestimmte Ereignisse, insbesondere:

Bit 0
0 bei normalem Programmabbruch, 1 bei Fehler

Bit 1
0, wenn kein geeigneter Faktor gefunden wurde, andernfalls 1

Bit 2
0, wenn der Faktor zusammengesetzt ist, 1, wenn der Faktor eine wahrscheinliche Primzahl ist

Bit 3
0, wenn der Cofaktor zusammengesetzt ist, 1, wenn der Cofaktor eine wahrscheinliche Primzahl ist

Somit können folgende Exit-Statuswerte auftreten:

0
Normaler Programmabbruch, kein Faktor gefunden

1
Fehler

2
Zusammengesetzter Faktor gefunden, Cofaktor ist zusammengesetzt

6
Wahrscheinlicher Primfaktor gefunden, Cofaktor ist zusammengesetzt

8
Eingabenummer gefunden

10
Zusammengesetzter Faktor gefunden, Cofaktor ist eine wahrscheinliche Primzahl

14
Wahrscheinlicher Primfaktor gefunden, Cofaktor ist eine wahrscheinliche Primzahl

Nutzen Sie ecm online über die Dienste von onworks.net