ecm - Online in de cloud

PROGRAMMA:

NAAM

ecm - factorisatie van gehele getallen met behulp van ECM, P-1 of P+1

KORTE INHOUD

enzovoort [opties] B1 [B2min-B2max | B2]

PRODUCTBESCHRIJVING

ecm is een integer factoring programma dat gebruik maakt van de Elliptic Curve Method (ECM), de P-1 methode,
of de P+1-methode. In de volgende paragrafen worden parameters beschreven die hiervoor relevant zijn
algoritmen.

STAP 1 EN STAP 2 GEBONDEN PARAMETERS

B1
B1 is de stap 1 gebonden. Het is een verplichte parameter. Het kan ofwel in geheel getal worden gegeven
formaat (bijvoorbeeld 3000000) of in floating-point formaat (3000000.0 of 3e6). De
grootst mogelijk B1 waarde is 9007199254740996 voor P-1, en ULONG_MAX of
9007199254740996 (welke kleiner is) voor ECM en P+1. Alle priemgetallen 2 <= p <= B1 zijn
verwerkt in stap 1.

B2
B2 is de stap 2 gebonden. Het is optioneel: indien weggelaten, wordt een standaardwaarde berekend
B1, die bijna optimaal zou moeten zijn. Leuk vinden B1, kan worden gegeven in integer of in
drijvende-komma formaat. De grootst mogelijke waarde van B2 is ongeveer 9e23, maar
afhankelijk van het aantal blokken k als u de -k keuze. Allemaal priemgetallen B1 <=p <=
B2 worden verwerkt in stap 2. Als B2 < B1, wordt stap 2 niet uitgevoerd.

B2min-B2max
als alternatief kan men de gebruiken B2min-B2max vorm, wat betekent dat alle priemgetallen B2min <= blz
<= B2max moeten worden verwerkt. Aldus specificeren B2 komt alleen overeen met B1-B2​ De waarden
of B2min en B2max kan willekeurig groot zijn, maar hun verschil mag niet groter zijn
ongeveer 9e23, afhankelijk van het aantal blokken k.

FACTOREN METHODE

-pm1
Voer P-1 uit in plaats van de standaardmethode (ECM).

-pp1
Voer P+1 uit in plaats van de standaardmethode (ECM).

GROEP EN EERSTE PUNT PARAMETERS

-x0 x
[ECM, P-1, P+1] Gebruiken x (willekeurige precisie geheel getal of rationaal) als beginpunt. Voor
voorbeeld, -x0 1/3 is geldig. Indien niet gegeven, x wordt gegenereerd op basis van de sigma-waarde voor ECM,
of willekeurig voor P-1 en P+1.

-sigma s
[ECM] Gebruik s (willekeurige precisie geheel getal) als curvegenerator. Indien weggelaten, s is
willekeurig gegenereerd.

-A a
[ECM] Gebruik a (geheel getal met willekeurige precisie) als curveparameter. Indien weggelaten, is het
gegenereerd uit de sigma-waarde.

-Gaan golf
[ECM, P-1, P+1] Vermenigvuldig het beginpunt met golf, wat elke geldige uitdrukking kan zijn,
mogelijk met het speciale teken N als plaatshouder voor de huidige invoer
nummer. Voorbeeld:

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

STAP 2 PARAMETERS

-k k
[ECM, P-1, P+1] Uitvoeren k blokken in stap 2. Voor een gegeven B2 waarde, toenemend k
vermindert het geheugengebruik van stap 2, ten koste van meer cpu-tijd.

-boombestand filet
Slaat enkele gegevenstabellen op in schijfbestanden om de hoeveelheid bezet geheugen te verminderen
stap 2, ten koste van schijf-I/O. Gegevens worden naar bestanden geschreven filet. 1, filet.2 enz.
Werkt niet met snelle trap 2 voor P+1 en P-1.

-Power n
[ECM, P-1] Gebruik x^n voor de extensie van Brent-Suyama (-Power 1 schakelt Brent-Suyama uit
verlenging). De standaardpolynoom wordt gekozen afhankelijk van de methode en B2. Voor P-1
en P+1, schakelt de snelle fase 2 uit. Voor P-1, n moet gelijk zijn.

-Dickson n
[ECM, P-1] Gebruik graden-n Dickson's polynoom voor de uitbreiding van Brent-Suyama. Voor P-1 en
P+1, schakelt de snelle fase 2 uit. Zoals voor -Power, n moet gelijk zijn voor P-1.

-maximum n
Gebruik maximaal n megabyte geheugen in fase 2.

-ntt, -nee-ntt
Schakel de getaltheoretische transformatiecode voor polynomiale rekenkunde in of uit
fase 2. Bij NTT wordt dF gekozen als een macht van 2, en wordt beperkt door het getal
geschikte priemgetallen die in een machinewoord passen (wat alleen een beperking is op 32 bit
systemen). De -no-ntt variant gebruikt meer geheugen, maar is sneller dan NTT met large
cijfers invoeren. Standaard wordt NTT gebruikt voor P-1, P+1 en voor ECM op nummers van grootte at
de meeste 30 machinewoorden.

