Working with polynomials (or at least trying to)

[absinthe]

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?

Thanks in advance.

[Justin C. Walker]

On Apr 4, 2015, at 17:29 , absinthe 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.

Answered, possibly, on sage-devel...

--
Justin C. Walker, Curmudgeon at Large
Institute for the Absorption of Federal Funds
-----------
My wife 'n kids 'n dogs are gone,
I can't get Jesus on the phone,
But Ol' Milwaukee's Best is my best friend.
-----------

[absinthe]

Justin thanks for your reply. When I realised that I have posted to dev I deleted the message and I posted to support. It looks like that you had already answered there. Since it might help others which will look at support and not dev, I copy and paste your dev reply here.

2. Yes no problem :)

1. The reason I resulted to Integers(p) was that I couldn't have the proper cooefficients when using GF.

For the same "configuration" I tried the following

Trying with the following 

p=32

N=100

FFQ.<t> = GF(q)#FiniteField(q)

PR.<x> = PolynomialRing(K)

Q.<xx> = PR.quotient(x^N - 1)

pp=Q.random_element()

while True:

    try:

        ppInv=pp.inverse_mod(xx^N-1)

        break

    except:

        pp=Q.random_element()

print (pp*ppInv).mod(x^N-1)

I get to a dead end as inverse_mod returns me a not implemented error (sage-6.3-x86_64-Linux)

On Sunday, April 5, 2015 at 3:59:42 AM UTC+3, Justin C. Walker wrote:

On Apr 4, 2015, at 17:25 , absinthe 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. 

I'm not sure how familiar you are with this stuff, so forgive me if this is already clear to you. 

1. When "p" is a prime power, Z/pZ is not a field (it's a ring, but not a domain).  If you want to deal with coefficients in a field, then you will want to use "GF(p)", not "Integers(p)".  And a minor syntactic wrinkle to beware of is that when "p" (as above) is a prime power, and not a prime, you need a second argument, to be used as the name of the "generator" of F_p (as an extension of F_q, q being the prime in p). 

2. Also, in computer algebra systems, you have to be careful about parentheses, to get what you want.  In particular, "X^N-1" and X^(N-1)" are not the same. 

If this isn't helpful, we can look at this some more. 

HTH 

Justin 

-- 
Justin C. Walker 
Curmudgeon at Large 
Director 
Institute for the Enhancement of the Director's Income 
-- 
Build a man a fire and he'll be warm 
 for a night. 
Set a man on fire and he'll be warm 
 for the rest of his life. 

[Dima Pasechnik]

On Sunday, 5 April 2015 13:20:49 UTC+1, absinthe wrote:

Justin thanks for your reply. When I realised that I have posted to dev I deleted the message and I posted to support. It looks like that you had already answered there. Since it might help others which will look at support and not dev, I copy and paste your dev reply here.

2. Yes no problem :)

1. The reason I resulted to Integers(p) was that I couldn't have the proper cooefficients when using GF.

For the same "configuration" I tried the following

Trying with the following 

p=32

N=100

FFQ.<t> = GF(q)#FiniteField(q)

PR.<x> = PolynomialRing(K)

Q.<xx> = PR.quotient(x^N - 1)

pp=Q.random_element()

while True:

    try:

        ppInv=pp.inverse_mod(xx^N-1)

        break

    except:

        pp=Q.random_element()

print (pp*ppInv).mod(x^N-1)

I get to a dead end as inverse_mod returns me a not implemented error (sage-6.3-x86_64-Linux)

What is K there? And what is q?
They are not defined in your code above.

As well,
it's not clear why you try to call inverse_mod(), as pp is already an element
of the quotient ring modulo (x^N-1).

But pp^{-1} need not exist, still, as Q is not a field for each N>1.

[absinthe]

Sorry for the leftovers I copied and pasted...

With the following I manage to create polynomials whose coefficients are in Z_32 and they are modulo x^N-1. 

N=100

q=32

PR.<xx> = Zmod(q)[]

Q.<x> = PR.quotient(xx^N - 1)

pp=Q.random_element()

The problem is that  pp.inverse_mod(x^N-1) does not work (NotImplementedError). Similarly, for pp^(-1) I get the error 

NotImplementedError: The base ring (=Ring of integers modulo 32) is not a field

I'm working on sage-6.3-x86_64-Linux

Justin proposed to use GF(), however, if I use the following (fixed the garbages of the previous code):

q=32

FFQ.<t> = GF(q)

PR.<x> = PolynomialRing(FFQ)

Q.<xx> = PR.quotient(x^N - 1)

My coefficients belong to a finite field of size 32 I can invert etc, but the coeffs are not in Z_32 as I would like to.

Thanks for your help

[Justin C. Walker]

On Apr 5, 2015, at 10:58 , absinthe wrote:

> Sorry for the leftovers I copied and pasted...
> With the following I manage to create polynomials whose coefficients are in
> Z_32 and they are modulo x^N-1.

[snip]

> My coefficients belong to a finite field of size 32 I can invert etc, but
> the coeffs are not in Z_32 as I would like to.
> Thanks for your help

Maybe it would help us if you could explain what you are trying to accomplish. Why, in particular, do you want coefficients in Z/32Z. This is not a field, and it contains zero-divisors, which can certainly interfere with obtaining inverses.

Justin

--
Justin C. Walker, Curmudgeon at Large

Director
Institute for the Enhancement of the Director's income
-----------
Question 43:
What if the hokey pokey
really *is* what it’s all about?
--

[David Joyner]

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.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[absinthe]

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) 

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...

[Justin C. Walker]

On Apr 5, 2015, at 11:39 , absinthe wrote:

> 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...

Thanks for your clarifications. I think the issue at the root of your problem is that Sage's algorithm implementing "foo.inverse_mod(bar)" uses the Euclidean algorithm (use the "?" or "??" operators as follows to see details:
sage: foo.inverse_mod? or foo.inverse_mod??)

I believe that the Euclidean algorithm assumes the underlying ring is Euclidean (which in turns requires no zero divisors). In the Hoffstein-et al article, they mention using an "easy modification" of said algorithm to compute inverses, an exercise, I suppose, for the really-interested reader.

HTH

Justin

--
Justin C. Walker

Curmudgeon-at-large
Director

Institute for the Absorption of Federal Funds
----

186,000 Miles per Second
Not just a good idea:
it's the law!
----

[absinthe]

Justin I believe that you are right so I will try to re-implement it. Thanks for your help. 

David, thank you as well. The answer I believe is somewhere close to both of you.

Some sips of absinthe will help me get this through or at least provide the illusion that I did it ;)

[Justin C. Walker]

On Apr 7, 2015, at 09:49 , absinthe wrote:

> Justin I believe that you are right so I will try to re-implement it.
> Thanks for your help.
> David, thank you as well. The answer I believe is somewhere close to both
> of you.
> Some sips of absinthe will help me get this through or at least provide the
> illusion that I did it ;)

Be careful with that. As it is written: absinthe makes the heart go wander...

--
Justin C. Walker, Curmudgeon at Large

Institute for the Absorption of Federal Funds

-----------
I'm beginning to like the cut of his jibberish.
-----------