GF(2)

Το  (επίσης συμβολίζεται ως ,  or ) είναι το πεπερασμένο σώμα με δύο στοιχεία. 

Το  είναι το σώμα με τον μικρότερο δυνατό αριθμό στοιχείων και είναι μοναδικό αν η προσθετική ταυτότητα και η πολλαπλασιαστική ταυτότητα συμβολίζονται αντίστοιχα με  και , ως συνήθως.

Τα στοιχεία του  μπορούν να ταυτιστούν με τις δύο δυνατές τιμές ενός bit και με τις τιμές Μπουλ αληθής και ψευδής. Προκύπτει ότι η  είναι θεμελιώδης και πανταχού παρούσα στην επιστήμη των υπολογιστών και στα λογικά της θεμέλια.

 Ορισμός 
Το GF(2) είναι το μοναδικό σώμα με δύο στοιχεία με τις προσθετικές και πολλαπλασιαστικές ταυτότητες που συμβολίζονται αντίστοιχα με  και .

Η πρόσθεση του ορίζεται ως η συνήθης πρόσθεση ακεραίων αλλά modulo 2 και αντιστοιχεί στον παρακάτω πίνακα:

 +  0  1 0 0  1 1 1  0

Αν τα στοιχεία του GF(2) θεωρηθούν ως τιμές Μπουλ, τότε η πρόσθεση είναι η ίδια με εκείνη της λογικής πράξης XOR.
Εφόσον κάθε στοιχείο ισούται με το αντίθετό του, η αφαίρεση είναι επομένως η ίδια πράξη με την πρόσθεση.

Ο πολλαπλασιασμός του GF(2) είναι και πάλι ο συνήθης πολλαπλασιασμός modulo 2 (βλ. τον παρακάτω πίνακα) και στις μεταβλητές Μπουλ αντιστοιχεί στη λογική σύζευξη AND.

 ×  0  1 0 0  0 1 0  1

Το GF(2) μπορεί να ταυτιστεί με το σώμα των ακεραίων modulo , δηλαδή, το πηλίκο του δακτυλίου των ακεραίων Z από το ιδανικό 2Z όλων των ζυγών αριθμών: .

Οι συμβολισμοί  και  μπορεί να συναντηθούν αν και μπορεί να συγχέονται με τον συμβολισμό των -adic ακεραίων.

 Ιδιότητες 
Κύριο λήμμα: Πεπερασμένο σώμα

Επειδή το GF(2) είναι ένα σώμα, διατηρούνται πολλές από τις γνωστές ιδιότητες των αριθμητικών συστημάτων, όπως οι ρητοί αριθμοί και οι πραγματικοί αριθμοί:

 Η πρόσθεση έχει ένα στοιχείο ταυτότητας (0) και ένα αντίστροφο για κάθε στοιχείο,
 ο πολλαπλασιασμός έχει ένα στοιχείο ταυτότητας (1) και ένα αντίστροφο για κάθε στοιχείο εκτός από το 0,
 η πρόσθεση και ο πολλαπλασιασμός έχουν αντιμεταθετική και προσεταιριστική ιδιότητα,
 Στον πολλαπλασιασµό ισχύει η επιµεριστική ιδιότητα επί της πρόσθεσης.

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

 κάθε στοιχείο x του GF(2) ικανοποιεί την  και επομένως - αυτό σημαίνει ότι η χαρακτηριστική του GF(2) είναι 2,
 κάθε στοιχείο x του GF(2) ικανοποιεί την τιμή  (δηλαδή είναι ταυτοδύναμο ως προς τον πολλαπλασιασμό)- αυτό είναι μια περίπτωση του μικρού θεωρήματος του Φερμά. Το GF(2) είναι το μόνο σώμα με αυτή την ιδιότητα (Απόδειξη: , τότε είτε  είτε . Στην τελευταία περίπτωση, το, x πρέπει να έχει πολλαπλασιαστικό αντίστροφο, οπότε διαιρώντας και τις δύο πλευρές με το x προκύπτει . Όλα τα μεγαλύτερα σώματα περιέχουν στοιχεία εκτός από το 0 και το 1, και τα στοιχεία αυτά δεν μπορούν να ικανοποιήσουν αυτή την ιδιότητα).

 Εφαρμογές 

Λόγω των παραπάνω αλγεβρικών ιδιοτήτων, πολλά γνωστά και ισχυρά εργαλεία των μαθηματικών λειτουργούν στο GF(2) καθώς και σε άλλους τομείς.  Παραδείγματος χάριν, οι πράξεις πινάκων, όπως του αντιστρέψιμου πίνακα, μπορούν να εφαρμοστούν σε πίνακες με στοιχεία στο GF(2) (βλέπε δακτύλιος πίνακα.)

