Integer multiplication algorithm using a divide and conquer approach?

As homework, I should implement inte开发者_StackOverflow社区ger multiplication on numbers of a 1000 digits using a divide and conquer approach that works below O(n). What algorithm should I look into?

---

Schönhage–Strassen algorithm is the one of the fastest multiplication algorithms known. It takes O(n log n log log n) time.

Fürer's algorithm is the fastest large number multiplication algorithm known so far and takes O(n*log n * 2^O(log*n)) time.

I don't think any multiplication algorithm could take less than or even equal to O(n). That's simply not possible.

---

Take a look at the Karatsuba algorithm. It involves a recursion step which you can easily model with divide-and-conquer.