Potrzebuję algorytmu szybszego niż obecne normalne długie mnożenie Pythona.

Próbowałem znaleźć porządną implementację Karatsuba, ale nie mogę.

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

Jak widzisz, nie jest to nic skomplikowanego, tylko kilka powtórzeń. Musi jednak obsługiwać liczby do 100000 cyfr w czasie poniżej 2,5 sekundy.

Chciałbym jakiś fragment funkcji lub po prostu link do implementacji szybszej funkcji mnożenia lub czegoś, co pomaga.