As the tests get more specific, the code gets more generic

Those kata examples (and the transformation rules expressed therein), like most of the kata I've seen, always feel limited. Take the prime number kata as an example. The implementation is only usable for small input values. Suppose one of the questions is the prime factors of 231-1. This is something which could be done by hand - in the 1770s, Euler worked out that it was prime - but it's not going to be something which the author's son would likely be assigned.

The author writes: "My premise is that if you choose the tests and implementations that employ transformations that are higher on the list, you will avoid the impasse."

What is the transformation technique which would take the existing prime solution and make it something which handles all integers in the range 1 to 231-1 in "reasonable" time?

Similarly, what is the set of transformations which converts the naive string searching algorithm - that being the one which most easily passes the simple unit tests at the start of a TDD project - and ends up with Boyer–Moore or Knuth–Morris–Pratt?

Or from the quadratic "grade school" algorithm for multiplying two large numbers to the Karatsuba algorithm?

I have a hard time believing that a simple set of transformations apply for all of those cases. I'm easily convinced; just show me the steps.

I do realize that most problems don't require anything more than non-trivial algorithm development. But it feels like TDD is at best a support method for testing complex algorithm development. If it cannot be used to design new algorithms, then what design techniques should people use instead?