832:
105:
547:
Because of the algebraic properties above, many familiar and powerful tools of mathematics work in GF(2) just as well as other fields. For example, matrix operations, including
373:
60:
662:. These spaces can also be augmented with a multiplication operation that makes them into a field GF(2), but the multiplication operation cannot be a bitwise operation. When
838:(these operations are however different from the standard addition and multiplication of ordinal numbers). The addition in this field is simple to perform and is akin to
968:
778:
is countable and contains a single copy of each of the finite fields GF(2); the copy of GF(2) is contained in the copy of GF(2) if and only if
249:
The multiplication of GF(2) is again the usual multiplication modulo 2 (see the table below), and on boolean variables corresponds to the
17:
952:
919:
803:
75:
679:
198:
Its addition is defined as the usual addition of integers but modulo 2 and corresponds to the table below:
538:. All larger fields contain elements other than 0 and 1, and those elements cannot satisfy this property).
655:
1024:
911:
749:
495:
349:
36:
468:
238:
If the elements of GF(2) are seen as boolean values, then the addition is the same as that of the
983:
294:
184:
126:
1014:
855:
675:
614:
243:
835:
697:
430:
929:
8:
1019:
899:
741:
562:
312:
118:
904:
396:
Because GF(2) is a field, many of the familiar properties of number systems such as the
962:
769:
168:
834:, where the addition and multiplication operations are defined in a natural manner by
948:
915:
729:
643:
180:
122:
925:
659:
548:
409:
305:
164:
415:
multiplication has an identity element (1) and an inverse for every element but 0;
910:. Encyclopedia of Mathematics and Its Applications. Vol. 20 (2nd ed.).
843:
737:
713:
689:
397:
798:
376:
149:
1008:
717:
693:
586:
301:
839:
701:
685:
639:
634:
590:
391:
108:
709:
651:
555:
527:
must have a multiplicative inverse, in which case dividing both sides by
423:
419:
401:
320:
250:
239:
875:
629:
490:
846:
has shown that the multiplication can also be performed efficiently.
375:
may be encountered although they can be confused with the notation of
748:
is a root of a polynomial with coefficients in GF(2)), and which is
121:
with the smallest possible number of elements, and is unique if the
705:
625:
674:, one can use multiplication of polynomials over GF(2) modulo a
437:
Properties that are not familiar from the real numbers include:
678:(as for instance for the field GF(2) in the description of the
667:
666:
is itself a power of two, the multiplication operation can be
765:
712:
over GF(2) (codes defined from vector spaces over GF(2)), or
654:
is another operation on this vector space, which makes it a
704:. For example, many common error correcting codes (such as
790:
is countable and is the union of all these finite fields.
647:
145:
494:
with respect to multiplication); this is an instance of
772:(i.e. essentially up to the notation of its elements).
246:, subtraction is thus the same operation as addition.
806:
642:
over GF(2). The addition of this vector space is the
551:, can be applied to matrices with elements in GF(2) (
352:
179:
GF(2) is the unique field with two elements with its
78:
39:
144:
may be identified with the two possible values of a
903:
826:
752:(any non-constant polynomial with coefficients in
367:
99:
54:
1006:
897:
593:over GF(2) in a natural fashion, by defining 0
293:GF(2) can be identified with the field of the
947:(2nd ed.). Wellesley, Mass. p. 61.
764:is uniquely determined by these properties,
638:. These are endowed with the structure of a
827:{\displaystyle \omega ^{\omega ^{\omega }}}
967:: CS1 maint: location missing publisher (
617:, implying that the number of elements of
100:{\displaystyle \mathbb {Z} /2\mathbb {Z} }
355:
242:operation. Since each element equals its
93:
80:
42:
991:Indagationes Mathematicae (Proceedings)
981:
14:
1007:
942:
621:must be a power of 2 (or infinite).
412:(0) and an inverse for every element;
723:
502:field with this property (Proof: if
24:
744:over GF(2) (i.e. every element of
25:
1036:
984:"On the Algebraic Closure of Two"
882:, another name for finite fields.
720:of polynomial rings over GF(2)).
658:, a structure that underlies all
163:is fundamental and ubiquitous in
613:. This vector space will have a
418:addition and multiplication are
368:{\displaystyle \mathbb {Z} _{2}}
55:{\displaystyle \mathbb {F} _{2}}
542:
975:
936:
891:
868:
692:over GF(2) are widely used in
13:
1:
861:
728:Like any field, GF(2) has an
385:
174:
680:Advanced Encryption Standard
628:, data are represented with
27:Finite field of two elements
7:
849:
797:can be identified with the
10:
1041:
912:Cambridge University Press
736:which contains GF(2) as a
632:of a fixed length, called
389:
982:Lenstra, Hendrik (1977).
670:; alternatively, for any
589:and can be turned into a
577: = 0 for every
185:multiplicative identities
129:are denoted respectively
943:Conway, John H. (2000).
696:, and in particular in
496:Fermat's little theorem
127:multiplicative identity
18:Field with two elements
856:Field with one element
828:
698:error correcting codes
676:irreducible polynomial
523:. In the latter case,
467:; this means that the
369:
101:
56:
836:transfinite induction
829:
793:Conway realized that
370:
187:respectively denoted
102:
57:
945:On Numbers and Games
900:Niederreiter, Harald
804:
750:algebraically closed
650:(exclusive or). The
597: = 0 and 1
569:) with the property
350:
111:with two elements.
76:
37:
478:of GF(2) satisfies
445:of GF(2) satisfies
824:
770:field automorphism
732:. This is a field
716:(codes defined as
668:nim-multiplication
429:multiplication is
365:
159:. It follows that
97:
52:
1025:Binary arithmetic
954:978-1-56881-127-7
730:algebraic closure
724:Algebraic closure
644:bitwise operation
291:
290:
236:
235:
123:additive identity
16:(Redirected from
1032:
999:
998:
988:
979:
973:
972:
966:
958:
940:
934:
933:
909:
895:
883:
872:
833:
831:
830:
825:
823:
822:
821:
820:
714:polynomial codes
690:polynomial rings
660:computer science
549:matrix inversion
537:
522:
515:
508:
487:
466:
455:
410:identity element
408:addition has an
398:rational numbers
379:
374:
372:
371:
366:
364:
363:
358:
345:
333:
306:ring of integers
298:
295:integers modulo
256:
255:
201:
200:
194:
190:
165:computer science
162:
143:
140:The elements of
136:
132:
116:
106:
104:
103:
98:
96:
88:
83:
71:
61:
59:
58:
53:
51:
50:
45:
32:
21:
1040:
1039:
1035:
1034:
1033:
1031:
1030:
1029:
1005:
1004:
1003:
1002:
986:
980:
976:
960:
959:
955:
941:
937:
922:
896:
892:
887:
886:
873:
869:
864:
852:
816:
812:
811:
807:
805:
802:
801:
726:
656:Boolean algebra
585:is necessarily
545:
532:
517:
510:
503:
498:. GF(2) is the
479:
457:
446:
394:
388:
377:
359:
354:
353:
351:
348:
347:
344:
338:
324:
300:, that is, the
296:
192:
188:
177:
160:
141:
134:
130:
114:
92:
84:
79:
77:
74:
73:
63:
46:
41:
40:
38:
35:
34:
30:
28:
23:
22:
15:
12:
11:
5:
1038:
1028:
1027:
1022:
1017:
1001:
1000:
974:
953:
935:
920:
898:Lidl, Rudolf;
889:
888:
885:
884:
866:
865:
863:
860:
859:
858:
851:
848:
819:
815:
810:
799:ordinal number
756:has a root in
725:
722:
544:
541:
540:
539:
509:, then either
474:every element
472:
471:of GF(2) is 2;
469:characteristic
456:and therefore
441:every element
435:
434:
433:over addition.
427:
416:
413:
404:are retained:
390:Main article:
387:
384:
380:-adic integers
362:
357:
342:
289:
288:
285:
282:
278:
277:
274:
271:
267:
266:
263:
260:
234:
233:
230:
227:
223:
222:
219:
216:
212:
211:
208:
205:
176:
173:
150:boolean values
95:
91:
87:
82:
49:
44:
33:(also denoted
26:
9:
6:
4:
3:
2:
1037:
1026:
1023:
1021:
1018:
1016:
1015:Finite fields
1013:
1012:
1010:
996:
992:
985:
978:
970:
964:
956:
950:
946:
939:
931:
927:
923:
921:0-521-39231-4
917:
913:
908:
907:
906:Finite fields
901:
894:
890:
881:
877:
871:
867:
857:
854:
853:
847:
845:
841:
837:
817:
813:
808:
800:
796:
791:
789:
785:
781:
777:
773:
771:
767:
763:
760:). The field
759:
755:
751:
747:
743:
739:
735:
731:
721:
719:
715:
711:
707:
703:
699:
695:
694:coding theory
691:
687:
686:Vector spaces
683:
681:
677:
673:
669:
665:
661:
657:
653:
649:
645:
641:
637:
636:
635:machine words
631:
627:
622:
620:
616:
612:
608:
604:
601: =
600:
596:
592:
588:
584:
580:
576:
573: +
572:
568:
564:
559:
557:
554:
550:
535:
530:
526:
520:
513:
506:
501:
497:
493:
492:
486:
482:
477:
473:
470:
465:
461:
453:
449:
444:
440:
439:
438:
432:
428:
425:
421:
417:
414:
411:
407:
406:
405:
403:
399:
393:
383:
381:
360:
341:
335:
332:
328:
322:
318:
314:
310:
307:
303:
302:quotient ring
299:
286:
283:
280:
279:
275:
272:
269:
268:
264:
261:
258:
257:
254:
252:
247:
245:
241:
231:
228:
225:
224:
220:
217:
214:
213:
209:
206:
203:
202:
199:
196:
186:
182:
172:
171:foundations.
170:
166:
158:
154:
151:
147:
138:
128:
124:
120:
112:
110:
89:
85:
70:
66:
47:
19:
994:
990:
977:
944:
938:
905:
893:
880:Galois field
879:
870:
840:Nim-addition
794:
792:
787:
783:
779:
775:
774:
761:
757:
753:
745:
733:
727:
710:linear codes
702:cryptography
684:
671:
663:
640:vector space
633:
623:
618:
610:
606:
602:
598:
594:
591:vector space
582:
578:
574:
570:
566:
560:
552:
546:
543:Applications
533:
528:
524:
518:
511:
504:
499:
489:
484:
480:
475:
463:
459:
451:
447:
442:
436:
431:distributive
402:real numbers
395:
392:finite field
339:
336:
330:
326:
321:even numbers
316:
308:
292:
248:
237:
197:
178:
156:
152:
139:
137:, as usual.
113:
109:finite field
68:
64:
29:
740:, which is
700:and modern
652:bitwise AND
630:bit strings
556:matrix ring
424:associative
420:commutative
253:operation.
251:logical AND
240:logical XOR
148:and to the
1020:2 (number)
1009:Categories
930:0866.11069
876:initialism
874:GF is the
862:References
786:The field
624:In modern
491:idempotent
386:Properties
337:Notations
175:Definition
963:cite book
818:ω
814:ω
809:ω
742:algebraic
718:quotients
706:BCH codes
682:cipher).
626:computers
488:(i.e. is
107:) is the
902:(1997).
850:See also
782:divides
738:subfield
605:for all
325:GF(2) =
244:opposite
181:additive
167:and its
125:and the
844:Lenstra
646:called
587:abelian
319:of all
311:by the
304:of the
169:logical
117:is the
951:
928:
918:
708:) are
531:gives
987:(PDF)
766:up to
615:basis
563:group
313:ideal
161:GF(2)
157:false
142:GF(2)
119:field
115:GF(2)
31:GF(2)
997:(5).
969:link
949:ISBN
916:ISBN
688:and
561:Any
500:only
422:and
400:and
346:and
191:and
183:and
155:and
153:true
133:and
926:Zbl
878:of
648:XOR
609:in
581:in
567:V,+
558:).
553:see
536:= 1
521:≠ 0
516:or
514:= 0
507:= x
454:= 0
146:bit
72:or
1011::
995:80
993:.
989:.
965:}}
961:{{
924:.
914:.
842:;
784:m.
768:a
483:=
462:=
450:+
382:.
334:.
329:/2
323::
287:1
281:1
276:0
270:0
265:1
232:0
226:1
221:1
215:0
210:1
195:.
67:/2
62:,
971:)
957:.
932:.
795:F
788:F
780:n
776:F
762:F
758:F
754:F
746:F
734:F
672:n
664:n
619:V
611:V
607:v
603:v
599:v
595:v
583:V
579:v
575:v
571:v
565:(
534:x
529:x
525:x
519:x
512:x
505:x
485:x
481:x
476:x
464:x
460:x
458:−
452:x
448:x
443:x
426:;
378:2
361:2
356:Z
343:2
340:Z
331:Z
327:Z
317:Z
315:2
309:Z
297:2
284:0
273:0
262:0
259:×
229:1
218:0
207:0
204:+
193:1
189:0
135:1
131:0
94:Z
90:2
86:/
81:Z
69:Z
65:Z
48:2
43:F
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.