Αλγόριθμος του Μπέρλεκαμπ

Στα μαθηματικά, ιδίως στην υπολογιστική άλγεβρα, ο **αλγόριθμος του Μπέρλεκαμπ** είναι μια γνωστή μέθοδος για την παραγοντοποίηση πολυωνύμων πάνω σε πεπερασμένα σώματα (επίσης γνωστά ως σώματα Γκαλουά). Ο αλγόριθμος αποτελείται κυρίως από αναγωγή πινάκων και υπολογισμούς πολυωνυμικών GCD. Εφευρέθηκε από τον Έλγουιν Μπέρλεκαμπ το 1967. Ήταν ο κυρίαρχος αλγόριθμος για την επίλυση του προβλήματος μέχρι τον αλγόριθμο Κάντορ-Ζάσενχαους του 1981. Σήμερα υλοποιείται σε πολλά γνωστά συστήματα υπολογιστικής άλγεβρας.

## Αναλυτικά

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

Όλοι οι πιθανοί παράγοντες της f(x) περιέχονται στον δακτύλιο παραγόντων
:R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}.
Ο αλγόριθμος επικεντρώνεται σε πολυώνυμα g(x) \in R που ικανοποιούν την ισοτιμία:
:g(x)^q \equiv g(x) \pmod{f(x)}.\,
Αυτά τα πολυώνυμα σχηματίζουν μια υποάλγεβρα του R (η οποία μπορεί να θεωρηθεί ως ένας διανυσματικός χώρος διαστάσεων n πάνω από το \mathbb{F}_q, που ονομάζεται *υποάλγεβρα  Μπέρλεκαμπ*.  Η υποάλγεβρα Μπέρλεκαμπ παρουσιάζει ενδιαφέρον επειδή τα πολυώνυμα g(x) που περιέχει ικανοποιούν

:f(x) = \prod_{s \in \mathbb{F}_q} \gcd(f(x),g(x)-s).

Γενικά, δεν θα είναι κάθε GCD στο παραπάνω γινόμενο ένας μη τετριμμένος παράγοντας του f(x), αλλά μερικοί είναι, παρέχοντας τους παράγοντες που αναζητάμε.

Ο **αλγόριθμος του Μπέρλεκαμπ** βρίσκει πολυώνυμα g(x) κατάλληλα για χρήση με το παραπάνω αποτέλεσμα υπολογίζοντας μια βάση για την υποάλγεβρα Μπέρλεκαμπ.  Αυτό επιτυγχάνεται μέσω της παρατήρησης ότι η υποάλγεβρα Μπέρλεκαμπ  είναι στην πραγματικότητα ο πυρήνας ενός συγκεκριμένου n \times n πίνακα πάνω από το \mathbb{F}_q, ο οποίος προκύπτει από τον λεγόμενο πίνακα Μπέρλεκαμπ του πολυωνύμου, που συμβολίζεται \mathcal{Q}. Αν \mathcal{Q}=[q_{i,j}] τότε q_{i,j} είναι ο συντελεστής του j-th δυναμικού όρου στην αναγωγή του x^{iq} modulo f(x), δηλ:

:x^{iq} \equiv q_{i,n-1}x^{n-1} + q_{i,n-2}x^{n-2} + \ldots + q_{i,0} \pmod{f(x)}.\,

Με ένα συγκεκριμένο πολυώνυμο g(x) \in R, ας πούμε:

:g(x) = g_{n-1}x^{n-1}+g_{n-2}x^{n-2} + \ldots + g_0,\,

μπορούμε να συσχετίσουμε το γραμμικό διάνυσμα:

:g = (g_0, g_1, \ldots, g_{n-1}).\,

Είναι σχετικά απλό να δούμε ότι το γραμμικό διάνυσμα g\mathcal{Q} αντιστοιχεί, με τον ίδιο τρόπο, στην αναγωγή του g(x)^q modulo f(x). Συνεπώς, ένα πολυώνυμο g(x) \in R βρίσκεται στην υποάλγεβρα Μπέρλεκαμπ αν και μόνο αν g(\mathcal{Q}-I)=0 (όπου I είναι ο n \times n ταυτοτικός πίνακας), δηλ. αν και μόνο αν βρίσκεται στο μηδενικό χώρο του \mathcal{Q}-I.

Υπολογίζοντας τον πίνακα \mathcal{Q}-I και ανάγοντάς τον σε μορφή μειωμένης γραμμής echelon και στη συνέχεια διαβάζοντας εύκολα μια βάση για τον μηδενικό χώρο, μπορούμε να βρούμε μια βάση για την υποάλγεβρα Μπέρλεκαμπ και συνεπώς να κατασκευάσουμε πολυώνυμα g(x)  σε αυτόν. Στη συνέχεια πρέπει να υπολογίσουμε διαδοχικά GCDs της παραπάνω μορφής μέχρι να βρούμε έναν μη τετριμμένο παράγοντα.  Δεδομένου ότι ο δακτύλιος των πολυωνύμων πάνω από ένα σώμα είναι μια ευκλείδεια περιοχή, μπορούμε να υπολογίσουμε αυτά τα GCD χρησιμοποιώντας τον ευκλείδειο αλγόριθμο.

## Εννοιολογική αλγεβρική εξήγηση

Με λίγη αφηρημένη άλγεβρα, η ιδέα πίσω από τον αλγόριθμο του Μπέρλεκαμπ γίνεται εννοιολογικά σαφής. Παρουσιάζουμε ένα πεπερασμένο σώμα  \mathbb{F}_q , όπου  q = p^m  για κάποιο πρώτο p, ως  \mathbb{F}_p[y]/(g(y)) . Μπορούμε να υποθέσουμε ότι  f(x) \in \mathbb{F}_q[x]  είναι χωρίς τετράγωνα,  με τη λήψη όλων των πιθανών pth ριζών και στη συνέχεια τον υπολογισμό του gcd με την παράγωγο του. .

Τώρα, ας υποθέσουμε ότι  f(x) = f_1(x) \ldots f_n(x)  είναι η παραγοντοποίηση σε μη αναγώγιμα. Τότε έχουμε έναν ισομορφισμό δακτυλίου  \sigma: \mathbb{F}_q[x]/(f(x)) \to \prod_i \mathbb{F}_q[x]/(f_i(x)) ,δίνεται από το κινεζικό θεώρημα υπολοίπων. Η κρίσιμη παρατήρηση είναι ότι ο αυτομορφισμός Φρομπένιους  x \to x^p   αντιμετατίθεται με   \sigma , έτσι ώστε αν συμβολίσουμε   \text{Fix}_p(R) = \{ f \in R : f^p = f \} , τότε   \sigma   περιορίζεται σε έναν ισομορφισμό \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) \to \prod_{i = 1}^n \text{Fix}_p( \mathbb{F}_q[x]/(f_i(x)) ) . Με τη θεωρία πεπερασμένων σωμάτων,    \text{Fix}_p( \mathbb{F}_q[x]/(f_i(x)) )  είναι πάντα το πρώτο υποσώμα της επέκτασης αυτού του σώματος. Συνεπώς,  \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) )   έχει   p   στοιχεία αν και μόνο αν   f(x)   είναι μη αναγωγίσιμη.

