Even and perfect-power preprocessing returns a proper factor

If $N$ is even, $2\mid N$. Since $N\ge 4$, $1<2<N$, so the returned integer is a proper factor.

Suppose the precheck finds $N=b^e$ with $2\le b\le N$ and $e\ge 2$. Then $N=b{b}^{e-1}$, so $b\mid N$ by [F1]. The power $b^{e-1}\ge 2$, so $N=b{b}^{e-1}\ge 2b>b$; hence $1<b<N$ and its explicit divisibility verification returns a proper factor.

Conversely, suppose $N=b^e$ with $b\ge 2$ and $e\ge 2$. If $N$ is even, step 1.1 shows that the earlier even branch returns $2$, so the root search is not reached. Now suppose $N$ is odd. Then the root-search branch is reached, and $2^e\le b^e=N\le 2^n$, so $e\le n$ and the loop includes this exponent. If the algorithm has not already returned on an earlier exact-power match in this root search, then for this fixed $e$, if $2\le x<y$, $y^e-x^e=(y-x){\sum }_{j=0}^{e-1}{y}^{e-1-j}{x}^j>0,$ because the factor and every summand are positive by [F2]. Hence $x\mapsto x^e$ is strictly increasing, so binary search on $[2,N]$ finds $b$; capping values above $N$ at $N+1$ preserves each comparison with $N$. If the algorithm already returned on an earlier root-search match, that match was itself an exact-power representation of $N$, and step 1.2 shows that its returned base is a proper factor. Thus the odd perfect-power input returns a proper factor through the root search, while the even case is handled by step 1.1.

There are at most $n$ exponents and at most $n$ binary-search comparisons per exponent because $N\le 2^n$. Each comparison uses at most $O(\log n)$ capped multiplications of $O(n)$-bit integers, hence $O(n^2\log n)$ bit operations by [F3]. The total is $O(n^4\log n)=O(n^5)$ for $n\ge 2$, proving the claimed bound.