[Sesse__]

Ah, of course, not only does it require O(n²) work to multiply, but n grows to n² for each iteration (n bits -> 2n bits). So that's why you get O(2^n) _total_ time.