  We revisit the problem of integer factorization with number-theoretic
oracles, including a well-known problem: can we factor an integer $N$
unconditionally, in deterministic polynomial time, given the value of the Euler
totient $$\Phi$(N)$? We show that this can be done, under certain size
conditions on the prime factors of N. The key technique is lattice basis
reduction using the LLL algorithm. Among our results, we show for example that
if $N$ is a squarefree integer with a prime factor $p > $\sqrt$ N$ , then we
can recover p in deterministic polynomial time given $$\Phi$(N)$. We also shed
some light on the analogous problems for Carmichael's function, and the order
oracle that is used in Shor's quantum factoring algorithm.
