Мне нужен алгоритм быстрее, чем текущее нормальное длинное умножение Python.

Я пытался найти достойную реализацию Карацубы, но не могу.

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

Как видите, ничего сложного, только несколько умножений. Но он должен обрабатывать числа до 100000 цифр менее чем за 2,5 секунды.

Я хотел бы получить фрагмент функции или просто ссылку на какую-то реализацию более быстрой функции умножения или что-нибудь, что поможет.