Επιπλέον, μπορούμε να χρησιμοποιήσουμε το γεγονός ότι ο αυτομορφισμός Φρομπένιους είναι  \mathbb{F}_p -γραμμικός για να υπολογίσουμε το σταθερό σύνολο. Δηλαδή, παρατηρούμε ότι το  \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) )  είναι ένα  \mathbb{F}_p -υποχώρος, και μια ρητή βάση γι' αυτόν μπορεί να υπολογιστεί στον πολυωνυμικό δακτύλιο  \mathbb{F}_p[x,y]/(f,g)  με τον υπολογισμό    (x^i y^j)^p  και την καθιέρωση των γραμμικών εξισώσεων στους συντελεστές των πολυωνύμων  x,y  που ικανοποιούνται αν είναι σταθερό από τον Φρομπένιους. Παρατηρούμε ότι σε αυτό το σημείο έχουμε ένα αποτελεσματικά υπολογίσιμο κριτήριο μη αναγωγιμότητας και η υπόλοιπη ανάλυση δείχνει πώς να το χρησιμοποιήσουμε για να βρούμε παράγοντες.

Ο αλγόριθμος αναλύεται τώρα σε δύο περιπτώσεις:

* Στην περίπτωση μικρών   p  μπορούμε να κατασκευάσουμε οποιοδήποτε    g \in \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) \setminus \mathbb{F}_p , και στη συνέχεια παρατηρούμε ότι για κάποιο  a \in \mathbb{F}_p  υπάρχουν   i,j  έτσι ώστε   g - a = 0 \mod f_i και  g - a \not = 0 \mod f_j . Ένα τέτοιο  g - a  έχει έναν μη τετριμμένο παράγοντα κοινό με την   f(x) , ο οποίος μπορεί να υπολογιστεί μέσω του gcd. Καθώς το   p  είναι μικρό, μπορούμε να διατρέξουμε κυκλικά όλα τα πιθανά   a .
* Για την περίπτωση των μεγάλων πρώτων αριθμών, οι οποίοι είναι αναγκαστικά περιττοί, μπορεί κανείς να εκμεταλλευτεί το γεγονός ότι ένα τυχαίο μη μηδενικό στοιχείο του  \mathbb{F}_p^*  είναι ένα τετράγωνο με πιθανότητα  1/2 , και ότι ο χάρτης  x \to x^{ \frac{ p -1}{2}}  απεικονίζει το σύνολο των μη μηδενικών τετραγώνων στο   1 , και το σύνολο των μη τετραγώνων στο   -1 . Έτσι, αν πάρουμε ένα τυχαίο στοιχείο  g \in \text{Fix}_p( \mathbb{F}_q[x]/f(x)) , τότε με καλή πιθανότητα  g^{ \frac{ p - 1}{2}} - 1  θα έχει έναν μη τετριμμένο παράγοντα κοινό με την   f(x) .

