Matthew van Eerde's web log

  • Matthew van Eerde's web log

    Addition and multiplication table for GF(2²)

    • 5 Comments

    I'm reading Joan Daemen and Vincent Rijmen's book The Design of Rijndael and I'm giving myself a refresher course on group theory.

    Key to the encryption standard is the Galois field on 256 elements GF(28). A multiplication table of 256 elements by 256 elements quickly becomes a wall of text, so let's reason by analogy and look at GF(22).

    There are a number of ways to represent elements of the field; we'll start by representing them as polynomials with degree at most 1, and with integer coefficients modulo 2. There are four such polynomials: {0, 1, x, x + 1}.

    Here are the addition and multiplication tables:

    + 0 1 x x + 1
    0 0 1 x x + 1
    1 1 0 x + 1 x
    x x x + 1 0 1
    x + 1 x + 1 x 1 0
     
    0 1 x x + 1
    0 0 0 0 0
    1 0 1 x x + 1
    x 0 x x2 mod m x2 + x mod m
    x + 1 0 x + 1 x2 + x mod m x2 + 1 mod m

    Hold on. What's that funny-looking m?

    It's a "reduction polynomial" which brings the product back down to degree 1 or less. It has to be a polynomial of degree 2. There are four such polynomials: let's try each and see what we get.

    x2
    0 x
    x 1
    x2 + 1
    1 x + 1
    x + 1 0
    x2 + x
    x 0
    0 x + 1
    x2 + x + 1
    x + 1 1
    1 x

    Note that the first three polynomials all factor into products of lower-degree polynomials: x2 = x(x), x2 + 1 = (x + 1)(x + 1), x2 + x = x(x + 1). Only x2 + x + 1 is prime; and this prime reduction polynomial generates a complete multiplication table with no 0s. This is a necessary condition to be a field. Our final tables are:

    + 0 1 x x + 1
    0 0 1 x x + 1
    1 1 0 x + 1 x
    x x x + 1 0 1
    x + 1 x + 1 x 1 0
     
    0 1 x x + 1
    0 0 0 0 0
    1 0 1 x x + 1
    x 0 x x + 1 1
    x + 1 0 x + 1 1 x

    We can also write our elements in binary form: 0 => 00, 1 => 01, x => 10, and x + 1 => 11. In this notation our tables become:

    + 00 01 10 11
    00 00 01 10 11
    01 01 00 11 10
    10 10 11 00 01
    11 11 10 01 00
     
    00 01 10 11
    00 00 00 00 00
    01 00 01 10 11
    10 00 10 11 01
    11 00 11 01 10

    Rijndael works in GF(28) and uses a reduction polynomial of x8 + x4 + x3 + x + 1. They say this is prime. I sure hope so.

  • Matthew van Eerde's web log

    Microsoft etiquette: calendar appointments when going out of office

    • 1 Comments

    A common convention within Microsoft when going out of office is to create two calendar appointments in Outlook:

    1. An appointment which allows people who are trying to schedule a meeting with you to know that you're out of office at the time
      1. Attendees: just you
      2. Show As: Out of Office
    2. An informational appointment which allows people who work closely with you to know when you're going to be out of office
      1. Attendees: people who work closely with you (e.g., your immediate team)
      2. Show As: Free
      3. Request Responses: Off
      4. Allow New Time Proposals: Off
      5. Reminder: None

    I'm always forgetting one of the steps under 2., so I'm creating this blog post. Next time I go out of office I'll remember to check this post.

  • Matthew van Eerde's web log

    Why is 1 Pascal equal to 94 dB Sound Pressure Level? (1 Pa = 94 dB SPL)

    • 0 Comments

    Last time we talked about why a full-scale digital sine wave has a power measurement of -3.01 dB FS (Spoiler: because it's not a square wave.)

    This time we'll discuss why an atmospheric sound which generates a root-mean-square pressure of 1 Pascal has a power measurement 94 dB SPL.

    As before, dB is defined as 10 log10(PA2 / PB2) where PB is a reference level.

    Before, we had a digital measurement with an obvious ceiling: sample values of -1 and 1. So the reference point 0 dB FS was defined in terms of the signal with the greatest possible energy.

    In the analog domain, there isn't an obvious ceiling. We instead consider the floor - the quietest possible signal that is still audible by human ears.

    This is a rather wishy-washy definition, but the convention is to take PB = 20 μPa = 0.00002 Pa exactly.

    So our 0 dB SPL reference point is when PA = PB: 0 dB SPL = 10 log10(0.000022 / 0.000022) = 10 log10(1) = 10 (0) = 0.

    What if the pressure level is 1 Pascal? This is a quite loud sound, somewhere between heavy traffic and a jackhammer.

    1 Pa in dB SPL =

        10 log10(12 / PB2) =

        20 log10(1 / PB) =

        -20 log10(PB) =

        -20 log10(2(10-5)) =

        -20 (log10 2 + log10 10-5) =

        -20 ((log10 2) - 5) =

        100 - 20 log10 2 ≈ 93.9794 dB SPL

    So 1 Pa is actually a tiny bit less than 94 dB SPL; it's closer to 93.98 = (100 - 6.02) dB SPL.

Page 1 of 1 (3 items)

January, 2014