Consider Fast Doubling. It is an optimized matrix multiplication approach. It is of logarithmic complexity, ignoring the cost of large integer multiplication.

The actual numerical multiplication (for large values) is not linear but can be sped up using the Fast Fourier Transform (with integers represented as polynomials), although this is a low-level optimization that only makes sense in lower-level languages (than Python).

In practice, it is often easier (and more efficient) to use polished and well-optimized libraries like GMP (in C/C++) for arbitrary precision arithmetic.