OUTPUT

-q
Stille modus. Gevonden factorisaties worden afgedrukt op standaarduitvoer, met factoren
gescheiden door spaties, één regel per invoernummer (als er geen factor is gevonden, wordt de
invoernummer wordt gewoon gekopieerd).

-v
Uitgebreide modus. Meer informatie wordt afgedrukt, meer -v opties vergroten de breedsprakigheid. Met
een -v, het gebruikte soort modulaire vermenigvuldiging, initiële x0-waarde, stap 2-parameters
en voortgang, en verwachte curves en tijd om factoren van verschillende grootte voor ECM te vinden
zijn gedrukt. Met -v -v, de A-waarde voor ECM en residuen aan het einde van stap 1 en
stap 2 worden afgedrukt. Meer -v druk interne gegevens af voor foutopsporing.

-tijdstempel
Druk een tijdstempel af wanneer een nieuwe ECM-curve of P+1- of P-1-run wordt verwerkt.

MODULAR REKENKUNDIG OPTIES

Er zijn verschillende algoritmen beschikbaar voor modulaire vermenigvuldiging. Het programma probeert de
beste voor elke invoer; men kan een bepaalde methode forceren met de volgende opties.

-mpzmod
Gebruik de mpz_mod-functie van GMP (sub-kwadratisch voor grote invoer, maar veroorzaakt enige overhead
voor kleintjes).

-modmuln
Gebruik de vermenigvuldiging van Montgomery (kwadratische versie). Meestal de beste methode voor kleine
invoer.

-redst
Gebruik de vermenigvuldiging van Montgomery (subkwadratische versie). Theoretisch optimaal voor
grote invoer.

-geenbasis2
Schakel speciale basis-2-code uit (die wordt gebruikt wanneer het ingevoerde getal een grote factor is van
2^n+1 of 2^n-1, zie -v).

-basis2 n
Forceer gebruik van speciale basis-2-code, invoernummer moet door 2^ worden gedeeldn+1 als n > 0 of 2^|n| -1
if n <0.

FILE I / O

Met de volgende opties kan men stap 1 en stap 2 afzonderlijk uitvoeren, hetzij aan
verschillende machines, op verschillende tijdstippen of met verschillende software (met name George
Het programma Prime95/mprime van Woltman kan uitvoer van stap 1 produceren die geschikt is om mee verder te gaan
GMP-ECM). Het kan ook handig zijn om stap 2 op te splitsen in meerdere runs, met behulp van de B2min-B2max
optie.

-inp filet
Neem invoer uit het bestand filet in plaats van uit standaard invoer.

-opslaan filet
Bewaar het resultaat van stap 1 in filet. Indien filet bestaat, wordt er een fout gegenereerd. Voorbeeld: uitvoeren
alleen stap 1 mee B1=1000000 op het samengestelde getal in het bestand "c155" en sla het op
resulteren in bestand "foo", gebruik

ecm -save foo 1e6 1 < c155

-besparen filet
Like -opslaan, maar wordt toegevoegd aan bestaande bestanden.

-cv filet
Hervat resten van filet, leest uit standaard invoer als filet is "-". Voorbeeld: naar
voer stap 2 uit volgens de bovenstaande stap 1 berekening, gebruik

ecm - hervat foo 1e6

-chkpunt filet
Schrijf periodiek het huidige residu in fase 1 naar filet. In het geval van een stroomstoring,
enz., kan de berekening worden voortgezet met de -cv optie.

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

LOOP MODE

De "loop-modus" (optie -c n) maakt het mogelijk om meerdere curven op elk invoernummer uit te voeren. De
volgende opties bepalen zijn gedrag.

-c n
Uitvoeren n draait op elk invoernummer (standaard is één). Deze optie is vooral handig voor
P+1 (bijvoorbeeld met n=3) of voor ECM, waar n kan worden ingesteld op het verwachte aantal
krommen om een ​​d-cijferige factor te vinden met een gegeven stap 1-grens. Deze optie is niet compatibel
Met -cv, -sigma, -x0. geven -c 0 produceert een oneindige lus totdat een factor is
gevonden.

-een
Stop in lusmodus wanneer een factor is gevonden; de standaard is om door te gaan tot de
cofactor is een priemgetal of het gespecificeerde aantal runs is gedaan.

-b
Breedte-eerste verwerking: voer in lusmodus één curve uit voor elk invoernummer en vervolgens a
tweede curve voor elk, enzovoort. Dit is de standaardmodus met -inp.

-d
Diepte-eerste verwerking: in lusmodus, uitvoeren n krommen voor het eerste nummer, dan n curves
voor de tweede enzovoort. Dit is de standaardmodus met standaardinvoer.

