1. Testing pathological code (e.g. bad argument values) isn't going to drive your implementation that much, so leave that for later. Try the simplest successful case first.
2. If you really can't think how to test it, sketch out the algorithm (e.g. code-first) and figure out how you could test that algorithm. If the algorithm is 50 lines long, pretend it is 50 method calls instead: how would you test each of those method-calls? What does each line/method take as input, what is its output? Then try to go back to test-first and re-implement the code. Don't worry about public / private methods. Once your are "done" or at good stopping point, figure out which classes should own which methods, then refactor them to cooperating classes where most of the work is in public methods of each class. Move the tests to be closer to the code they test.
3. A class where there is only one or two public methods and a dozen or more private methods is exhibiting the code smell "Iceberg Class".
4. If the complexity resides in a third-party library or framework, concentrate your tests on YOUR code, assuming the third-party library or framework is correct. Unless, of course, the third-party library or framework needs tests (because it is unreliable), in which case test how your code uses the library or framework to get expected results.
5. You might have the test create the output, you verify that the output is correct manually, and then you save that output as a "gold standard" to test against automatically. I've done that for image-processing... it broke rarely, when the jpg library I was using changed.
