The goal is to factor $N = 319375146$ without a calculator, using only pencil and paper in under 30 minutes. The exact question is "What is the 4 digit prime factor of 319375146?" This comes from a 2021 math contest, but the solution can't be found online. Searching the number doesn't help.
As it turns out, $N = 2 \cdot 3 \cdot 73 \cdot 571 \cdot 1277.$ You can divide out $2, 3$ easily. With more time, you can divide out $73,$ leaving $571 \cdot 1277 = 729167,$ which is too big to go further. Is there any way to recognize one of the numbers as the output of a polynomial and then factor that polynomial?
For example, $1061106 = p(101)$ for $p(x) = x^3+3x^2+2x.$ We can factor $p(x) = x(x+1)(x+2)$ and as a result factor the original number.
There are a few options for where to detect a polynomial: $N, \frac{N}{2 \cdot 3} = 53229191, \frac{N}{2 \cdot 3 \cdot 73} = 729167.$ I suppose if you're evil, the solution could rely on looking at $\frac{N}{3} = 106458382.$ In any case, none of the numbers fit with a natural polynomial. Can anyone see one?
There is a technique (due to Fermat, I believe?) to attack this using the difference of squares factorization. $729167=571\cdot 1277=(924+353)(924-353)=924^2-353^2$, and we can search for a way to express the number as a difference of two squares as follows. The first square bigger than 729167 is $854^2$. Our starting point is then writing $729167=854^2-149$. Unfortunately, 149 is not a perfect square, so we want to move on and find the difference from $855^2$. But we can do this quickly by noting that $855^2=(854+1)^2=854^2+2(854)+1$, and so $855^2-729167=149+2(854)+1=1858$. But this isn't a perfect square either. So we move on to $856^2-729167=1858+2(855)+1=3769$. Continuing for $924-854=70$ steps, we find our factorization by using nothing more than doubling, addition, and the ability to detect perfect squares.
So we are able to look for $729167=x^2-b$ for many different values of b, searching for one where $b$ is a perfect square.
This technique works best when there are two factors of our number that are both close to the square root, but we got somewhat unlucky, as one of our prime factors of 729167 was close to twice the other. We could have accounted for this possibility by running two computations in parallel: trying to factor 729167 but also trying to factor $2\cdot 729167$. However, we run into a small hiccup if we try to use this technique on an even number that isn't a multiple of 4: if we have $n=ab$, where $a$ and $b$ are different parities, and we try to write $ab=x^2-y^2=(x+y)(x-y)$, then since $(x+y)-(x-y)=2y$, if $y$ is a whole number, then $x+y$ and $x-y$ have the same parity. However, we can repair this by trying to factor $8\cdot 729167$, into two even numbers.
In this case, we would have started with $8\cdot 729167 =2416^2-3720$, and in order to find the factorization $8\cdot 729167 =(4\cdot 571)(2\cdot 1277)=2419^2-135^2$ would have only taken 3 steps.
Tossing in more copies of 2 allows you to quickly factor numbers of the for $n=pq$ where $p/q$ is close to other powers of $2$ besides $2^0$ or $2^1$.