-ve n
Voer in de loop-modus in de tweede en volgende uitvoeringen alleen uitdrukkingen uit die at hebben
meest n karakters. Standaard is -ve 0.

-i n
In lusmodus, verhogen B1 by n na elke bocht.

-I n
Vermenigvuldig in lusmodus B1 met een factor afhankelijk van n na elke bocht. Standaard is één
die op één machine optimaal zou moeten zijn, terwijl -I 10 kan worden gebruikt bij het proberen
factor hetzelfde aantal tegelijkertijd op 10 identieke machines.

SHELL COMMAND EXECUTIE

Deze opt-ins maken het uitvoeren van shell-commando's mogelijk om de functionaliteit van GMP-ECM aan te vullen.

-prcmd cmd
Voer opdracht uit cmd om primaliteitsfactoren en cofactoren te testen in plaats van GMP-ECM's
eigen functies. Het te testen nummer wordt doorgegeven via stdin. Een exitcode van 0 is
geïnterpreteerd als "waarschijnlijk prime", een niet-nul exit-code als "composiet".

-facmd cmd
Voert opdracht uit cmd wanneer een factor wordt gevonden door P-1, P+1 of ECM. Het invoernummer,
factor en cofactor worden doorgegeven via stdin, elk op een regel. Dit zou kunnen worden gebruikt om oa
automatisch nieuwe factoren mailen:

ecm -faccmd 'mail -s “$HOSTNAME heeft een factor gevonden”
[e-mail beveiligd]' 11e6 < cunningham.in

-idlecmd cmd
Voert opdracht uit cmd voordat elke ECM-curve wordt gestart, wordt een P-1- of P+1-poging op een nummer gestart.
Als de exitstatus van cmd niet nul is, wordt GMP-ECM onmiddellijk beëindigd, anders wordt het
gaat normaal door. GMP-ECM wordt even gestopt cmd loopt en biedt een manier om te verhuren
GMP-ECM slaapt bijvoorbeeld terwijl het systeem verder bezig is.

DIVERSE

-n
Voer het programma uit in de "leuke" modus (onder normale prioriteit).

-nn
Voer het programma uit in de "zeer mooie" modus (inactieve prioriteit).

-B2schaal f
Vermenigvuldig de standaard stap 2 gebonden B2 door de drijvende-kommawaarde f. Voorbeeld: -B2schaal
0.5 verdeelt de standaard B2 door 2.

-stage1tijd n
Toevoegen n seconden naar fase 1 tijd. Dit is handig om de juiste verwachte tijd mee te krijgen -v if
een deel van etappe 1 werd in een andere run afgelegd.

-cofdec
Forceer cofactor-uitvoer in decimalen (zelfs als er uitdrukkingen worden gebruikt).

-h, --help
Geef een korte beschrijving weer van het gebruik van ecm, parameters en opdrachtregelopties.

-printconfig
Drukt configuratieparameters af die worden gebruikt voor de compilatie en sluit af.

INVOER SYNTAXIS

De invoernummers kunnen verschillende vormen hebben:

Ruwe decimale getallen zoals 123456789.

Opmerkingen kunnen in het bestand worden geplaatst: alles na "//" wordt genegeerd, tot het einde van
lijn.

Lijn voortzetting. Als een regel eindigt met een backslash-teken "\", wordt dit beschouwd als
verder op de volgende regel.

Algemene rekenkundige uitdrukkingen kunnen worden gebruikt. Voorbeeld: 3*5+2^10.

Faculteit: voorbeeld 53!.

Multifactorieel: voorbeeld 15! 3 means 15*12*9*6*3.

Primair: voorbeeld 11 # means 2*3*5*7*11.

Gereduceerd priemgetal: voorbeeld 17 # 5 means 5*7*11*13*17.

Functies: momenteel is de enige beschikbare functie Phi(x,n).

EXIT STATUS

De exitstatus weerspiegelt het resultaat van de laatste ECM-curve of P-1/P+1-poging van het programma
uitgevoerd. Individuele bits duiden bepaalde gebeurtenissen aan, met name:

Beetje 0
0 als het programma normaal is beëindigd, 1 als er een fout is opgetreden

Beetje 1
0 als er geen juiste factor is gevonden, anders 1

Beetje 2
0 als de factor samengesteld is, 1 als de factor een waarschijnlijk priemgetal is

Beetje 3
0 als cofactor samengesteld is, 1 als cofactor een waarschijnlijk priemgetal is

Zo kunnen de volgende uitgangsstatuswaarden voorkomen:

0
Normale programmabeëindiging, geen factor gevonden

1
Fout

2
Samengestelde factor gevonden, cofactor is samengesteld

6
Vermoedelijke priemfactor gevonden, cofactor is samengesteld

8
Invoernummer gevonden

10
Samengestelde factor gevonden, cofactor is een waarschijnlijk priemgetal

14
Waarschijnlijk priemgetal gevonden, cofactor is een waarschijnlijk priemgetal

Gebruik ecm online met behulp van onworks.net-services