polynomial calculations over Z/Zp (for prime p)?
12-24-2013, 04:00 AM
Post: #1
 Jeff Nye Junior Member Posts: 3 Joined: Dec 2013
polynomial calculations over Z/Zp (for prime p)?
Hi,

Does the Prime have some way to compute with polynomials whose coefficients are in Z/pZ (for prime p)? If so, I'd be grateful for an example.

thank you,
Jeff
12-24-2013, 04:09 AM
Post: #2
 Han Senior Member Posts: 1,882 Joined: Dec 2013
RE: polynomial calculations over Z/Zp (for prime p)?
You have several ways of implementing $$\mathbb{Z}/\mathbb{Z}_p[x]$$. You can use vectors (of coefficients), actual symbolic expressions, or the "poly" type:
Code:
 p:=3; // examples below p1:=[ 12 13 -20 5 ] % p; p2:=(12x^3 + 13x^2 - 20x + 5) % p; p3:=poly[ 12 13 -20 5 ] % p;

Graph 3D | QPI | SolveSys
12-24-2013, 07:04 AM
Post: #3
 Alberto Candel Member Posts: 169 Joined: Dec 2013
RE: polynomial calculations over Z/Zp (for prime p)?
Hi,
What are the CAS settings for this to work? For example, quo() is documented in the xcas manual (2.25.3), but I cannot get it to work in the HP prime:
quo( (x^3+3x)%5,(2x^2+6x-5)%5)
should output -2x+1 but I get an error. Same if % is replaced by MOD (or mod). In fact, the HP prime example in the Help for MOD is 9 mod 5 results in an error. Maybe my CAS settings are wrong.
12-24-2013, 11:56 AM (This post was last modified: 12-24-2013 12:40 PM by Jeff Nye.)
Post: #4
 Jeff Nye Junior Member Posts: 3 Joined: Dec 2013
RE: polynomial calculations over Z/Zp (for prime p)?
(12-24-2013 04:09 AM)Han Wrote:
Code:
 p:=3; p1:=[ 12 13 -20 5 ] % p; p2:=(12x^3 + 13x^2 - 20x + 5) % p; p3:=poly[ 12 13 -20 5 ] % p;

These didn't work for me (using the latest firmware).

However, last night I stumbled upon the CAS %%(n,p) operator, which seems to be the % operator in xcas. With %% instead of %, example p1 worked fine. Example p2 produces a polynomial with non-modular coefficients. For example p3, I needed to say poly([ 12 13 -20 5 ] %% p).

Linear algebra seems to work with integers mod p. The expression [[4,3],[5,1]]%%3 defines a matrix of integers mod 3.
12-24-2013, 03:39 PM
Post: #5
 Alberto Candel Member Posts: 169 Joined: Dec 2013
RE: polynomial calculations over Z/Zp (for prime p)?
Yes, %% does the job. The single % is for percentage in the Prime. Very convoluted notation thou.
12-24-2013, 03:49 PM
Post: #6
 Han Senior Member Posts: 1,882 Joined: Dec 2013
RE: polynomial calculations over Z/Zp (for prime p)?
(12-24-2013 11:56 AM)Jeff Nye Wrote:
(12-24-2013 04:09 AM)Han Wrote:
Code:
 p:=3; p1:=[ 12 13 -20 5 ] % p; p2:=(12x^3 + 13x^2 - 20x + 5) % p; p3:=poly[ 12 13 -20 5 ] % p;

These didn't work for me (using the latest firmware).

However, last night I stumbled upon the CAS %%(n,p) operator, which seems to be the % operator in xcas. With %% instead of %, example p1 worked fine. Example p2 produces a polynomial with non-modular coefficients. For example p3, I needed to say poly([ 12 13 -20 5 ] %% p).

Linear algebra seems to work with integers mod p. The expression [[4,3],[5,1]]%%3 defines a matrix of integers mod 3.

Thank you for the corrections

Graph 3D | QPI | SolveSys
12-24-2013, 04:10 PM
Post: #7
 Alberto Candel Member Posts: 169 Joined: Dec 2013
RE: polynomial calculations over Z/Zp (for prime p)?
I wonder if one has a choice of residue system used. The %% uses the minimal residue system mod n. Is there a way to display results using the common (or least) residue system mod n (that is, {0,1,...,n-1})? The negative signs combined with the double %% make the results rather cumbersome to read.
12-25-2013, 07:55 AM
Post: #8
 parisse Senior Member Posts: 1,236 Joined: Dec 2013
RE: polynomial calculations over Z/Zp (for prime p)?
You can remove the %% by the %% 0 command, then run irem on each coefficient.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)