ecm - Online na nuvem

PROGRAMA:

NOME

ecm - fatoração de número inteiro usando ECM, P-1 ou P + 1

SINOPSE

ecm [opções] B1 [B2min-B2máx | B2]

DESCRIÇÃO

ecm é um programa de fatoração de inteiros usando o Método da Curva Elíptica (ECM), o método P-1,
ou o método P + 1. As seções a seguir descrevem os parâmetros relevantes para esses
algoritmos.

PASSO 1 E PASSO 2 LIMITE PARÂMETROS

B1
B1 é o limite da etapa 1. É um parâmetro obrigatório. Pode ser dado em número inteiro
formato (por exemplo 3000000) ou em formato de ponto flutuante (3000000.0 ou 3e6). o
maior possível B1 o valor é 9007199254740996 para P-1 e ULONG_MAX ou
9007199254740996 (o que for menor) para ECM e P + 1. Todos os primos 2 <= p <= B1 e guarante que os mesmos estão
processado na etapa 1.

B2
B2 é o limite da etapa 2. É opcional: se omitido, um valor padrão é calculado a partir de
B1, que deve estar próximo do ideal. Gostar B1, pode ser dado em número inteiro ou em
formato de ponto flutuante. O maior valor possível de B2 é aproximadamente 9e23, mas
depende do número de blocos k se você especificar o -k opção. Todos os primos B1 <= p <=
B2 são processados ​​na etapa 2. Se B2 < B1, nenhuma etapa 2 é executada.

B2min-B2máx
alternativamente, pode-se usar o B2min-B2máx forma, o que significa que todos os primos B2min <= p
<= B2máx deve ser processado. Assim especificando B2 apenas corresponde a B1-B2. Os valores
of B2min e B2máx pode ser arbitrariamente grande, mas sua diferença não deve exceder
aproximadamente 9e23, sujeito ao número de blocos k.

FATORING MÉTODO

-pm1
Execute P-1 em vez do método padrão (ECM).

-pp1
Execute P + 1 em vez do método padrão (ECM).

GRUPO E INICIAL PONTO PARÂMETROS

-x0 x
[ECM, P-1, P + 1] Use x (inteiro ou racional de precisão arbitrária) como ponto inicial. Para
exemplo, -x0 1/3 é válido. Se não for dado, x é gerado a partir do valor sigma para ECM,
ou aleatoriamente para P-1 e P + 1.

-sigma s
[ECM] Usar s (inteiro de precisão arbitrária) como gerador de curva. Se omitido, s is
gerado aleatoriamente.

-A a
[ECM] Usar a (inteiro de precisão arbitrária) como parâmetro de curva. Se omitido, é
gerado a partir do valor sigma.

-ir onda
[ECM, P-1, P + 1] Multiplique o ponto inicial por onda, que pode ser qualquer expressão válida,
possivelmente contendo o caractere especial N como espaço reservado para a entrada atual
número. Exemplo:

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

PASSO 2 PARÂMETROS

-k k
[ECM, P-1, P + 1] Executar k blocos na etapa 2. Para um determinado B2 valor, aumentando k
diminui o uso de memória da etapa 2, ao custo de mais tempo de CPU.

-arquivo de árvore lima
Armazena algumas tabelas de dados em arquivos de disco para reduzir a quantidade de memória ocupada em
etapa 2, às custas de E / S de disco. Os dados serão gravados em arquivos lima. 1, lima.2 etc.
Não funciona com o estágio rápido 2 para P + 1 e P-1.

-poder n
[ECM, P-1] Use x ^n para a extensão de Brent-Suyama (-poder 1 desativa o de Brent-Suyama
extensão). O polinômio padrão é escolhido dependendo do método e B2. Para P-1
e P + 1, desativa o estágio rápido 2. Para P-1, n deve ser igual.

-Dickson n
[ECM, P-1] Grau de uso-n Polinômio de Dickson para a extensão de Brent-Suyama. Para P-1 e
P + 1, desativa o estágio rápido 2. Como para -poder, n deve ser igual para P-1.

-máximo n
Use no máximo n megabytes de memória no estágio 2.

