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

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.

• pull a three out of each and try to complete the cube ? – Roddy MacPhee Oct 13 '19 at 0:04
• Vepir checked the range upto $$2.3\cdot 10^{11}$$ without finding a prime factor. – Peter Oct 16 '19 at 20:50
• I ran your code up to $5\cdot 10^{11}$, no factors found. – Vepir Oct 20 '19 at 12:25

$$\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.

• Thank you, lucky that p-1-method worked. (+1 and accept) – Peter Oct 23 '19 at 9:02
• Yes, it was indeed fun. You never know how the test ends up. – Martin Hopf Oct 23 '19 at 9:09
• I started the p-1-method as well but had not the patience to wait. $p-1$ for prime numbers of this magnitude rarely is B-smooth for a "small" B, so we were lucky here. I noticed that you already reported the factor to factordb. – Peter Oct 23 '19 at 9:10