3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thank you, lucky that p-1-method worked. (+1 and accept) $\endgroup$ – Peter Oct 23 '19 at 9:02
  • $\begingroup$ Yes, it was indeed fun. You never know how the test ends up. $\endgroup$ – Martin Hopf Oct 23 '19 at 9:09
  • $\begingroup$ 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. $\endgroup$ – Peter Oct 23 '19 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.