Here's one approach which applies some basic definitions and long-established theory (without delving into those):
- Construct a non-deterministic polynomial-time turing machine which, when given an $n$ and $k$ accepts if there exists some $m$ where $1 < m < k$ and $m$ divides $n$, or rejects otherwise. Find out some particular polynomial which bounds the execution time of this machine.
Ideally you would use this turing machine to do a binary search on the set $\{1, \ldots, n\}$ to extract a factor of $n$. Then divide $n$ by this factor and repeat until you have a full factorization.
However, you don't have a way of executing non-deterministic turing machines directly. So instead do the following:
- For each query $(n, k)$, use the Cook/Levin reduction (See the Cook-Levin theorem) to construct a boolean circuit which is satisfiable iff the turing machine accepts $(n, k)$.
- Use the reduction from Circuit-SAT to 3-SAT to convert the circuit into a formula.
- Use the reduction from 3-SAT to Hamiltonian Path to convert the formula into a graph.
- Use your Hamiltonian Path oracle to tell you whether the graph has a hamiltonian path.
- Since reductions are answer-preserving, the answer it gives is the same as the answer to the question of whether $n$ has a non-trivial factor less than $k$.
An approach that probably leads to smaller graphs is to directly construct a boolean circuit (or formula) which is satisfiable iff $(n, k)$ is a yes-instance of the has-nontrivial-factor problem.