O fatorador inteiro tweetável mais rápido

17

A tarefa é encontrar um fator não trivial de um número composto.

Escreva um código que encontre um fator não trivial de um número composto o mais rápido possível, sujeito a que seu código não tenha mais que 140 bytes. A saída deve ser apenas o fator que você encontrou.

Seu código pode receber e fornecer resultados de qualquer maneira que seja conveniente, incluindo, por exemplo, como argumentos para uma função.

Casos de teste que listam todos os fatores (você só precisa gerar um)

187: 11 17
1679: 23 73
14369648346682547857: 1500450271 9576890767
34747575467581863011: 3628273133 9576890767
52634041113150420921061348357: 2860486313 5463458053 3367900313
82312263010898855308580978867: 264575131106459 311111111111113
205255454905325730631914319249: 2860486313 71755440315342536873 
1233457775854251160763811229216063007: 1110111110111 1000000000063 1111111999999
1751952685614616185916001760791655006749: 36413321723440003717 48112959837082048697

Não pontuarei sua resposta no seguinte caso de teste difícil, que pode ser de interesse para o teste:

513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471

Ponto

Sua pontuação é o tempo combinado para fatorar todos os casos de teste acima com uma penalidade de 10 minutos para cada fatoração com falha (todos arredondados para o segundo mais próximo). Seu código também deve funcionar para outros números inteiros, ou seja, não deve apenas codificar essas respostas.

Vou parar o seu código após 10 minutos.

Se duas pessoas obtiverem a mesma pontuação, a primeira resposta vence.

Restrições

Seu código não pode usar nenhuma função interna ou de biblioteca que execute a fatoração de número inteiro. Você pode assumir que a entrada leva menos de 256 bits. Todos os números de entrada serão compostos.

Como vou cronometrar?

Vou literalmente rodar time ./myprogno meu sistema Ubuntu para fazer o tempo; por isso, forneça também um programa completo para rodar que inclua qualquer função que você definiu.

Uma observação para idiomas compilados

O tempo de compilação não deve demorar mais de 1 minuto na minha máquina.

Isso é realmente possível?

Se você ignorar as restrições de espaço, cada uma poderá ser fatorada em menos de 2 segundos no meu computador usando código Python puro + pypy.

Então, o que é um algoritmo de fatoração não trivial?

O algoritmo rho de Pollard é rápido e adequado para jogar golfe. É claro que existem muitas outras maneiras de fatorar um número inteiro também.

Ainda mais rápido é a peneira quadrática . Parece um sério desafio espremer isso em 140 bytes.

Pontuações principais

  • SEJPM , 10 minutos de penalidade no último caso de teste + 16 segundos em Haskell

fonte
Então, podemos receber um número como 2 ** 1024?
Conor O'Brien
@ ConorO'Brien Você não receberá nada com mais dígitos do que os casos de teste.
Então, em termos de precisão, nada mais que 256 bits.
Conor O'Brien
Para uma entrada como 4, a saída deve ser 2ou 2, 2?
Mr. Xcoder
11
@AndersKaseorg Atualizei a pergunta seguindo sua sugestão. Obrigado.

Respostas:

9

Haskell, 100 97 91 89 87 72 67 Bytes

Experimente Online!

-3 bytes graças a @flawr
-6 bytes graças a @flawr novamente
-2 bytes graças a @flawr novamente
-2 bytes graças a um conjunto otimizado de parâmetros
-1 byte graças a @flawrs mais um tempo
-14 bytes graças a requisitos para ter apenas que gerar um fator
-5 bytes graças a @AndersKaseorg

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

Isso funciona para os 5 primeiros casos de teste em um tempo imperceptível.
Isso provavelmente expirará no maior caso de teste.

Em geral, isso geralmente retornará um fator não trivial no tempo proporcional à raiz quadrada do menor fator.
Ele não funcionará em todas as entradas porque não varia o polinômio e a detecção do caso excepcional é difícil de fazer em 140 bytes.
Também não produzirá a fatoração completa, mas sim um fator não trivial e a divisão da entrada por esse fator.
Também não classificará os fatores por tamanho.

