Prime factoring $2^{22} + 1$ the sneaky way?

$22=4\cdot5+2$, so $2^{22}+1$ has an Aurifeuillean factorisation: $$2^{22}+1=(2^{11}-2^6+1)(2^{11}+2^6+1)=1985×2113$$ The numbers are now within the point where trial division with primes up to $97$ will easily find all factors. In fact, other than the $5$ that appears with the naive factorisation, these are the only prime factors: $$2^{22}+1=5×397×2113$$

It is well known that $2048 = 2^{11}$, by the famous game 2048, so I won't count that as "excessively long computation".

So $2^{22}+1=4194305$. You've already got a factor $5$: $$2^{22}+1 = 5\times838861.$$

Now to find other factors of $2^{22}+1$, you need to know which primes $p$ satisfies $$2^{22}\equiv -1 \pmod p.$$ So let's tackle the easier: $$2^{44}\equiv 1 \pmod p.$$ This is likely to happen when $p = 44k + 1$. And $k \equiv 0,2 \pmod 3$ to make $p$ a prime. And we have the fast exponentiation algorithm that enables us to quickly find $2^{44}$ modulo a number, taking $k=9$ as an example:

$$\begin{align} 2^{44} &\equiv 4^{22}\\ &\equiv 16^{11}\\ &\equiv (-141)^{5} \times 16 \\ &\equiv 31^{2} \times 16 \times (-141)\\ &\equiv 167 \times 16 \times (-141)\\ &\equiv -290 \times 141 \\ &\equiv 1 \pmod 397 \end{align}$$

This says $397 \mathop{|} 2^{44}-1$, so possibly $397 \mathop{|} 2^22+1$. And by division we see that it is indeed the case. $$2^{22} + 1 = 5 \times 397 \times 2113.$$

And 2113 is prime.