Try   HackMD

Finite Fields

Groups, Rings, and Fields

  • Fields are a subset of rings, which are a subset of the groups.
    • Groups are defined by a simple set of properties. Each successive subset adds additional properties and is thus more complex.
    • 同一集合中的兩個元素以多種方式組合後得到的元素,仍在同一個集合內
    • 這些特殊的運算規則定義了集合的性質

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Group

A group

G, sometimes denoted by
{G,}
, is a set of elements with a binary operation denoted by
that associates to each ordered pair (a, b) of elements in G an element
(ab)
in
G×G
, such that the following axioms are obeyed:

The operator

is generic and can refer to addition, multiplication, or some other mathematical operation.

  • (A1) Closure: If
    a
    and
    b
    belong to
    G
    , then
    ab
    is also in
    G
    .
  • (A2) Associative:
    a(bc)=(ab)c
    for all
    a,b,c
    in
    G
    .
  • (A3) Identity element: There is an element
    e
    in
    G
    such that
    ae=ea=a
    for all
    a
    in
    G
    .
  • (A4) Inverse element: For each
    a
    in
    G
    , there is an element
    a
    in
    G
    such that
    aa=aa=e
    .

Abelian Group

A group is said to be abelian (also called commutative) if it satisfies the following additional condition:

  • (A5) Commutitive:
    ab=ba
    for all
    a,b
    in
    G
    .

Example:

  • The set of integers (positive, negative, and 0) under addition is an abelian group.
  • The set of nonzero real numbers under multiplication is an abelian group.

Cyclic Group

  • Define exponentiation within a group as repeated application of operator
    • Example:
      a3=aaa
  • Define
    a0=e
    as the identity element.
  • A group
    G
    is cyclic if every element in
    G
    is a power
    ak
    (
    k
    is integer) of some fixed element
    aG
    .

Ring

https://math.ntnu.edu.tw/~li/algebra-html/chap5.pdf

A ring

R, sometimes denoted by
{R,+,×}
, is a set of elements with two binary operations, called addition and multiplication, such that for all
a,b,c
in
R
the following axioms are obeyed.

  • (A1 - A5) R is an abelian group with respect to addition; that is, R satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as 0 and the inverse of a as -a.
    • 在加法運算下是一個 abelian group
    • 乘法僅要求封閉性和結合律
  • (M1) Closure under multiplication: If
    a
    and
    b
    belong to
    R
    , then
    ab
    is also in
    R
    .
  • (M2) Associativity of multiplication:
    a(b+c)=ab+ac
    for all
    a,b,c
    in
    R
    .
  • (M3) Distributive laws:
    a(b+c)=ab+ac
    for all
    a,b,c
    in
    R
    .
    (a+b)c=ac+bc
    for all
    a,b,c
    in
    R
    .

本質上 ring 是一個可以在其中進行加法、減法 [

ab=a+(b)] 與乘法的集合(運算後結果仍在集合中)。

Commutative Ring

A ring is said to be commutative if it satisfies the following additional condition:

  • (M4) Commutativity of multiplication:
    ab=ba
    for all
    a,b
    in
    R
    .

Integral Domain

Define an integral domain, which is a commutative ring that obeys the following axioms.

  • (M5) Multiplicative identity: There is an element 1 in
    R
    such that
    a1=1a=a
    for all
    a
    in
    R
    .
  • (M6) No zero divisors: If
    a,b
    in
    R
    and
    ab=0
    , then either
    a=0
    or
    b=0
    .

Field

https://ccckmit.gitbooks.io/rlab/content/field.html

A field F, sometimes denoted by

{F,+,×}, is a set of elements with two binary operations, called addition and multiplication, such that for all
a,b,c
in
F
the following
axioms are obeyed.

  • (A1 - M6)
    F
    is an integral domain; that is,
    F
    satisfies axioms A1 through A5 and M1 through M6.
  • (M7) Multiplicative inverse: For each
    a
    in
    F
    , except 0, there is an element
    a1
    in
    F
    such that
    aa1=(a1)a=1
    .

本質上 field 是一個可以在其中進行加法、減法、乘法與除法的集合。除法定義為

a/b=a(b1)

Field 範例:

  • 有理數
    {Q,+,×}
  • 實數
    {R,+,×}
  • 複數
    {C,+,×}
  • 由於整數中只有 1 與 -1 有乘法反元素,因此整數不是一個 field

Properties of Groups, Rings, and Fields

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Finite Fields

  • Galois Fields
  • Finite fields are of increasing importance in Cryptography
  • The finite field of order,元素的個數)
    pn
    , where p is a prime, is generally written
    GF(pn)
  • Special Finite Fields
    • GF(p)
      : Prime Field
      • The set of integers
        {0,1,,p1}
        with arithmetic operations modulo prime
        p
        .
    • GF(2n)
      : Binary Field

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Example:

