ecm - En ligne dans le Cloud

PROGRAMME:

Nom

ecm - factorisation d'entiers utilisant ECM, P-1 ou P+1

SYNOPSIS

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

DESCRIPTION

ecm est un programme de factorisation d'entiers utilisant la méthode de la courbe elliptique (ECM), la méthode P-1,
ou la méthode P+1. Les sections suivantes décrivent les paramètres relatifs à ces
algorithmes.

ÉTAPE 1 ET ÉTAPE 2 LIÉ PARAMETRES

B1
B1 est la borne de l'étape 1. C'est un paramètre obligatoire. Il peut être donné soit en entier
format (par exemple 3000000) ou au format virgule flottante (3000000.0 ou 3e6). Les
le plus grand possible B1 la valeur est 9007199254740996 pour P-1, et ULONG_MAX ou
9007199254740996 (le plus petit des deux) pour ECM et P+1. Tous les nombres premiers 2 <= p <= B1
traité à l'étape 1.

B2
B2 est la borne de pas 2. Il est facultatif : s'il est omis, une valeur par défaut est calculée à partir de
B1, qui devrait être proche de l'optimum. Comme B1, il peut être donné soit en entier soit en
format à virgule flottante. La plus grande valeur possible de B2 est d'environ 9e23, mais
dépend du nombre de blocs k si vous spécifiez le -k option. Tous les nombres premiers B1 <= p <=
B2 sont traités à l'étape 2. Si B2 < B1, aucune étape 2 n'est effectuée.

B2min-B2max
alternativement, on peut utiliser le B2min-B2max forme, ce qui signifie que tous les nombres premiers B2min <= p
<= B2max doit être traité. spécifiant ainsi B2 correspond seulement à B1-B2. Les valeurs
of B2min ainsi que B2max peuvent être arbitrairement grandes, mais leur différence ne doit pas dépasser
environ 9e23, sous réserve du nombre de blocs k.

FACTEUR MÉTHODE

-pm1
Effectuez P-1 au lieu de la méthode par défaut (ECM).

-pp1
Effectuez P+1 au lieu de la méthode par défaut (ECM).

GROUPE ET INITIALE POINT PARAMETRES

-X0 x
[ECM, P-1, P+1] Utiliser x (entier de précision arbitraire ou rationnel) comme point initial. Pour
Par exemple, -X0 1/3 est valable. S'il n'est pas donné, x est généré à partir de la valeur sigma pour l'ECM,
ou au hasard pour P-1 et P+1.

-sigma s
[ECM] Utilisation s (entier de précision arbitraire) comme générateur de courbe. Si omis, s is
généré au hasard.

-A a
[ECM] Utilisation a (entier de précision arbitraire) comme paramètre de courbe. S'il est omis, est-ce
généré à partir de la valeur sigma.

-aller vague
[ECM, P-1, P+1] Multipliez le point initial par vague, qui peut toute expression valide,
contenant éventuellement le caractère spécial N comme espace réservé pour l'entrée actuelle
numéro. Exemple:

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

ÉTAPE 2 PARAMETRES

-k k
[ECM, P-1, P+1] Exécuter k blocs à l'étape 2. Pour un B2 valeur, augmentation k
diminue l'utilisation de la mémoire de l'étape 2, au détriment de plus de temps processeur.

-fichier arborescent filet
Stocke certaines tables de données dans des fichiers disque pour réduire la quantité de mémoire occupée dans
étape 2, au détriment des E/S disque. Les données seront écrites dans des fichiers filet. 1, filet.2 etc..
Ne fonctionne pas avec l'étage rapide 2 pour P+1 et P-1.

-Puissance n
[ECM, P-1] Utiliser x^n pour l'extension de Brent-Suyama (-Puissance 1 désactive le Brent-Suyama
extension). Le polynôme par défaut est choisi en fonction de la méthode et de B2. Pour P-1
et P+1, désactive l'étage rapide 2. Pour P-1, n doit être pair.

-Dickson n
[ECM, P-1] Utiliser le degré-n Le polynôme de Dickson pour l'extension de Brent-Suyama. Pour P-1 et
P+1, désactive l'étage rapide 2. Comme pour -Puissance, n doit être pair pour P-1.

-maxmem n
Utiliser au maximum n mégaoctets de mémoire à l'étape 2.

-ntt, -non-ntt
Activer ou désactiver le code de transformation théorique des nombres pour l'arithmétique polynomiale dans
étage 2. Avec NTT, dF est choisi comme une puissance de 2, et est limité par le nombre
nombres premiers appropriés qui tiennent dans un mot machine (ce qui n'est une limitation que sur 32 bits
systèmes). La variante -no-ntt utilise plus de mémoire, mais est plus rapide que NTT avec une grande
saisir des chiffres. Par défaut, NTT est utilisé pour P-1, P+1 et pour ECM sur des nombres de taille à
la plupart des 30 mots machines.