-ntt, -não-ntt
Habilite ou desabilite o código da Transformação Teórica Numérica para aritmética polinomial em
estágio 2. Com NTT, dF é escolhido para ser uma potência de 2 e é limitado pelo número
primos adequados que cabem em uma palavra de máquina (que é uma limitação apenas em 32 bits
sistemas). A variante -no-ntt usa mais memória, mas é mais rápida do que NTT com grandes
números de entrada. Por padrão, NTT é usado para P-1, P + 1 e para ECM em números de tamanho em
a maioria das 30 palavras de máquina.

SAÍDA

-q
Modo silencioso. As fatorações encontradas são impressas na saída padrão, com fatores
separados por espaços em branco, uma linha por número de entrada (se nenhum fator foi encontrado, o
o número de entrada é simplesmente copiado).

-v
Modo detalhado. Mais informações são impressas, mais -v opções aumentam a verbosidade. Com
um -v, o tipo de multiplicação modular usada, valor inicial x0, parâmetros da etapa 2
e progresso, curvas esperadas e tempo para encontrar fatores de diferentes tamanhos para ECM
são impressos. Com -v -v, o valor A para ECM e resíduos no final da etapa 1 e
passo 2 são impressos. Mais -v imprimir dados internos para depuração.

- timestamp
Imprima um carimbo de hora sempre que uma nova curva ECM ou execução P + 1 ou P-1 for processada.

MODULAR ARITMÉTICA OPÇÕES

Vários algoritmos estão disponíveis para multiplicação modular. O programa tenta encontrar o
o melhor para cada entrada; pode-se forçar um determinado método com as seguintes opções.

-mpzmod
Use a função mpz_mod do GMP (sub-quadrática para grandes entradas, mas induz alguma sobrecarga
para os pequenos).

-modmuln
Use a multiplicação de Montgomery (versão quadrática). Geralmente o melhor método para pequenos
entrada.

-redc
Use a multiplicação de Montgomery (versão subquadrática). Teoricamente ideal para
grande entrada.

-nobase2
Desative o código especial de base 2 (que é usado quando o número de entrada é um grande fator de
2 ^ n + 1 ou 2 ^ n-1, consulte -v).

-base2 n
Força o uso de código especial de base 2, o número de entrada deve dividir 2 ^n+1 se n > 0 ou 2 ^ |n| -1
if n <0.

ARQUIVO I / O

As opções a seguir permitem executar as etapas 1 e 2 separadamente, seja em
máquinas diferentes, em momentos diferentes, ou usando software diferente (em particular, George
O programa Prime95 / mprime de Woltman pode produzir a saída da etapa 1 adequada para retomar com
GMP-ECM). Também pode ser útil dividir a etapa 2 em várias execuções, usando o B2min-B2máx
opção.

-inp lima
Obter entrada do arquivo lima em vez da entrada padrão.

-Salve  lima
Salvar o resultado da etapa 1 em lima. Se lima existe, um erro é gerado. Exemplo: para realizar
apenas o passo 1 com B1= 1000000 no número composto no arquivo "c155" e salve seu
resultar no arquivo "foo", use

ecm -save foo 1e6 1 <c155

-salvar um lima
Como -Salve , mas anexa a arquivos existentes.

-currículo lima
Retomar resíduos de lima, lê a entrada padrão se lima é "-". Exemplo: para
execute a etapa 2 seguindo o cálculo da etapa 1 acima, use

ecm -currículo foo 1e6

-ponto de verificação lima
Grave periodicamente o resíduo atual no estágio 1 para lima. Em caso de falha de energia,
etc., o cálculo pode ser continuado com o -currículo opção.

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

LOOP MODA

O “modo de loop” (opção -c n) permite executar várias curvas em cada número de entrada. o
as opções a seguir controlam seu comportamento.

-c n
Realizar n é executado em cada número de entrada (o padrão é um). Esta opção é útil principalmente para
P + 1 (por exemplo com n= 3) ou para ECM, onde n poderia ser definido para o número esperado de
curvas para encontrar um fator de dígito d com um determinado limite da etapa 1. Esta opção é incompatível
com -retomar, -sigma, -x0. Dando -c 0 produz um loop infinito até que um fator seja
encontrado.

-1
No modo de loop, pare quando um fator for encontrado; o padrão é continuar até o
cofator é primo ou o número especificado de execuções é feito.

-b
Processamento por amplitude: no modo de loop, execute uma curva para cada número de entrada e, em seguida, um
segunda curva para cada um e assim por diante. Este é o modo padrão com -inp.

