If it happens in a polynomial number of steps on average, but you might get unlucky, https://en.wikipedia.org/wiki/ZPP_(complexity) https://en.wikipedia.org/wik

If it happens in a polynomial number of steps on average, but you might get unlucky, https://en.wikipedia.org/wiki/ZPP_(complexity) https://en.wikipedia.org/wiki/ZPP_(complexity) If it can just take as long as they want, then the probabilistic part is basically irrelevant and you're probably looking at https://en.wikipedia.org/wiki/PSPACE https://en.wikipedia.org/wiki/PSPACE In any case, I very much doubt they'd made any real breakthrough in factoring numbers.