I want to show that FACTORING $\le_P$ SPLITTING. First let us recall the definitions:
FACTORING: Given an integer $n \ge 2$ find its prime factorisation.
SPLITTING: Given an integer $n \ge 2$ find two non-trivial factors of it.
The core idea for FACTORING $\le_P$ SPLITTING is easy: Suppose we have an algorithm $\mathcal{A}$ that solves SPLITTING. We can use $\mathcal{A}$ to find two non-trivial factors, say $a$ and $b$, of $n$. We can then use the AKS-test on $a$ and $b$ to test them for primality in polynomial time. If both are prime we are done. Otherwise we can recursively use $\mathcal{A}$ on them to find non-trivial factors of $a$ and $b$ and repeatedly test them for primality with the AKS-algorithm until we found the prime factorisation of $n$.
But how can I estimate the runtime of the above scheme? Could you help me?
Consider a number as a list of prime factors. Each time you call split this list is partitioned in two parts and you recurse on both parts. The base case is a list of length 1 - a prime.
It should be obvious that the worst case performance happens when each split is as imbalanced as possible - only 1 prime is separated per split. In that case our performance is $O\left(l \cdot \left(s(n)+p(n)\right)\right)$ where $l$ is the length of our list and $s(n)$ is the time taken to split a number $n$ and $p(n)$ the time taken to check for primality.
But since each element in the list of prime factors must be at least two, we know that $2^l \leq n$ and thus $l \leq \log_2(n)$, and thus our total runtime is $O\left(\log n \cdot \left(s(n)+p(n)\right)\right)$.