Mnożenie liczb całkowitych o nieograniczonej długości

Witam, przede mną taki problem :

Specyfikacja : Napisać program mnożący dwie liczby całkowite o nieograniczonej ilości cyfr w każdej
Technologia : Java

Jedyne rozwiązanie, jakie przychodzi mi do głowy, to po prostu każdą z takich całkowitych liczb przetrzymywać w stringu, bądź tablicy znakowej. Implementacja dodawania jest prosta, bo wystarczy od końca komórka po komórce zamieniać stringi na inty i dodawać, pamiętając o bicie przesunięcia, a wynik będzie miał maksymalnie o 1 więcej cyfr, niż każdy ze składników.

Jednakże w przypadku mnożenia sytuacja jest już bardziej skomplikowana. Raczej metoda typu mnożenie pod kreską odpada, z prostego względu:

dajmy na to, że chcemy pomnożyć ze sobą dwie liczby o ogromnej wartości. Jeżeli żadna z liczb nie będzie mieścić się w jakimś całkowitym typie danych, to nawet nie będzie można w pętli ich dodawać.

Ma ktoś jakiś pomysł jak można by to skutecznie zrealizować? Albo słyszał kiedyś o jakimś algorytmie używanym do czegoś takiego?

ZTCW to Javowy BigInteger używa właśnie mnożenia pod kreską.

Wersja łatwa - mnożenie pod kreską. Spokojnie da się zaimplementować w kilkanaście minut (nie wiem o co Ci chodzi z dodawaniem - po prostu jeśli suma dodawania > max cyfra to robisz przeniesienie na wyższą cyfrę... jak w szkole).
Wada to złożoność (O(n</sup>2))

Wersja trudna - FFT. Pierwszy materiał jaki znalazłem w google (nie wygląda na zbyt przejrzysty, może znajdziesz coś lepszego) - http://www.aimath.org/news/congruentnumbers/howtomultiply.html .
Jest zauważalnie trudniejszy w implementacji, ale za to działa w czasie (O(n log n))