Return to Answer

In GF(2⁸), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example. Noting that 7 = 111₂ and 11 = 1011₂, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication. But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      111₂ + 1110₂ + 111000₂ = 10101₂ + 111000₂ = 1001101₂ = 77,

in GF(2ⁿ) addition is done bitwise without carries (i.e. GF(2ⁿ) addition is the same as bitwise XOR), and thus we get

      111₂ + 1110₂ + 111000₂ = 1001₂ + 111000₂ = 110001₂ = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the reduction polynomial, but in this case that doesn't happen for n ≥ 7.)

In GF(2⁸), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example. Noting that 7 = 111₂ and 11 = 1011₂, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication. But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      111₂ + 1110₂ + 111000₂ = 10101₂ + 111000₂ = 1001101₂ = 77,

in GF(2ⁿ) addition is done bitwise without carries (i.e. GF(2ⁿ) addition is the same as bitwise XOR), and thus we get

      111₂ + 1110₂ + 111000₂ = 1001₂ + 111000₂ = 110001₂ = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the reduction polynomial, but in this case that doesn't happen for n ≥ 7.)

In GF(2⁸), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example. Noting that 7 = 111₂ and 11 = 1011₂, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication. But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      111₂ + 1110₂ + 111000₂ = 10101₂ + 111000₂ = 1001101₂ = 77,

in GF(2ⁿ) addition is done bitwise without carries (i.e. GF(2ⁿ) addition is the same as bitwise XOR), and thus we get

      111₂ + 1110₂ + 111000₂ = 1001₂ + 111000₂ = 110001₂ = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the group polynomial, but in this case it doesn't happen for n ≥ 7.)

In GF(2⁸), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example. Noting that 7 = 111₂ and 11 = 1011₂, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication. But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      111₂ + 1110₂ + 111000₂ = 10101₂ + 111000₂ = 1001101₂ = 77,

in GF(2ⁿ) addition is done bitwise without carries (i.e. GF(2ⁿ) addition is the same as bitwise XOR), and thus we get

      111₂ + 1110₂ + 111000₂ = 1001₂ + 111000₂ = 110001₂ = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the reduction polynomial, but in this case that doesn't happen for n ≥ 7.)

In GF(2⁸), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

In GF(2⁸), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example. Noting that 7 = 111₂ and 11 = 1011₂, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication. But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      111₂ + 1110₂ + 111000₂ = 10101₂ + 111000₂ = 1001101₂ = 77,

in GF(2ⁿ) addition is done bitwise without carries (i.e. GF(2ⁿ) addition is the same as bitwise XOR), and thus we get

      111₂ + 1110₂ + 111000₂ = 1001₂ + 111000₂ = 110001₂ = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the group polynomial, but in this case it doesn't happen for n ≥ 7.)