Dear all, thanks for your replies. In general I don't want others to do the dirty work for me, so I ask the actual problem. Anyway, since I have to give more details to get the actual help... The case is that I want to implement NTRU (see here for details <http://en.wikipedia.org/wiki/NTRUEncrypt>) As you see, I have to construct polynomials, similar to the ones I was refering to and compute their inverse... So it is definite that I'm going to have zero-divisors and the like...
On Sunday, April 5, 2015 at 9:07:33 PM UTC+3, David Joyner wrote: > > On Sat, Apr 4, 2015 at 8:29 PM, absinthe <kpa...@gmail.com <javascript:>> > wrote: > > Dear all, > > > > I'm trying to work with polynomials modulo x^N-1 whose coefficients > belong > > to Z_p (If it helps p is a power of a prime). I know that I'm doing > > something wrong, but I cannot figure out what so any help is welcome. > > p=32 > > N=100 > > ZZp.<x> = PolynomialRing(Integers(p)) > > #find an element that can be inverted > > pp=ZZp.random_element() > > while True: > > try: > > ppInv=pp.inverse_mod(x^N-1) > > break > > except: > > pp=ZZp.random_element() > > #multiply the inverses > > print (pp*ppInv).mod(x^N-1) > > > > The result is not always 1 (sometimes it is though). So the question is > why? > > From their definition, the two polynomials are inverse but their product > is > > not 1? Am I interprenting wrong? > > > > Maybe you want a polynomial f(x) in GF(p)[x] with the property that > f(x) has an inverse in GF(p)[x]/(x^N - 1)? An f(x) in GF(p)[x] has this > property > if an only if gcd(f(x), x^N - 1) = 1. Moreover, you can find the > inverse of f(x) in this > ring using xgcd. All this is implemented in Sage. > > > > Thanks in advance. > > > > -- > > You received this message because you are subscribed to the Google > Groups > > "sage-support" group. > > To unsubscribe from this group and stop receiving emails from it, send > an > > email to sage-support...@googlegroups.com <javascript:>. > > To post to this group, send email to sage-s...@googlegroups.com > <javascript:>. > > Visit this group at http://groups.google.com/group/sage-support. > > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
