Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

#1

Ας εξετασθεί η αναγωγισιμότητα του πολυωνύμου

$\displaystyle{1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}}$

πάνω από το $\displaystyle{\mathbb{Z}_{3}[X]}$ .

(Χωρίς επίλυση συστημάτων και διάκριση περιπτώσεων)

#2

Ποιό τρόπο έχεις στο νου σου;

Ένας τρόπος είναι το τεστ Rabin:

(a) Το πολυώνυμο διαιρεί το x^7-1

που που διαιρεί το $x^{728}-1=x^{7\cdot 104}-1$ , κι άρα το $x^{3^6}-x=x(x^{728}-1)$

Επί του $\mathbb{F}_3$ είναι

Αφού $6=2\cdot 3$ , αρκει να δειχθεί ότι

(b) $\gcd(x^{3^{6/2}}-x,x^6+x^5+x^4+x^3+x^2+x+1)=1$

(b) $\gcd(^{3^{6/3}}-x,x^6+x^5+x^4+x^3+x^2+x+1)=1$ .

oι οποίες ισχύουν από τον αλγόριθμο του Ευκλείδη. (Κάνουμε τις διαιρέσεις).

Φιλικά,

Αχιλλέας

#3

Αχιλλέα μπορείς να μας πεις τι λέει το test του Rabin;

Γράφω την λύση που βρήκα. Έχει αρκετές ομοιότητες με του Αχιλλέα αλλά θέλω να κάνω περισσότερους ελέγχους. Αποφεύγω όμως τον αλγόριθμο του Ευκλείδη.

Ας υποθέσουμε πως δεν είναι ανάγωγο. Από θεωρία Galois, το σώμα ριζών του πολυωνύμου πάνω από το $\mathbb{F}_3$ πρέπει να είναι ένα από τα $\mathbb{F}_3,\mathbb{F}_{3^2},\mathbb{F}_{3^3},\mathbb{F}_{3^4},\mathbb{F}_{3^5}$ . Αλλά τότε το πολυώνυμο θα πρέπει να διαιρεί ένα από τα $x^3-x,x^9-x,x^{27}-x,x^{81}-x,x^{243}-x$ . Έστω $\alpha$ μια ρίζα του πολυωνύμου. Τότε $\alpha^7=1,\alpha \neq 1$ . Επειδή όμως το 7 δεν διαιρεί τα 2,8,26,80,242 το $\alpha$ δεν μπορεί να είναι ρίζα των πιο πάνω πολυωνύμων και άρα το αρχικό πολυώνυμο είναι ανάγωγο.

#4

Πολύ καλύτερη η λύση του Δημήτρη!

Τεστ Rabin:

Αν $f(x)\in \mathbb{F}_q[x]=n$ , τότε
f(x)

ανάγωγο αν και μόνο αν

(i) $\gcd(f(x), x^{q^{n/p}}-x)=1$ για κάθε πρώτο διαρέτη

του

.

και

(ii) το f(x)

διαιρεί το $x^{q^n}-x$ (στο $\mathbb{F}_q[x]$ ).

Αχιλλέας

#5

Το πολυώνυμο στην αρχή είναι το 7-κυκλοτομικό πολυώνυμο. Μήπως μπορεί αυτό να βοηθήσει ? Δηλαδή με κάποιο γενικευμένο Eiseinstein ή κάτι τέτοιο.

#6

smar έγραψε:Το πολυώνυμο στην αρχή είναι το 7-κυκλοτομικό πολυώνυμο. Μήπως μπορεί αυτό να βοηθήσει ? Δηλαδή με κάποιο γενικευμένο Eiseinstein ή κάτι τέτοιο.

Δε γνωρίζω την ύπαρξη "γενικευμένου" Eisenstein.

Δείτε

viewtopic.php?f=10&t=3601

Το ότι το πολυώνυμο είναι ανάγωγο επί του $\mathbb{Q}$ δε σημαίνει ότι είναι ανάγωγο επί του $\mathbb{Z}/3\mathbb{Z}$ .

Φιλικά,

Αχιλλέας

#7

Την γενίκευση του Eisenstein μπορεί να τη δει κανείς εδώ.

Δεν μπορεί ωστόσο να εφαρμοστεί εδώ,δεδομένου ότι το μόνο πρώτο ιδεώδες του $\displaystyle{\mathbb{Z}_{3}}$ είναι το $\displaystyle{\langle0\rangle}$ .

#8

Ένας άλλος πιθανός τρόπος είναι σχετικός με τον αλγόριθμο Berleκamp.

Ο αριθμός των ανάγωγων παραγόντων ενός πολυωνύμου ισούται με τη διάσταση της λεγόμενης Berleκamp υποάλγεβρας.

http://en.wikipedia.org/wiki/Berlekamp's_algorithm

Δε γνωρίζω πολλά όμως.

Χρειάζομαι να διαβάσω αρκετά για να μπορέσω να δώσω μια απάντηση με αυτό τον τρόπο...

Φιλικά,

Αχιλλέας

Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Re: Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Re: Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Re: Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Re: Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Re: Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Re: Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Re: Ανάγωγο (;) πολυώνυμο πάνω από πεπερασμένο σώμα

Μέλη σε σύνδεση