Browse by Tags

Tagged Content List
  • Blog Post: Expressing a function f: GF(2⁸) → GF(2⁸) as a polynomial using a Lagrange polynomial

    I talked about Rijndael in a couple of previous posts: Generating the Rijndael S-box , Efficient multiplication and division in GF(2 8 ) , Sieving irreducible monic polynomials over a finite field , Addition and multiplication table for GF(2 2 ) . I'm going to talk some more about it today. The...
  • Blog Post: Generating the Rijndael S-box

    I talked about Rijndael in a couple of previous posts: Efficient multiplication and division in GF(2 8 ) , Sieving irreducible monic polynomials over a finite field , Addition and multiplication table for GF(2 2 ) . I'm going to talk some more about it today. One of the more interesting steps used...
  • Blog Post: Efficient multiplication and division in GF(2⁸)

    I talked about Rijndael in a couple of previous posts: Sieving irreducible monic polynomials over a finite field , Addition and multiplication table for GF(2²) I'm going to talk some more about it today. Rijndael does a lot of arithmetic operations (addition and multiplication) on elements...
  • Blog Post: Sieving irreducible monic polynomials over a finite field

    Last time we talked about the addition and multiplication tables for GF(2²) ; GF(2 8 ) is relevant for the Rijndael encryption scheme. Joan Daemen and Vincent Rijmen use a representation of GF(2 8 ) where each element is a polynomial of the form b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3...
  • Blog Post: Addition and multiplication table for GF(2²)

    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(2 8 ). A multiplication table of 256 elements by 256 elements quickly becomes a wall of text, so...
  • Blog Post: Why is 1 Pascal equal to 94 dB Sound Pressure Level? (1 Pa = 94 dB SPL)

    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...
  • Blog Post: Sample app for RECT functions

    Riffing on Raymond Chen's post today about SubtractRect I threw together a toy app which demonstrates three rectangle functions: UnionRect, IntersectRect, and SubtractRect. Usage: >rects.exe rects.exe union (left1 top1 right1 bottom1) (left2 top2 right2 bottom2) | intersect (left1 top1 right1...
  • Blog Post: An attempt to explain the twin prime conjecture to a five-year-old

    Back in April, Zhang Yitang came up with a result that is a major step toward proving the twin prime conjecture that there are infinitely many primes p for which p + 2 is also prime. In a reddit.com/r/math thread on the subject, I made the following comment as an attempt to explain the twin prime...
  • Blog Post: Generating sample first names

    I had a need to write a script that would give me a random first name. I grabbed the top 200 first names for baby boys in the US from 2000-2009, and the same list for baby girls: http://www.ssa.gov/OACT/babynames/decades/names2000s.html Boys Girls Jacob Emily Michael...
  • Blog Post: Grabbing large amounts of text from STDIN in O(n) time

    Last time I blogged about an O( n log n ) solution to finding the longest duplicated substring in a given piece of text ; I have since found an O( n ) algorithm, which I linked to in the comments. But my blog post used an O( n 2 ) algorithm to read the text from STDIN! It looked something like this...
  • Blog Post: Finding the longest substring which occurs twice in a given string

    I'm reading Jon Bentley's Programming Pearls and one of the interesting exercises was to find the longest substring which occurs twice in a given string of length n . There's a naïve solution where you look at every pair of (distinct) indexes ( i , j ), and calculate the length of the common...
  • Blog Post: Weighing the Sun and the Moon

    In an earlier post I mentioned how the Cavendish experiment allowed us to weigh the Earth - to determine the mass of the Earth m E . Newton knew the acceleration due to gravity on the surface of the Earth and was able to use that to find the product G m E ; Cavendish determined G directly, and was thus...
  • Blog Post: How many numbers are straights?

    As many people, I have to deal with a lot of numbers all the time (bug numbers, changelist numbers, tracking numbers, ...) and as a mathematician I sometimes notice when numbers have peculiar properties. For example, I recently ran into 152463, which is a straight (made up of consecutive digits, not...
  • Blog Post: Teaching someone to fish and the AKS primality test

    This morning my wife (whom I love and adore) woke me up at 3:00 AM with an urgent question. "Hey!" she said, shaking me awake. "Is 19 prime?" ... Like a fool, I answered her. "Yes. Yes it is." Off she went. This is a true response, but not a correct response. I realized shortly afterwards...
  • Blog Post: What is a perfect score in Yahtzee?

    The dice game Yahtzee takes thirteen turns. Each turn involves rolling a set of five dice (with two possible rerolls, the player having the option to reroll only a subset of the dice), then marking one of thirteen boxes and scoring points according to whether the numbers on the dice meet the rules of...
  • Blog Post: Generating primes using the Sieve of Eratosthenes plus a few optimizations

    When solving Project Euler problems I frequently need to iterate over prime numbers less than a given n . A Sieve of Eratosthenes method quickly and easily finds the small prime numbers; there are more complicated methods that find larger prime numbers, but with a couple of tweaks the Sieve of Eratosthenes...
  • Blog Post: Linearity of Windows volume APIs - render session and stream volumes

    We have talked about some of the volume APIs Windows exposes . We have also talked about what it means for a volume control to be linear in magnitude, linear in power, or linear in dB . We have also talked about how to read IAudioMeterInformation and how the limiter can attenuate full-scale signals...
  • Blog Post: Car Talk puzzler analysis - palindromic odometers

    Last week's Car Talk question was again of mathematical interest - it dealt with palindromic numbers on a car's odometer. (This is not the first palindromic odometer question they've done.) Read Car Talk's "Tommy's Drive to Work" puzzler question Short version: Tommy goes for a short drive ...
  • Blog Post: Translating Ada Lovelace - mathematical science is an instrument

    Lady Augusta Ada, Countess of Lovelace is credited with being the first computer programmer. The short version: her associate Charles Babbage gave a lecture on his Analytical Engine in Italy; an Italian engineer wrote up a report on his lecture, in French; Lady Ada then translated the report...
  • Blog Post: Car Talk puzzler analysis - Limerick equation

    Car Talk's puzzler of the week has some mathematical interest. See Car Talk's transcript of the question. In brief, we are given the equation... (12 + 144 + 20 + 3√4) / 7 + 5(11) = 9 2 + 0 (which holds true, by the way) ... and asked to transcribe it as a limerick. ...
  • Blog Post: Linearity of Windows volume APIs - IAudioMeterInformation and full-scale signals

    We have talked about some of the volume APIs Windows exposes . We have also talked about what it means for a volume control to be linear in magnitude , linear in power , or linear in dB . The attachment to this blog post contains: An app I wrote to exercise the IAudioStreamVolume, ISimpleAudioVolume...
  • Blog Post: Basic audio volume theory

    Last time we talked about the different Windows Audio Session APIs for setting volume. Let's talk a little about what volume means. For purposes of illustration, let's take our signal to be a full-scale square wave: Incidentally, the answer to the exercise completely characterize the set...
  • Blog Post: Generating formulae for polygonal numbers (triangular, square, pentagonal...)

    The formula for square numbers is easy to remember: s n = n 2 There are also triangular numbers, pentagonal numbers, hexagonal numbers, and in general k -gonal numbers. These have formulae too... for example, triangular numbers: t n = n ( n + 1) / 2 ... but they can be hard to remember. If you see...
  • Blog Post: How much is a perfect Jeopardy! score?

    Some sports and games have a notion of a "perfect score." For example, a perfect score in bowling is 300 (twelve consecutive strikes;) a perfect score in golf would be 18 (18 holes-in-one.) After watching Watson destroy Ken Jennings and Brad Rutter I began to wonder what a perfect score in Jeopardy...
  • Blog Post: Phase and stereo-to-mono downmix

    Warning: trigonometry ahead. Last time we looked at how to downmix a stereo signal to mono ( M = L /2 + R /2). The resulting M signal can only be as powerful as the L and R signals if they are perfectly correlated ( L = R ); if the L and R signals are uncorrelated (no relationship between L and R...
Page 1 of 2 (49 items) 12