Is there any alternative for extended euclidean algorithm to perform modulo division?
For increasing speed, you should use of  "Barrett reduction" and "Montgomery multiplication". For more detail you can see "Guide to Elliptic Curve Cryptography". Also you can use "MAGMA". This program is  one of the best and fastest program for elliptic curve.