¿Cuánto tiempo tomará la factorización de$4^{(4^4)}+555$ el uso del exponente grande?

Question

Traté de factor el número de $$4^{(4^4)}+555=4^{256}+555$$ It is composite and using the ECM-method (elliptic-curve-method) I did not find a non-trivial factor yet. I think the smallest prime factor has more than $30$ digits. The number has $155$ dígitos, por lo que está dentro del alcance del campo número de tamiz. Pero el uso de una aplicación para números general todavía va a tardar un tiempo considerable. Mi pregunta :

Si puedo hacer uso de el gran exponente (como fas por lo que he entendido, utilizando especialmente el polinomio $x^{256}+555$ woule ser útil) , ¿qué tan rápido puede el de la factorización de ser encontrado ?

Por desgracia, no tengo un programa mediante el multipolynomial cuadrática tamiz. Yafu rechaza MPQS (el número es demasiado grande para eso).

Answer 1

Usé Yafu recién sacado de la caja y obtuve la respuesta en aproximadamente un minuto (73 s en mi i3 anterior). Aquí la pancarta si ayuda.

 08/22/17 23:20:24 v1.34.5 @ MARVIN, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected        Intel(R) Core(TM) i3-2350M CPU @ 2.30GHz
detected L1 = 32768 bytes, L2 = 3145728 bytes, CL = 64 bytes
measured cpu frequency ~= 2275.735680
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983
 

y el factoring

 >> n=4^256+555
n = 1340780792994259709957402499820584612747936582059239337772356144372176403007
3546976801874298166903427690031858186486050853753882811946569946433649006084651

>> factor(n)

fac: factoring 13407807929942597099574024998205846127479365820592393377723561443
72176403007354697680187429816690342769003185818648605085375388281194656994643364
9006084651
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C155
rho: x^2 + 2, starting 1000 iterations on C155
rho: x^2 + 1, starting 1000 iterations on C155
pm1: starting B1 = 150K, B2 = gmp-ecm default on C155
ecm: 30/30 curves on C155, B1=2K, B2=gmp-ecm default
ecm: 74/74 curves on C155, B1=11K, B2=gmp-ecm default
ecm: 176/214 curves on C155, B1=50K, B2=gmp-ecm default, ETA: 14 sec
Total factoring time = 73.5642 seconds


***factors found***

P37 = 2727068085850358403268887244594373731
P118 = 4916565156370767546727800957533087600205143937757201924147473931815890701
063359800699421633668871056803859756916007321