-d
Processamento de profundidade: no modo de loop, execute n curvas para o primeiro número, então n curvas
para o segundo e assim por diante. Este é o modo padrão com entrada padrão.

-ve n
No modo de loop, na segunda execução e nas seguintes, produza apenas expressões que tenham
a maioria n personagens. O padrão é -ve 0.

-i n
No modo de loop, incremento B1 by n após cada curva.

-I n
No modo de loop, multiplique B1 por um fator dependendo de n após cada curva. O padrão é um
que deve ser ideal em uma máquina, enquanto -I 10 poderia ser usado ao tentar
fatorar o mesmo número simultaneamente em 10 máquinas idênticas.

SHELL COMANDO EXECUÇÃO

Essas opções permitem a execução de comandos shell para complementar a funcionalidade do GMP-ECM.

-prpcmd cmd
Executar comando cmd para testar a primalidade se fatores e cofatores em vez de GMP-ECM's
próprias funções. O número a testar é passado via stdin. Um código de saída 0 é
interpretado como “provavelmente primo”, um código de saída diferente de zero como “composto”.

-faccmd cmd
Executa o comando cmd sempre que um fator é encontrado por P-1, P + 1 ou ECM. O número de entrada,
fator e cofator são passados ​​via stdin, cada um em uma linha. Isso poderia ser usado, por exemplo, para
enviar novos fatores automaticamente:

ecm -faccmd 'mail -s “$ HOSTNAME encontrou um fator”
[email protegido]'11e6 <cunningham.in

-idlecmd cmd
Executa o comando cmd antes de cada curva ECM, P-1 ou P + 1 tentativa em um número é iniciada.
Se o status de saída de cmd é diferente de zero, GMP-ECM termina imediatamente, caso contrário,
continua normalmente. GMP-ECM é interrompido enquanto cmd corre, oferecendo uma maneira de deixar
GMP-ECM hibernar, por exemplo, enquanto o sistema está ocupado.

DIVERSOS

-n
Execute o programa no modo “bom” (prioridade abaixo do normal).

-nn
Execute o programa no modo “very nice” (prioridade inativa).

-B2escala f
Multiplique o limite padrão da etapa 2 B2 pelo valor de ponto flutuante f. Exemplo: -B2escala
0.5 divide o padrão B2 por 2.

-estágio1tempo n
Adicionar n segundos para o estágio 1 vez. Isso é útil para obter o tempo esperado correto com -v if
parte da fase 1 foi feita em outra execução.

-cofdec
Força a saída do cofator em decimal (mesmo se expressões forem usadas).

-h, --Socorro
Exibe uma breve descrição do uso de ecm, parâmetros e opções de linha de comando.

-printconfig
Imprime os parâmetros de configuração usados ​​para a compilação e sai.

INPUT SINTAXE

Os números de entrada podem ter várias formas:

Números decimais brutos como 123456789.

Os comentários podem ser colocados no arquivo: tudo após “//” é ignorado, até o final de
linha.

Continuação da linha. Se uma linha terminar com um caractere de barra invertida “\”, é considerada como
continue na próxima linha.

Expressões aritméticas comuns podem ser usadas. Exemplo: 3 * 5 + 2 ^ 10.

Fatorial: exemplo 53!.

Multi-fatorial: exemplo 15! 3 means 15*12*9*6*3.

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

Primorial reduzido: exemplo 17 5 # means 5*7*11*13*17.

Funções: atualmente, a única função disponível é Phi (x, n).

SAIR STATUS

O status de saída reflete o resultado da última curva ECM ou P-1 / P + 1 tentativa do programa
realizada. Bits individuais significam eventos particulares, especificamente:

bocado 0
0 se o término do programa normal, 1 se ocorreu um erro

bocado 1
0 se nenhum fator adequado foi encontrado, 1 caso contrário

bocado 2
0 se o fator for composto, 1 se o fator for um primo provável

bocado 3
0 se o cofator for composto, 1 se o cofator for um provável primo

Assim, os seguintes valores de status de saída podem ocorrer:

0
Encerramento normal do programa, nenhum fator encontrado

1
erro

2
Fator composto encontrado, cofator é composto

6
Provável fator principal encontrado, o cofator é composto

8
Número de entrada encontrado

10
Fator composto encontrado, cofator é um provável primo

14
Provável fator primo encontrado, cofator é um provável primo

Use ecm online usando serviços onworks.net