Format Example : GF(2)

Galois Field : GF(2)
Number of variables (n) : 4
Number of equations (m) : 8
Seed : 0
Order : graded reverse lex order

*********************
1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 ;
0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 ;
1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 ;
0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 ;
0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 ;
0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 ;
1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 ;
0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 ;

The text box above is an example of a MQ challenge system over GF(2), which is used for Type I and Type IV systems. As we can see in the example, it specifies the coefficient field F, the number of the variables n and the number m of equations in the system m. It also shows the seed used to generate the MQ system.

Moreover, we use the graded reverse lex order to represent the monomials. Every line after ************ line ends up with the semicolon ; mark and represents one polynomial. Every number represents the the coefficient of the corresponding monomial.

For example, let x1, x2, x3 and x4 to be the four variables of the system with x1 > x2 > x3 > x4. Then for a quadratic system, the order of monomials should be x12 > x1x2 > x22 > x1x3 > x2x3 > x32 > x1x4 > x2x4 > x3x4 > x42 > x1 > x2 > x3 > x4 > 1. Thus, in this example, the first polynomial is x12 + x1x2 + x2x3 + x32 + x1 + x4 and the second polynomial is x2x3 + x32 + x2x4 + x42 + x2 + x4 + 1.

Format Example : GF(28)

Galois Field : GF(2)[x] / x^8 + x^4 + x^3 + x^2 + 1
Number of variables (n) : 4
Number of equations (m) : 8
Seed : 0
Order : graded reverse lex order

*********************
de 8d 73 3b f0 46 88 50 ca 7b dc 9d 22 cd b2 ;
e1 f7 ac 25 ed b9 74 9b 7b d4 94 4f e6 b5 e0 ;
f2 cf c3 5d c4 cd a1 aa 20 51 85 4b dd b1 bc ;
08 4e 21 48 7e bc 7a ad de d5 0c b3 00 4f 5c ;
81 0e 98 4d 3c 38 d3 07 48 f3 5a 52 27 fc 91 ;
ee 27 47 c9 82 21 99 31 0e cd c4 b8 69 69 9e ;
7b ce 96 c5 37 6a ce 34 ca 19 73 8f 30 34 b6 ;
90 65 bc d0 02 77 6c af 1d 7f 1c 29 9c 55 60 ;

The text box above is an example of a MQ challenge system over GF(28), which is used for Type II and Type V systems. Most of this format is similar to the case of GF(2). The coefficient field F is defined by the irreducible polynomial p(x)= x8 + x4 + x3 + x2 + 1. Any polynomial a= a7x7 + a6x6 + … + a1x + a0 (mod p(x)) represents uniquely an element of GF(28). To this element, we associate 2-digits hex number equal to the number a7a6…a1a0 in base 2.

In this example, the first coefficient de indicates 1101 1110, which refers to x7 + x6 + x4 + x3 + x2 + x ∈ GF(2)[x] / x8 + x4 + x3 + x2 + 1. Similarly, the second coefficient 8d, which indicates 1000 1101, refers to x7 + x3 + x2 + 1 ∈ GF(2)[x] / x8 + x4 + x3 + x2 + 1.

Format Example : GF(31)

Galois Field : GF(31)
Number of variables (n) : 4
Number of equations (m) : 8
Seed : 0
Order : graded reverse lex order

*********************
29 20 25 28 4 7 10 28 8 13 14 29 19 30 8 ;
24 20 3 27 25 28 30 3 23 6 23 25 3 2 18 ;
4 29 29 31 0 19 7 24 18 8 9 23 24 8 27 ;
28 4 4 4 17 16 3 25 14 2 1 6 30 8 16 ;
6 1 11 17 3 1 14 14 6 29 3 23 27 18 22 ;
25 19 7 0 1 14 28 27 6 11 13 26 29 14 24 ;
12 21 28 2 21 25 0 12 1 29 27 7 23 23 14 ;
1 28 21 15 11 30 23 7 9 26 10 29 2 0 7 ;

The text box above is an example of a MQ challenge system over GF(31), which is used for Type III and Type VI systems. All the format is similar to the examples of GF(2) and of GF(28). Every number is a coefficient in GF(31).