Can I accelerate the trial division because of the large exponents?

Question

I want to find a factor of the number $$3^{3^{14}}+3^{3^{13}}+1$$ and I wonder whether the large exponents ($\ 3^{14}\ $ and $\ 3^{13}\ $) allow an acceleration of the trial division. A primality test and methods like pollard-rho or ECM are slow for this number because it has $$2\ 282\ 057$$ digits. According to my calculations , there is no factor below $\ 10^{10}\ $. Maybe someone doublechecks this or even extends the search range. For PARI/GP-users, here is the code :

? f(p)=lift(Mod(3,p)^(3^14)+Mod(3,p)^(3^13)+1)
%35 = (p)->lift(Mod(3,p)^(3^14)+Mod(3,p)^(3^13)+1)
? forprime(q=1,10^9,if(f(q)==0,print1(q," ")))
?

The range $\ 1-10^9\ $ can easily be changed.

Motivation : I currently try to collect primes of the form $$n^{n^{k+1}}+n^{n^k}+1$$ with positive integers $n$ and $k$. For $\ n=1\ $, this is trivially prime ($\ 3\ $), if $\ n\ $ is of the form $\ 3k+1\ $ or even, the expression is divisibe by $\ 3\ $ and if $n$ is of the form $\ 3k+2\ $ , the expression contains algebraic factors because of $\ x^2+x+1\mid x^n+x+1\ $ in this case. Such algebraic factors do not seem to exist however for my given number.

Answer 1

$\large p_{23} = 49538146230969121798249$ is a 23 digit factor of $\large n = 3^{3^{14}}+3^{3^{13}}+1$.

Vepir runned trial division already to $5 \cdot 10^{11}$. As Peter mentioned ECM and Pollard-RHO are quite time consuming.

So I thought about methods which can give me an answer in maybe a day or two. Finally I decided to run a test with the PM1-method which provides a factor $p$ of $n$ if the factors of $p-1$ are $B$-smooth.

The PM1()-function with computer algebra system PARI/GP:

PM1(n,b,B)={my(g,E=round(5*log(B))!*factorback(primes([2,B])));g=gcd(lift(Mod(b,n)^E-1),n);if(g>1&g<n,g)};

Parameters are $n$ the number to find a factor, $b$ the base for testing and $B$ the upper bound. For a 2 million digit $n$ and $B$ up to $10^6$ make sure enough memory is allocated. 256MB should do:

allocatemem(256*10^6)

For Peters $n$, $b$ should be coprime to $3$ so I choosed $b=2$. For $B=10^6$ I estimated a running time for about 3 days. So I tested some smaller $B$ and finally suceeded with $B=3\cdot 10^5$:

PM1(3^3^14+3^3^13+1,2,3*10^5)
time = 22h, 4min, 5,406 ms.
%# = 49538146230969121798249

The factors of $p_{23}-1= 2^3\cdot 3\cdot 11^2\cdot 79\cdot 2437\cdot 13217\cdot 50129\cdot 133733$.

$133733$ is the largest factor. Thus $p_{23}-1$ is $133733$-smooth.

As you can see I quite overestimated $B$. with $B=1.5\cdot 10^5$ you can get the same result in about 10 hours.

$$$$

There are a lot of other examples where the PM1-method returns a factor in reasonable time. For example:

PM1(2^17387-1,3,3*10^4)

returns a 22-digit factor in about 2 seconds.