SORTIE

-q
Mode silencieux. Les factorisations trouvées sont imprimées sur la sortie standard, avec des facteurs
séparés par des espaces blancs, une ligne par numéro d'entrée (si aucun facteur n'a été trouvé, le
le numéro d'entrée est simplement copié).

-v
Mode verbeux. Plus d'informations sont imprimées, plus -v les options augmentent la verbosité. Avec
UN -v, le type de multiplication modulaire utilisée, la valeur x0 initiale, les paramètres de l'étape 2
et les progrès, et les courbes attendues et le temps pour trouver des facteurs de différentes tailles pour l'ECM
sont imprimés. Avec -v -v, la valeur A pour l'ECM et les résidus à la fin de l'étape 1 et
étape 2 sont imprimés. Suite -v imprimer les données internes pour le débogage.

-horodatage
Imprimez un horodatage chaque fois qu'une nouvelle courbe ECM ou une analyse P+1 ou P-1 est traitée.

MODULAR ARITHMÉTIQUE OPTIONS

Plusieurs algorithmes sont disponibles pour la multiplication modulaire. Le programme essaie de trouver le
le meilleur pour chaque entrée ; on peut forcer une méthode donnée avec les options suivantes.

-mpzmod
Utilisez la fonction mpz_mod de GMP (sous-quadratique pour les entrées volumineuses, mais induit une surcharge
pour les petits).

-modmuln
Utilisez la multiplication de Montgomery (version quadratique). Généralement la meilleure méthode pour les petits
contribution.

-rouge
Utilisez la multiplication de Montgomery (version sous-quadratique). Théoriquement optimal pour
grande entrée.

-nobase2
Désactivez le code spécial base-2 (qui est utilisé lorsque le nombre d'entrée est un facteur important de
2^n+1 ou 2^n-1, voir -v).

-base2 n
Forcer l'utilisation d'un code spécial en base 2, le nombre saisi doit diviser 2^n+1 si n > 0, ou 2^|n| -1
if n <0.

DOSSIER I / O

Les options suivantes permettent d'effectuer l'étape 1 et l'étape 2 séparément, soit sur
différentes machines, à différents moments, ou en utilisant différents logiciels (en particulier, George
Le programme Prime95/mprime de Woltman peut produire une sortie de l'étape 1 adaptée à la reprise avec
GMP-ECM). Il peut également être utile de diviser l'étape 2 en plusieurs passages, en utilisant le B2min-B2max
option.

-entrée filet
Prendre l'entrée du fichier filet au lieu de l'entrée standard.

-sauver filet
Enregistrer le résultat de l'étape 1 dans filet. Si filet existe, une erreur est générée. Exemple : effectuer
seule étape 1 avec B1=1000000 sur le numéro composé dans le fichier "c155" et enregistrez son
résultat dans le fichier "foo", utilisez

ecm -save foo 1e6 1 < c155

-sauvegarder filet
Comme -sauver, mais s'ajoute aux fichiers existants.

-CV filet
Reprendre les résidus de filet, lit à partir de l'entrée standard si filet est "-". Exemple : à
effectuez l'étape 2 après le calcul de l'étape 1 ci-dessus, utilisez

ecm -reprendre foo 1e6

-point de contrôle filet
Écrivez périodiquement le résidu actuel dans l'étape 1 à filet. En cas de panne de courant,
etc., le calcul peut être poursuivi avec le -CV option.

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

BOUCLE MODE

Le « mode boucle » (option -c n) permet d'exécuter plusieurs courbes sur chaque numéro d'entrée. Les
les options suivantes contrôlent son comportement.

-c n
Effectuer n s'exécute sur chaque numéro d'entrée (la valeur par défaut est un). Cette option est principalement utile pour
P+1 (par exemple avec n=3) ou pour l'ECM, où n peut être réglé sur le nombre attendu de
courbes pour trouver un facteur à d chiffres avec une borne de pas 1 donnée. Cette option est incompatible
avec -reprendre, -sigma, -X0. Donnant -c 0 produit une boucle infinie jusqu'à ce qu'un facteur soit
trouvé.

-un
En mode boucle, arrêt lorsqu'un facteur est trouvé ; la valeur par défaut est de continuer jusqu'à ce que le
cofacteur est premier ou le nombre spécifié d'exécutions est effectué.

-b
Traitement en largeur d'abord : en mode boucle, exécutez une courbe pour chaque nombre d'entrée, puis une
deuxième courbe pour chacun, et ainsi de suite. C'est le mode par défaut avec -entrée.

-d
Traitement en profondeur : en mode boucle, exécutez n courbes pour le premier nombre, puis n courbes
pour le deuxième et ainsi de suite. C'est le mode par défaut avec une entrée standard.