O método utilizado é o Pollard-Rho-Factoring com o valor inicial padrão de 2 (com o x^2+1polinômio padrão aplicado uma vez) e o fator constante polinomial não padrão de 7 (porque 1não funcionou com 1679) para todas as avaliações posteriores.

Programa completo ( factor.hs):

import System.Environment(getArgs)

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

main= do
      args <- getArgs
      print$f (read $ head args :: Integer)

Compile como $ ghc factor.hs(necessidades ghcinstaladas).
Executar como $ ./factor <number>.

Exemplo de execução:

$ ./factor 187
11

Código não destruído:

f n=g 5 (s 5)
   where s x=mod(x*x+7)n
         g a b = if d>1 then d else g(s a)(s(s b))
               where d=gcd(b-a)n

Calcula o fator não trivial chamando gcom valores iniciais. O polinômio é pré-aplicado em 2 aqui e reaplicado no resultado (5), para que a entrada para g(em uma cláusula "where" ) sempre possa ser usada prontamente para o teste de MDC. g(a versão golfed usa infix #) tenta calcular um fator não trivial d(na cláusula where na versão não golfed, em linha na golfed) como a diferença entre as duas entradas para g, se for bem-sucedido, retorna o referido fator , mais tentativas. Aqui, ele pode gerar ncomo saída se, a==be assim retornar apenas um fator trivial, a abordagem adequada para lidar com isso seria variar os valores iniciais desse evento ou alterar o polinômio.

SEJPM
fonte
|1<2=s a#(s$s b)poderia ser substituído por |c<-s b=s a#s cAcho :): (também por que você não postar uma TIO link?)
flawr
Atualizei a pergunta seguindo as sugestões de comentários. Agora você só precisa gerar um fator e os números são garantidos para serem compostos.
3
PS: por que estamos golfe, este não é mesmo código-golf
flawr
4
Você agora tem 53 bytes em que para implementar um algoritmo factoring ainda mais sofisticado :)
11
Além disso, você pode retirar abs , pois bé sempre não-negativo. (Talvez você quis dizer abs$b-a, mas gcdaceita argumentos negativos e sempre produz um resultado não negativo.) Isso reduz a menos de metade de um tweet!
Anders Kaseorg
6

Pari / GP , 137 bytes, ~ 5 segundos

Usando as operações de curva elíptica incorporadas do GP (e alguns ajustes de parâmetros ocultos) :

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

ecm é uma função que (deve) retornar um fator. Experimente online!

Teste:

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

{
ns = [
  187,
  1679,
  14369648346682547857,
  34747575467581863011,
  52634041113150420921061348357,
  82312263010898855308580978867,
  205255454905325730631914319249,
  1233457775854251160763811229216063007,
  1751952685614616185916001760791655006749
  ]
}

test(n) = {
    d = ecm(n);
    if (!(1<d && d<n && n%d==0), error(d));
    print(n, ": ", d)
}

apply(test, ns)

quit

Ungolfed:

ecm(n) = {
  iferr(if(n%2 == 0, 2,
           n%3 == 0, 3,
           for(a = 1, n,
               /* x^3 + A*x + B = y^2 */
               E = ellinit(Mod([a, a^2-a-1], n)); /* [A, B] */
               x0 = [1, a]; /* [x, y] */
               B = ceil(4^a^0.5); /* ~ exp(sqrt(log(p))), p ~= exp(a) */
               print("a=", a, ", B=", B);
               ellmul(E, x0, lcm([1..B]))
              )
          ),
         ERR, gcd(n, lift(Vec(ERR)[3] /* = Mod(d, n) */)),
         errname(ERR)=="e_INV")
}

Infelizmente, lidar com os fatores 2 e 3 usa muitos bytes. Bytes que poderiam ter sido usados ​​para adicionar um estágio 2:

ecm(n)=iferr(for(a=1,n,Y=X=ellmul(E=ellinit(Mod([a,1],n)),[0,1],(B=ceil(4^a^0.5))!);for(z=0,9*B,Y=elladd(E,Y,X))),e,gcd(n,lift(Vec(e)[3])))
japh
fonte
1

Axioma, 137 bytes 9 minutos

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

