(5)
Finite Fields and Generators
A field is simply a set which contains numerical elements that are subject to the familiar addition and multiplication operations. Several different types of fields exist; for example, , the field of real numbers, and , the field of rational numbers, or , the field of complex numbers. A generic field is usually denoted .
Finite Fields
Cryptography utilizes primarily finite fields, nearly exclusively composed of integers. The most notable exception to this are the Gaussian numbers of the form which are complex numbers with integer real and imaginary parts. Finite fields are defined as follows
The set of integers modulo
The set of integers modulo a prime
Since cryptography is concerned with the solution of diophantine equations, the finite fields utilized are primarily integer based, and are denoted by the symbol for the field of integers, .
A finite field contains exactly elements, of which there are nonzero elements. An extension of is the multiplicative group of , written , and consisting of the following elements
such that
in other words, contains the elements coprime to
Finite fields form an abelian group with respect to multiplication, defined by the following properties
The product of two nonzero elements is nonzero
The associative law holds
The commutative law holds
There is an identity element
Any nonzero element has an inverse
A subscript following the symbol for the field represents the set of integers modulo , and these integers run from to as represented by the example below
The multiplicative order of is represented and consists of all elements such that . An example for is given below
If is prime, the set consists of all integers such that . For example
Composite n Prime p
Generators
Every finite field has a generator. A generator is capable of generating all of the elements in the set by exponentiating the generator . Assuming is a generator of , then contains the elements for the range . If has a generator, then is said to be cyclic.
The total number of generators is given by
Examples
For (Prime)
Total number of generators generators
Let , then , is a generator
Since is a generator, check if
, and , , therefore, is not a generator
, and , , therefore, is not a generator
Let , then , is a generator
Let , then , is a generator
Let , then , is a generator
There are a total of generators, as predicted by the formula
For (Composite)
Total number of generators generators
Let , then , is a generator
Let , then , is a generator
There are a total of generators as predicted by the formula
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|