-ve n
En mode boucle, dans la deuxième exécution et les suivantes, ne sortez que les expressions qui ont au
(en fait, presque toutes) n personnages. La valeur par défaut est -ve 0.

-i n
En mode boucle, incrémenter B1 by n après chaque courbe.

-I n
En mode boucle, multiplier B1 par un facteur dépendant n après chaque courbe. La valeur par défaut est un
qui devrait être optimal sur une machine, tandis que -I 10 pourrait être utilisé en essayant de
factoriser le même nombre simultanément sur 10 machines identiques.

SHELL COMMAND EXÉCUTION

Ces optins permettent d'exécuter des commandes shell pour compléter les fonctionnalités de GMP-ECM.

-prpcmd cmd
Exécuter la commande cmd pour tester la primalité si facteurs et cofacteurs au lieu de GMP-ECM
propres fonctions. Le numéro à tester est transmis via stdin. Un code de sortie de 0 est
interprété comme "probablement premier", un code de sortie non nul comme "composite".

-faccmd cmd
Exécute la commande cmd chaque fois qu'un facteur est trouvé par P-1, P+1 ou ECM. Le numéro d'entrée,
le facteur et le cofacteur sont transmis via stdin, chacun sur une ligne. Cela pourrait être utilisé, c'est-à-dire pour
envoyer automatiquement les nouveaux facteurs :

ecm -faccmd 'mail -s "$HOSTNAME a trouvé un facteur"
[email protected]' 11e6 < cunningham.in

-idlecmd cmd
Exécute la commande cmd avant chaque courbe ECM, une tentative P-1 ou P+1 sur un numéro est lancée.
Si l'état de sortie de cmd est différent de zéro, GMP-ECM se termine immédiatement, sinon il
continue normalement. GMP-ECM est arrêté pendant cmd fonctionne, offrant un moyen de laisser
GMP-ECM veille par exemple pendant que le système est occupé par ailleurs.

DIVERS

-n
Exécutez le programme en mode « nice » (en dessous de la priorité normale).

-nn
Exécutez le programme en mode "très sympa" (priorité au repos).

-échelle B2 f
Multipliez la borne par défaut de l'étape 2 B2 par la valeur à virgule flottante f. exemple: -échelle B2
0.5 divise la valeur par défaut B2 dès 2.

-étape1heure n
Ajouter n secondes pour l'étape 1 fois. Ceci est utile pour obtenir le temps prévu correct avec -v if
une partie de l'étape 1 a été effectuée dans une autre manche.

-cofdec
Force la sortie du cofacteur en décimal (même si des expressions sont utilisées).

-h, --Aidez-moi
Affichez une brève description de l'utilisation d'ecm, des paramètres et des options de ligne de commande.

-configuration d'impression
Imprime les paramètres de configuration utilisés pour la compilation et quitte.

CONTRIBUTION SYNTAXE

Les numéros d'entrée peuvent avoir plusieurs formes :

Nombres décimaux bruts comme 123456789.

Des commentaires peuvent être placés dans le fichier : tout ce qui suit « // » est ignoré, jusqu'à la fin de
ligne.

Suite de la ligne. Si une ligne se termine par une barre oblique inverse "\", elle est considérée comme
continuer sur la ligne suivante.

Des expressions arithmétiques courantes peuvent être utilisées. Exemple: 3*5+2^10.

Factorielle : exemple 53!.

Multifactoriel : exemple 15! 3 means 15*12*9*6*3.

Primordial : exemple 11 # means 2*3*5*7*11.

Primorial réduit : exemple 17 # 5 means 5*7*11*13*17.

Fonctions : actuellement, la seule fonction disponible est Phi(x,n).

EXIT STATUT

L'état de sortie reflète le résultat de la dernière courbe ECM ou P-1/P+1 tentative du programme
effectué. Les bits individuels signifient des événements particuliers, en particulier :

Bit 0
0 si fin normale du programme, 1 si erreur survenue

Bit 1
0 si aucun facteur approprié n'a été trouvé, 1 sinon

Bit 2
0 si le facteur est composite, 1 si le facteur est un nombre premier probable

Bit 3
0 si le cofacteur est composite, 1 si le cofacteur est un nombre premier probable

Ainsi, les valeurs d'état de sortie suivantes peuvent apparaître :

0
Fin de programme normale, aucun facteur trouvé

1
Erreur

2
Facteur composite trouvé, le cofacteur est composite

6
Facteur premier probable trouvé, le cofacteur est composite

8
Numéro d'entrée trouvé

10
Facteur composite trouvé, le cofacteur est un nombre premier probable

14
Facteur premier probable trouvé, le cofacteur est un premier probable

Utiliser ecm en ligne en utilisant les services onworks.net