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

Hi there,

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 XGCD routine for correct mod 2^N calculation of resultant (norm)?

Thank you.

mod prime version of XGCD:

XGCD.mw