GF(2) is the simplest finite field.

Addition is equivalent to the XOR operation, and Multiplication is equivalent to the logical AND operation.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Generator of Finite Field

  • A generator
    g
    of a finite field
    F
    of order
    q
    (contains q elements) is an element whose first
    q1
    powers generate all the nonzero elements of
    F
    • The
      q
      element of
      F
      • 0,g0,g1,g2,...,gq2

Prime Field GF(p)

  • The set of integers
    {0,1,,p1}
    with arithmetic operations modulo prime
    p
    .
  • Example
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

    -
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

Finding the Multiplicative Inverse in GF(p)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Polynomial Arithmetic

f(x)=anxn+an1xn1++a1x+a0=i=0naixi

Degree: n

Treatment of Polynomials

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  • Three Classes of Polynomial Arithmetic
    • Ordinary polynomial arithmetic, using the basic rules of algebra.
    • Polynomial arithmetic in which the coefficients are in
      GF(p)
      .
    • Polynomial arithmetic in which the coefficients are in
      GF(p)
      , and the polynomials are defined modulo a polynomial
      m(x)
      whose highest power is some integer
      n
      .

Ordinary Polynomial Arithmetic

  • add or subtract corresponding coefficients
  • multiply all terms by each other
  • Example
    let f(x)=x3+x2+2 and g(x)=x2x+1f(x)+g(x)=x3+2x2x+3f(x)g(x)=x3+x+1f(x)×g(x)=x5+3x22x+2

    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

Polynomial Arithmetic with Modulo Coefficeients

  • when computing value of each coefficient do calculation modulo some value
    • forms a polynomial ring
  • could be modulo any prime
    • most interested in mod 2
    • i.e., all coefficients are 0 or 1
    • Example
      • Image Not Showing Possible Reasons
        • The image was uploaded to a note which you don't have access to
        • The note which the image was originally uploaded to has been deleted
        Learn More →
  • Polynomial Division
    • f(x)=q(x)×g(x)+r(x)
    • r(x)=f(x) mod g(x)
    • if r(x) = 0, g(x) divides f(x)
    • if g(x) has no divisors other than itself & 1, then it is an irreducible polynomial (
      prime polynomial)
      • arithmetic modulo an irreducible polynomial forms a field
        image.png
  • Examples: Polynomial Arithmetic over
    GF(2)

    (減法與加法都是 XOR 運算)
    image.png

Binary Field
GF(2n)

Computation in
GF(2n)

  • polynomials with coefficients modulo 2
    • degree < n
      • hence must reduce modulo an irreducible poly of degree n (for multiplication only)
  • Multiplicative Inverse
    • by using the Extended Euclidean Algorithm

Elements of
GF(2n)

  • Example: 8 Elements of
    GF(23)
    • Polynomial Representation (form:
      x2+x+1
      )
      0,1,x,x+1,x2,x2+1,x2+x,x2+x+1
    • Binary Representation (form:
      )
      • 000, 001, 010, 011, 100, 101, 110, 111

Addition in
GF(2n)

  • Example: Addition in
    GF(23)
    • Polynomial Representation
      image.png
    • Binary Representation
      image.png
      • bitwise

Multiplication in
GF(2n)

  • Example: Multiplication in
    GF(23)
    • Polynomial Representation
      image.png
      • using the irreducible poly of degree 3:
        x3+x+1
      • 要標明是使用什麼 irreducible poly,若有其他符合的 irreducible poly 也可以使用
    • Binary Representation
      image.png

Additive and Multiplicative Inverses in
GF(2n)

  • Example: Additive and Multiplicative Inverses in
    GF(23)

    image.png
  • Calculate the Multiplicative Inverse in
    GF(2n)
    • Calculate
      a1(x)modm(x)
      by using the Extended Euclidean Algorithm
      • gcd(m(x),a(x))=1
      • degree of
        a(x)
        < the degree of
        m(x)
    • Example: Compute
      (x7+x+1)1modx8+x4+x3+x+1

      image.png
      • (x7+x+1)1modx8+x4+x3+x+1=x7

Computational Considerations for
GF(2n)

  • Represent polynomials as bit strings
  • Addition
    XOR
    • (x2+1)+(x2+x+1)=x101111=010
  • Multiplication
    shift & XOR
    • (x+1)(x2+1)=x(x2+1)+1·(x2+1)=x3+x2+x+1

      011101=((101)1)((101)0)=1010101=1111
  • Polynomial Modulo Reduction
    shift & XOR
    • (x3+x2+x+1)mod(x3+x+1)=1(x3+x+1)+(x2)=x2

      1111mod1011=11111011=0100