Για περισσότερες λεπτομέρειες μπορείτε να συμβουλευτείτε.

## Εφαρμογές

Μια σημαντική εφαρμογή του αλγορίθμου του Μπέρλεκαμπ είναι ο υπολογισμός διακριτών λογαρίθμων πάνω σε πεπερασμένα σώματα \mathbb{F}_{p^n}, όπου p είναι πρώτος αριθμός και n\geq 2.  Ο υπολογισμός των διακριτών λογαρίθμων αποτελεί σημαντικό πρόβλημα στην κρυπτογραφία δημόσιου κλειδιού και στην κωδικοποίηση ελέγχου σφαλμάτων.  Για ένα πεπερασμένο σώμα, η ταχύτερη γνωστή μέθοδος είναι η μέθοδος του υπολογισμού των δεικτών, η οποία περιλαμβάνει την παραγοντοποίηση των στοιχείων του σώματος.  Αν αναπαραστήσουμε το σώμα \mathbb{F}_{p^n} με τον συνήθη τρόπο - δηλαδή ως πολυώνυμα πάνω στο βασικό σώμα \mathbb{F}_{p}, αναγόμενα modulo ένα μη αναγώγιμο πολυώνυμο βαθμού n - τότε πρόκειται απλώς για πολυωνυμική παραγοντοποίηση, όπως προβλέπεται από τον αλγόριθμο του Μπέρλεκαμπ.

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

Ο αλγόριθμος του Μπέρλεκαμπ είναι προσβάσιμος στο πακέτο PARI/GP χρησιμοποιώντας την εντολή factormod και στον ιστότοπο WolframAlpha .

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

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

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

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

* BSTJ Later republished in: 
*
*. A masterpiece on algebra written by one of the leading contributors.
*Chapter VI of 
* 

*
*
*
*
*
*

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

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