acima da função p () que implementaria algo p-1 para fatorar abaixo o que copiar em um arquivo para teste na função p ()

-- one has to copy this below text in a file name for example file.input
-- in one window where there is Axiom one could write 
-- )read C:\absolutepathwherethereisthatfile\file
-- and call the function test()
-- test()
-- the first character of all function and array must be afther a new line "\n"
)cl all
)time on
vA:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

-- this would try to factor n with p-1 Pollard method
pm1(n:PI):PI==
   j:=1;a:=3;s:=n^.2
   repeat
      b:=j:=nextPrime(j)
      repeat(b<s=>(b:=b*j);break)
      a:=powmod(a,b,n)
      d:=gcd(a-1,n);d>1 or j>n=>break
   d

test()==(for i in 1..#vA repeat output [vA.i, p(vA.i)])

resultados aqui:

(5) -> test()
   [187,11]
   [1679,73]
   [14369648346682547857,9576890767]
   [34747575467581863011,9576890767]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,311111111111113]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
   [1751952685614616185916001760791655006749,36413321723440003717]
                                                               Type: Void
                              Time: 496.78 (EV) + 53.05 (GC) = 549.83 sec
RosLuP
fonte
Você poderia explicar exatamente como executar esse código na linha de comando no ubuntu, por favor? Instalei o axioma e criei um arquivo chamado foo.ax com o seu código não-golfe.
@Lembik 1) renomeie fop.ax em foo.input 2) execute o Axiom em um terminal ou xterm 3) escreva no terminal Axiom o comando a seguir ") leia C: absolutepath \ foo" 4) escreva no terminal do Axiom a chamada para funcionar test (). Isto é como fazer no Windows, a pista parece-me um aberto sessão Axiom e carregar o arquivo com ") ler" comando
RosLuP
@Lembik se houver algum problema com os arquivos, acho que também ficaria bem: 1) execute o Axiom 2) escreva) tempo no <return> no programa Axiom 3) copie e cole e pressione return em cada "copiar e colar" no programa Axiom: variedade vA, a função p () e test () 4) no teste Axiom programa write () <retorno>
RosLuP
@Lembik então, quanto tempo leva?
RosLuP
1

Axioma, 10 minutos + 31 segundos

A(a)==>a:=(a*a+7)rem n;z(n)==(p:=a:=b:=101;for i in 1..repeat(A(a);A(b);A(b);p:=mulmod(p,a-b,n);i rem 999<9=>(p:=gcd(p,n);p>1=>break));p)

z () é a função rho, uma função de 137 bytes; ungolfed z () e chame-o de rho (). Supõe-se que gcd (0, n) = n, para que o loop pare e retorne para a falha n.

)time on    
rho(n)==
  p:=a:=b:=101
  for i in 1..repeat
          A(a);A(b);A(b)
          p:=mulmod(p,a-b,n)
          i rem 999<9=>(p:=gcd(p,n);p>1=>break)
  p

va1:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]
p1()==(for i in 1..#va1-1 repeat output [va1.i,z(va1.i)]) 

os resultados (z () são válidos para todos, exceto o último número 1751952685614616185916001760791655006749 permanecem sem fatoração (10 minutos))

(6) -> p1()
   [187,17]
   [1679,23]
   [14369648346682547857,1500450271]
   [34747575467581863011,3628273133]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,264575131106459]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
                                                               Type: Void
                                 Time: 30.38 (EV) + 1.38 (GC) = 31.77 sec

(8) -> z(1679)
   (8)  23
                                                    Type: PositiveInteger
                                                              Time: 0 sec
RosLuP
fonte
0

Python 3 , 100 99 bytes, 45 40 39 segundos + 10 minutos de penalidade

import math
def f(n):
 x=y=2;d=1
 while d<2:y=y*y+1;x,y=1+x*x%n,y*y%n+1;d=math.gcd(x-y,n)
 return d

Experimente online!

Usa Pollard-Rho com valor inicial 2 e polinômio x ^ 2 + 1.

teto
fonte
Você pode usar pow(com o terceiro argumento) para melhorar sua velocidade de execução.
Mbomb007