# Fast Extended Euclidean Algorithm in Harley's elliptic curves point counting method

Could you help me with Harley's norm computation algorithm that is based on the Fast Extended Euclidean Algorithm that was suggested by Harley in an email to NMBRTHRY list in 2002 and that described in Vercauteren's thesis pp 87-90:

https://pdfs.semanticscholar.org/c945/c98267db064b272c87a885fc5eeb764b0b2d.pdf

My implementation working correctly and fast for low degree polynomials without modulo and for high degree polynomials with modulo M, where M is a prime number greater than 2^N. But all I need - it's a resultant modulo 2^N (or 2^(Nc) due to Vercauteren's Remark 3.10.3) of two large polynomials. So I should include in routine mod 2^N (or mod 2^(Nc)...) instructions to avoid exponential coefficients' growing. But since the 2^N is not prime it's a problem - polynomials contain even coefficients and this leads to some even denominators - and for example multiplicative inverse 1/2 mod 2^N doesn't exist. Please tell me how to solve this problem?

How to adapt XCGD routine for correct mod 2^N calculation of resultant (norm)?

Thank you.

• I am not familiar with your question, but i had a quick look at this algorithm. As far as I can tell all the computations are in the field $K$ (I can't see where is this ${\rm mod}{2^N}$ you wrote about). For the resultant the author suggests Lemma 3.10.2 – 111 Jul 28 at 20:25