Necesito un algoritmo más rápido que la multiplicación larga de Python normal actual.

Traté de encontrar una implementación de Karatsuba decente, pero no puedo.

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 ves, no es nada complicado, solo unas pocas multiplicaciones. Pero tiene que manejar números con hasta 100000 dígitos en menos de 2,5 segundos.

Me gustaría algún fragmento de una función o simplemente un enlace a alguna implementación de una función de multiplicación más rápida, o cualquier cosa que ayude.