Οποιαδήποτε ομάδα (V,+) με την ιδιότητα v + v = 0 για κάθε v στο V είναι αναγκαστικά αβελιανή και μπορεί να μετατραπεί σε διανυσματικό χώρο πάνω από την GF(2) με φυσικό τρόπο, ορίζοντας 0v = 0 και 1v = v για όλα τα v στο V. Αυτός ο διανυσματικός χώρος θα έχει μια βάση, που σημαίνει ότι ο αριθμός των στοιχείων του V πρέπει να είναι δύναμη του 2 (ή άπειρος).

Στους σύγχρονους υπολογιστές, τα δεδομένα αναπαρίστανται με σειρές μπιτ σταθερού μήκους, που ονομάζονται λέξεις μηχανής. Αυτές έχουν τη δομή ενός διανυσματικού χώρου πάνω σε GF(2).  Η πρόσθεση αυτού του διανυσματικού χώρου είναι η πράξη κατά ψηφία που ονομάζεται XOR (αποκλειστικό ή). Το bitwise AND είναι μια άλλη πράξη σε αυτόν τον διανυσματικό χώρο, η οποία τον καθιστά άλγεβρα Μπουλ, μια δομή που διέπει όλη την επιστήμη των υπολογιστών. Αυτοί οι χώροι μπορούν επίσης να εμπλουτιστούν με μια πράξη πολλαπλασιασμού που τους μετατρέπει σε σώμα GF(2n), αλλά η πράξη πολλαπλασιασμού δεν μπορεί να είναι πράξη κατά bitwise. Όταν n Όταν το n είναι δύναμη του δύο, η πράξη πολλαπλασιασμού μπορεί να είναι ο πολλαπλασιασμός nim- εναλλακτικά, για οποιοδήποτε n, μπορεί κανείς να χρησιμοποιήσει πολλαπλασιασμό πολυωνύμων πάνω στο GF(2) modulo ένα μη αναγώγιμο πολυώνυμο (όπως επί παραδείγματι το σώμα GF(28) στην περιγραφή της κρυπτογράφησης με το Advanced Encryption Standard).

Οι διανυσματικοί χώροι και οι πολυωνυμικοί δακτύλιοι πάνω από το GF(2) χρησιμοποιούνται ευρέως στη θεωρία κωδικοποίησης, και ιδίως στους κώδικες διόρθωσης σφαλμάτων και στη σύγχρονη κρυπτογραφία. Παραδείγματος χάριν, πολλοί κοινοί κώδικες διόρθωσης σφαλμάτων (όπως οι κώδικες BCH) είναι γραμμικοί κώδικες πάνω από το GF(2)(κώδικες που ορίζονται από διανυσματικούς χώρους πάνω από το GF(2)), ή πολυωνυμικοί κώδικες (κώδικες που ορίζονται ως πηλίκα πολυωνυμικών δακτυλίων πάνω από το  GF(2)).

 Αλγεβρική κλειστότητα 

Όπως κάθε σώμα, το GF(2) έχει μια αλγεβρική κλειστότητα. Αυτό είναι ένα σώμα F το οποίο περιέχει το GF(2) ως υποσώμα, το οποίο είναι αλγεβρικό πάνω στο GF(2) (δηλαδή κάθε στοιχείο του F είναι ρίζα ενός πολυωνύμου με συντελεστές στο GF(2)), και το οποίο είναι αλγεβρικά κλειστό (κάθε μη σταθερό πολυώνυμο με συντελεστές στο F έχει ρίζα στο F). Το σώμα F καθορίζεται μοναδικά από αυτές τις ιδιότητες, μέχρι έναν αυτομορφισμό του σώματος (δηλαδή ουσιαστικά μέχρι τον συμβολισμό των στοιχείων του).

Το F είναι μετρήσιμο και περιέχει ένα μόνο αντίγραφο καθενός από τα πεπερασμένα σώματα GF(2n); το αντίγραφο του GF(2n) περιέχεται στο αντίγραφο του GF(2m) εάν και μόνο εάν το n διαιρεί το m. Το σώμα F είναι μετρήσιμο και είναι η ένωση όλων αυτών των πεπερασμένων σωμάτων.

Ο Κονγουέι συνειδητοποίησε ότι ο F μπορεί να ταυτιστεί με τον τακτικό αριθμό , όπου οι πράξεις πρόσθεσης και πολλαπλασιασμού ορίζονται με φυσικό τρόπο μέσω της υπερβατικής επαγωγής (οι πράξεις αυτές είναι ωστόσο διαφορετικές από την τυπική πρόσθεση και τον πολλαπλασιασμό των τακτικών αριθμών). Η πρόσθεση σε αυτό το σώμα είναι απλή στην εκτέλεση και μοιάζει με την πρόσθεση Νιμ- ο Λένστρα έδειξε ότι ο πολλαπλασιασμός μπορεί επίσης να εκτελεστεί αποτελεσματικά. 

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

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

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











 Παραπομπές 



 Lang, Serge (1993), Algebra (Third ed.), Reading, Mass.: Addison-Wesley, ISBN 978-0-201-55540-0, Zbl 0848.13001

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

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