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:


enter image description here enter image description here

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.

Best regards, Vadim

  • 1
    $\begingroup$ Please refrain yourself from cross-posting. This is considered not ethical in SO networks. Is cross-posting a question on multiple Stack Exchange sites permitted if the question is on-topic for each site?. Please keep one question alive. $\endgroup$ – kelalaka Jul 26 at 20:56
  • 3
    $\begingroup$ I’m voting to close this question because crossposted with Math.SE $\endgroup$ – kelalaka Jul 27 at 15:05
  • $\begingroup$ Any ideas about the question? $\endgroup$ – Vadim Jul 28 at 8:45
  • $\begingroup$ 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 $\endgroup$ – 111 Jul 28 at 20:25
  • $\begingroup$ @111 > I can't see where is this mod2N you wrote about Of course. It's a question how to insert mod in XGCD. > For the resultant the author suggests Lemma 3.10.2 Algorithm 3.10.6 follows from this lemma $\endgroup$ – Vadim Jul 29 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.