Mark Dickinson <dicki...@gmail.com> added the comment:
> Then, it should be considerably faster Why would you expect that? Both algorithms involve a number of (bigint) operations that's proportional to log(p), so it's going to be down to the constants involved and the running times of the individual operations. Is there a clear reason for your expectation that the xgcd-based algorithm should be faster? Remember that Python has a subquadratic multiplication (via Karatsuba), but its division algorithm has quadratic running time. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue36027> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com