How long will the factorization of $4^{(4^4)}+555$ take making use of the large exponent?

Question

I tried to factor the number $$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$ digits, so it is within the scope of the number field sieve. But using an implementation for general numbers will still take considerable time. My question :

If I make use of the large exponent (as fas as I understood using especially the polynomial $x^{256}+555$ woule be useful) , how fast can the factorization be found ?

Unfortunately, I do not have a program using the multipolynomial quadratic sieve. Yafu rejects MPQS (the number is too big for that).

Answer 1

I used Yafu just out of the box from and get the answer within a minute or so (73s on my old i3). Here the banner if it helps

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) =======
=======             [email protected]                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983

and the 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