I am reading this paper, but I will write everyting I need for my question here.
So, long story short, we have a proth-number $n$, i.e. $n = h\cdot 2^k+1$ for odd $h<2^k$.
We are looking for integers $D$ such that the Jacobi symbol
$$
\left(\frac{D}{n}\right) \neq 1.
$$
I could already prove that
$$ \left(\frac{D}{n}\right) = \left(\frac{n}{D}\right),$$
so we can reduce $n \pmod D$.
Now I know that
$$ h\cdot 2^k+1 \equiv (h\pmod D)\cdot 2^{k\mod ord_p(2)}\pmod D,$$
where $ord_p(2)$ is the order of $2$ modulo $D$.
So of course we are interested in finding a $D$ with a possibly low order, because if $D$ is a solution for a $k$, then it's a solution for every $k\pmod{ord_p(2)}$.
What I do not understand is this: In (4.1) of the paper, they say:
But I do not get the link. Why is it useful to factorize $2^u-1$?
Any prime $D$ that divides $2^u-1$ satisfies $2^u-1\equiv 0\pmod D$, which means that $2^u\equiv 1\pmod D$, i.e. $\mathrm{ord}_p(2)\mid u$.