Here is a probabilistic method that borrows ideas from an
extension of the Rabin-Miller primality test
which can be used for factoring pseudoprimes $n$
that are not strong pseudoprimes. The extension is described in
Miller 1976,
which is one of the references given in Bill Dubuque's answer.
It works when given some multiple $m$ of $\lambda(n)$
where $\lambda$ is Carmichael's lambda function.
We assume that $n$ can be represented as $n=pq$ with unknown odd coprime
$p,q>1$. The goal is to find a nontrivial factor of $n$.
- Set $h$ to the largest odd divisor of $m$ by dividing out $2$ as many times
as possible.
- Choose a random $a\in\{2,3,\ldots,n-2\}$.
- Compute $g=\gcd(a,n)$. This is probably $1$ for most $a$, but if not,
you have found a nontrivial factor $g$ of $n$, so you are done.
More importantly, the following steps implicitly assume that $\gcd(a,n)=1$.
- Compute $b = a^h\bmod{n}$.
We know that the multiplicative order of $b\pmod{n}$ is $1$
or some power of $2$. That order is also the least common multiple of
the orders$\bmod{p}$ and$\bmod{q}$.
We hope that those orders differ, which is likely (see below).
In the following, we try to find the smallest order.
- Compute $g=\gcd(b-1,n)$.
Remark: If $b\equiv1\pmod{p}$, then $g$ will be divisible by $p$.
And if $b\not\equiv1\pmod{q}$ yet, then $g$ will not be divisible by $q$,
so $g$ will be a nontrivial divisor.
- If $g=1$, replace $b$ with $b^2\bmod{n}$ and go to step 5.
This will not loop forever because $b$ is known to reach $1\pmod{n}$
with a finite number of repetitions of step 6. That brings us to$\ldots$
- If $g=n$, the multiplicative orders of $a^h\pmod{p}$ and $a^h\pmod{q}$
are equal. Then go to step 2, we need another $a$.
- If you end up here, $g$ is a nontrivial factor of $n$.
How likely is it that the orders of $a^h$ are different$\bmod{p}$ and$\bmod{q}$?
Let $n=p_1^{e_1}\cdots p_k^{e_k}$ with pairwise distinct odd primes $p_i$
and positive integer exponents $e_i$.
Write $\phi(p_i^{e_i}) = 2^{t_i} u_i$ with odd $u_i$
and set $t_{\text{min}} = \min\{t_1,\ldots,t_k\} \geq 1$.
Note that $t_i$ does not depend on $e_i$.
Note also that each $u_i$ divides the given $h$.
The $a$ that do not yield nontrivial factors of $n$ are those with
order $\text{(odd number)}\cdot2^j$ in the unit group$\bmod{p_i^{e_i}}$,
with the same $j$ for every $i$.
Therefore such $j$ cannot exceed $t_{\text{min}}$.
For each such $j$, there are exactly $\phi(2^j)\,u_i = 2^{\max\{0,j-1\}} u_i$
non-yielding $a$ in the unit group$\bmod{p_i^{e^i}}$,
namely, the primitive $2^j$-th roots of the $u_i$ solutions
to $X^{u_i}\equiv 1\pmod{p_i^{e_i}}$.
In the unit group$\bmod{p_i^{e_i}}$,
those $a$ have a density of $2^{\max\{0,j-1\} - t_i}$.
By chinese remaindering, we find that the non-yielding $a$
in the unit group$\bmod{n}$ have density
$$\begin{align}
\rho &= \sum_{j=0}^{t_{\text{min}}} \prod_{i=1}^k 2^{\max\{0,j-1\} - t_i}
\\ &= \sum_{j=0}^{t_{\text{min}}} 2^{k\max\{0,j-1\} - (t_1 + \cdots + t_k)}
\\ &= 2^{-(t_1 + \cdots + t_k)}
\left(1 + \frac{2^{k\,t_{\text{min}}} - 1}{2^k - 1}\right)
\\ &\leq 2^{-k\,t_{\text{min}}}\cdot 2^{k\,(t_{\text{min}}-1)+1}
\\ &= 2^{-(k-1)}
\end{align}$$
Thus for composite $n$, the success probability is at least $50\%$
for each $a$ that makes it to step 4.