Αλγόριθμος Κάντορ-Ζασενχάους

Στην υπολογιστική άλγεβρα, ο **αλγόριθμος Κάντορ-Ζασενχάους** είναι μια μέθοδος παραγοντοποίησης πολυωνύμων πάνω σε πεπερασμένα σώματα (που ονομάζονται επίσης **σώματα Γκαλουά**).

Ο αλγόριθμος αποτελείται κυρίως από υπολογισμούς εκθετικοποίησης και πολυωνυμικού GCD. Εφευρέθηκε από τους Νταβίδ Γ. Κάντορ και Χανς Ζασενχάους το 1981.

Είναι αναμφισβήτητα ο κυρίαρχος αλγόριθμος για την επίλυση του προβλήματος, αφού αντικατέστησε τον προηγούμενο αλγόριθμο του Μπέρλεκαμπ του 1967. Σήμερα υλοποιείται σε πολλά συστήματα υπολογιστικής άλγεβρας όπως το PARI/GP.

## Επισκόπηση

### Ιστορικό

Ο αλγόριθμος Κάντορ-Ζασενχάους δέχεται ως είσοδο ένα πολυώνυμο f(x) χωρίς τετράγωνα (δηλ. ένα χωρίς επαναλαμβανόμενους παράγοντες) βαθμού *n* με συντελεστές σε ένα πεπερασμένο σώμα \mathbb{F}_q του οποίου οι μη αναγώγιμοι πολυωνυμικοί παράγοντες είναι όλοι ίσου βαθμού (υπάρχουν αλγόριθμοι για την αποτελεσματική παραγοντοποίηση αυθαίρετων πολυωνύμων σε ένα γινόμενο πολυωνύμων που ικανοποιούν αυτές τις συνθήκες, επί παραδείγματι, το f(x)/\gcd(f(x),f'(x)) είναι ένα τετραγωνικό πολυώνυμο με τους ίδιους παράγοντες με το f(x), οπότε ο αλγόριθμος Κάντορ-Ζασενχάους μπορεί να χρησιμοποιηθεί για την παραγοντοποίηση αυθαίρετων πολυωνύμων).  Δίνει ως έξοδο ένα πολυώνυμο g(x) με συντελεστές στο ίδιο σώμα τέτοιο ώστε το g(x) να διαιρεί το f(x).  Ο αλγόριθμος μπορεί στη συνέχεια να εφαρμοστεί αναδρομικά σε αυτούς και σε επόμενους διαιρέτες, μέχρι να βρεθεί η διάσπαση του f(x) σε δυνάμεις μη αναγώγιμων πολυωνύμων (υπενθυμίζοντας ότι ο δακτύλιος των πολυωνύμων πάνω σε οποιοδήποτε σώμα είναι ένα μοναδικό πεδίο παραγοντοποίησης).

Όλοι οι πιθανοί παράγοντες της f(x) περιέχονται στον δακτύλιο παραγόντων
R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}. Αν υποθέσουμε ότι η f(x) έχει μη αναγώγιμους παράγοντες p_1(x), p_2(x), \ldots, p_s(x), όλοι βαθμού *d*, τότε αυτός ο παραγοντικός δακτύλιος είναι ισομορφικός με το ευθύ γινόμενο παραγοντικών δακτυλίων S = \prod_{i=1}^s \frac{\mathbb{F}_q[x]}{\langle p_i(x) \rangle}.  Ο ισομορφισμός από το *R* στο *S*, ας πούμε \phi, αντιστοιχεί ένα πολυώνυμο g(x) \in R στην *s*-νιάδα των αναγωγών του modulo κάθε ένα από τα p_i(x), δηλαδή αν:

: 
\begin{align}
g(x) & {} \equiv g_1(x) \pmod{p_1(x)}, \\
g(x) & {} \equiv g_2(x) \pmod{p_2(x)}, \\
& {} \  \  \vdots \\
g(x) & {} \equiv g_s(x) \pmod{p_s(x)},
\end{align}


τότε \phi(g(x) + \langle f(x) \rangle) = (g_1(x) + \langle p_1(x) \rangle, \ldots, g_s(x) + \langle p_s(x) \rangle).  Είναι σημαντικό να σημειωθεί το εξής σε αυτό το σημείο, καθώς θα έχει κρίσιμη σημασία αργότερα στον αλγόριθμο:  Δεδομένου ότι τα p_i(x) είναι το καθένα μη αναγωγίσιμο, κάθε ένας από τους παραγοντικούς δακτυλίους σε αυτό το άμεσο άθροισμα είναι στην πραγματικότητα ένα σώμα.  Αυτά τα σώματα έχουν το καθένα βαθμό q^d.

### Κεντρικό αποτέλεσμα
Το βασικό αποτέλεσμα που διέπει τον αλγόριθμο Κάντορ-Ζασενχάους είναι το εξής:  Αν a(x) \in R είναι ένα πολυώνυμο που ικανοποιεί: a(x) \in R:

: a(x) \neq 0, \pm 1 

: a_i(x) \in \{0,-1,1\}\text{ for }i=1,2,\ldots, s,

όπου a_i(x) είναι η αναγωγή του a(x) modulo p_i(x), όπως προηγουμένως, και αν οποιαδήποτε δύο από τα ακόλουθα τρία σύνολα είναι μη κενά:

: A = \{ i \mid a_i(x) = 0 \}, 

: B = \{ i \mid a_i(x) = -1 \}, 

: C = \{ i \mid a_i(x) = 1 \}, 

τότε υπάρχουν οι ακόλουθοι μη τετριμμένοι παράγοντες της f(x):

: \gcd(f(x),a(x)) = \prod_{i \in A} p_i(x),

: \gcd(f(x),a(x)+1) = \prod_{i \in B} p_i(x),

: \gcd(f(x),a(x)-1) = \prod_{i \in C} p_i(x).

### Αλγόριθμος

Ο αλγόριθμος Κάντορ-Ζασενχάους υπολογίζει πολυώνυμα του ίδιου τύπου με το a(x) παραπάνω, χρησιμοποιώντας τον ισομορφισμό που συζητήθηκε στην ενότητα Ιστορικό.  Προχωράει ως εξής, στην περίπτωση που το σώμα \mathbb{F}_q είναι περιττού χαρακτηριστικού (η διαδικασία μπορεί να γενικευτεί σε σώματα χαρακτηριστικού 2 με αρκετά απλό τρόπο.  Επιλέγουμε ένα τυχαίο πολυώνυμο b(x) \in R τέτοιο ώστε b(x) \neq 0, \pm 1 .  Ορίζουμε m=(q^d-1)/2 και υπολογίζουμε το b(x)^m.  Εφόσον το \phi είναι ισομορφισμός, έχουμε (χρησιμοποιώντας τον καθιερωμένο πλέον συμβολισμό μας):

:\phi(b(x)^m) = (b_1^m(x) + \langle p_1(x) \rangle, \ldots, b^m_s(x) + \langle p_s(x) \rangle).

Τώρα, κάθε b_i(x) + \langle p_i(x)\rangle είναι στοιχείο ενός σώματος τάξης q^d, όπως σημειώθηκε προηγουμένως.  Η πολλαπλασιαστική υποομάδα αυτού του σώματος έχει τάξη q^d-1 και έτσι, εκτός αν b_i(x)=0, έχουμε b_i(x)^{q^d-1}=1 για κάθε *i* και συνεπώς b_i(x)^m = \pm 1 για κάθε *i*.  Αν b_i(x)=0, τότε φυσικά b_i(x)^m=0.  Επομένως, το b(x)^m είναι ένα πολυώνυμο του ίδιου τύπου με το a(x) παραπάνω.  Περαιτέρω, αφού b(x) \neq 0, \pm1, τουλάχιστον δύο από τα σύνολα A,B και *C* είναι μη κενά και υπολογίζοντας τα παραπάνω GCD μπορούμε να λάβουμε μη τετριμμένους παράγοντες.  Δεδομένου ότι ο δακτύλιος των πολυωνύμων πάνω από ένα σώμα είναι ένας ευκλείδειος τομέας, μπορούμε να υπολογίσουμε αυτά τα GCD χρησιμοποιώντας τον ευκλείδειο αλγόριθμο.

## Εφαρμογές

Μια σημαντική εφαρμογή του αλγορίθμου Κάντορ-Ζασενχάους είναι ο υπολογισμός διακριτών λογαρίθμων πάνω σε πεπερασμένα σώματα τάξης πρώτης δύναμης.  Ο υπολογισμός διακριτών λογαρίθμων είναι ένα σημαντικό πρόβλημα στην κρυπτογραφία δημόσιου κλειδιού. Για ένα σώμα τάξης πρώτης δύναμης, η ταχύτερη γνωστή μέθοδος είναι η μέθοδος υπολογισμού δεικτών, η οποία περιλαμβάνει την παραγοντοποίηση των στοιχείων του σώματος. Εάν αναπαραστήσουμε το σώμα τάξης πρώτης δύναμης με τον συνήθη τρόπο -δηλαδή ως πολυώνυμα πάνω στο σώμα βάσης πρώτης τάξης, αναγόμενα modulo σε ένα μη αναγώγιμο πολυώνυμο κατάλληλου βαθμού- τότε πρόκειται απλώς για πολυωνυμική παραγοντοποίηση, όπως προβλέπεται από τον αλγόριθμο Κάντορ-Ζασενχάους.

## Εφαρμογή σε συστήματα άλγεβρας υπολογιστών

Ο αλγόριθμος Κάντορ-Ζασενχάους υλοποιείται στο σύστημα άλγεβρας υπολογιστών PARI/GP ως η συνάρτηση factormod() (πρώην factorcantor()).

## Εξωτερικοί σύνδεσμοι
*English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
*Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
*ΑΓΓΛΟΕΛΛΗΝΙΚΟ. ΛΕΞΙΚΟ. ΜΑΘΗΜΑΤΙΚΩΝ. ΟΡΩΝ Αριάδνη Καλογερόπουλου. Μίλτος Γκίκας — Δ. Καραπαννακης — Μ. Λάμπρου. 
* Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
* Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
* Θεωρία Αριθμών και Εφαρμογές
* Υπολογιστική Θεωρία Αριθμών
* Καμπυλότητες και γεωμετρία του Riemann σε διαφορίσιμες πολλαπλότητες Εθνικό Αρχείο Διδακτορικών Διατριβών
* Μέθοδοι μηχανικής μάθησης βασισμένες σε έλεγχο μονοτροπικότητας Εθνικό Αρχείο Διδακτορικών Διατριβών
*  Παράμετροι και Στατιστικά. Διωνυμική και Κανονική Κατανομή
* Wolfram Mathematica Online Integrator
*  A Table of Integrals of the Error Functions

## Δείτε επίσης
* Απαγορευτική αρχή του Πάουλι
* Μορφοκλασματική διάσταση
* Ομοπαραλληλική γεωμετρία
* Αλγεβρική θεωρία αριθμών
* Άρθουρ Στάνλεϋ Έντινγκτον
* Μοναδιαία βηματική συνάρτηση
* Σουμπραμανιάν Τσαντρασεκάρ
* Ευκλείδειος χώρος
* Υπερβολική γεωμετρία
* Βαθμός (γραμμική άλγεβρα)
* Εφαρμοσμένα μαθηματικά
* Υπολογιστική ρευστοδυναμική
* Καμπυλότητα Γκάους
* Καρτεσιανό σύστημα συντεταγμένων
* Θεμελιώδες θεώρημα αριθμητικής
* Αλγεβρική γεωμετρία
* Σώμα διασπάσεως
* Συνήθης διαφορική εξίσωση
* Γραμμική απεικόνιση
* Νοεροί υπολογισμοί

## Βιβλιογραφία
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 

## Παραπομπές

*
*
*
*
*
*
*
*.   **English translation** (of 2nd revised edition):  *(Later republished in English by Springer under the title "Algebra".)*
*

## Πηγές
* 
* 
* 
*
*
*
*
* Wendelin Degen, Lothar Profke: *Grundlagen der affinen und euklidischen Geometrie.* Teubner, Stuttgart 1976, ISBN 3-519-02751-8.
* Hans Freudenthal: *Mathematik als pädagogische Aufgabe.* Band 1. Klett, Stuttgart 1973, ISBN 3-12-983220-3.
* Thomas W. Hungerford: *Algebra* (= *Graduate Texts in Mathematics.* Bd. 73). 5th printing. Springer, New York NY u. a. 1989, ISBN 0-387-90518-9.

Κατηγορία:Θεωρία σωμάτων
Κατηγορία:Αλγεβρική θεωρία αριθμών
Κατηγορία:Θεωρία δακτυλίων
Κατηγορία:Αφηρημένη άλγεβρα