2 Jul 2007 fzort   » (Journeyer)

I shall start using my Advogato account more often. If that bothers you, feel free to lower my journal's rating. I entertained the idea of using Livejournal of Wordpress or something for my random ramblings, but both are blocked from work.

OMG BRUCE SCHNEIER CAUGHT WRONG IN PRINT LOL

In Applied Cryptography, latest edition, in the subsection on the Chinese Remainder Theorem, the following code is given without justification:


/* r is the number of elements in arrays m and u;
   m is the array of (pairwise relatively prime) moduli
   u is the array of coefficients
   return value is n such than n == u[k]%m[k] (k=0..r-1) and
                               n  < m[0]*m[1]*...*m[r-1]
*/
int
chinese_remainder(size_t r, int *m, int *u)
{
    size_t i;
    int modulus;
    int n;
    modulus = 1;
    for (i=0; i<r; ++i)
        modulus *= m[i];
    n = 0;
    for (i=0; i<r; ++i) {
        n += u[i] *
          modexp(modulus/m[i], totient(m[i]), m[i]);
        n %= modulus;
    }
    return n;
}

This does not work. bi observed that it could be made to work if the line in boldface was changed to:


n += u[i] * modexp(modulus/m[i], totient(m[i]), modulus);

Weirdly for a decade-old book, this is not in the latest errata.

Coding

I don't get to do much of that at work. When I do, it involves maintaining the Worst Code Ever. In order to avoid becoming this guy, I've been playing a bit at sites like SPOJ, acm.uva, and Project Euler. It's less demanding than trying to participate in a more or less relevant free software project, and you're rewarded for doing just the (at least for me) interesting part of programming, that of actually solving problems.

In the process, I've been accumulating a body of math factoids such as a formula for the size of the Farey sequence of order n, or wtf a Farey sequence is for that matter. I should start documenting that sort of stuff in my page sometime.

Listening to

Sarah White - You're Not Easy, You're Hard

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!