Eu estou precisando de um algoritmo mais rápido que a multiplicação longa do Python normal atual.

Eu tentei encontrar uma implementação decente da Karatsuba, mas não posso.

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()

Como você vê, não é nada complicado, apenas algumas multiplicações. Mas tem que lidar com números com até 100000 dígitos em menos de 2,5 segundos.

Eu gostaria de algum trecho de uma função ou apenas um link para alguma implementação de uma função de multiplicação mais rápida, ou qualquer coisa que ajude.