Visualizing group structure with colored addition/multiplication tables

2008-12-07 – 01:32

When working with finite fields, if the number of elements is a prime power p^m with m > 1, you can represent the elements as polynomials with degree m-1 and do the field addition and multiplication modulo a irreducible polynomial with degree m.

The field GF(5) is composed by the numbers 0 to 4. We don’t need to represent its elements as polynomials since m=1. Addition is done modulo 5 and multiplication also modulo 5. So 2 + 3 = 0; 4 * 2 = 3; and so on. This is the addition table for GF(5):

Multiplicative table of integers modulo 5

The rows, top down, represent 0 to 4. The columns, right to left, represent 0 to 4. Each square is the result of the addition of the respective numbers in the row / column it belongs to. Black is 0, purple is 1, red is 2, orange is 3, yellow is 4.

In the field GF(25) = GF(5²), as I said, you represent each element as a polynomial. So we have 25 elements: 0 to 4; x, x+ 1, …, x + 4; 2x, 2x + 1, …; 3x, 3x + 1, …; 4x, 4x + 1, …, 4x + 4.

In order to add two elements, add them as you would add two polynomials, but remember that the coefficients are in GF(5); for example, in GF(5²), we have (3x + 2) + (4x + 4) = (2x + 1). In order to multiply two elements, multiply them as usual but then take the result modulo an irreducible polynomial. So, with GF(5²) modulo x^2 + 4x + 2, you have (2x + 5) * (3x + 4) = (4x + 3).

I always wondered what would happen when you changed the modulus. Obviously the group “changes”, but in order to actually see it, I’ve built the multiplication table for GF(5²) modulus x^2 + 4x + 2 and x^2 + 3x + 3:

Multiplicative table for GF(5^2)/(x^2+4x+2)Multiplicative table for GF(5^2)/(x^2+3x+3)

Yep, they’re different :D

Of course, both are isomorphic, so you’re free to pick your favorite modulus.

Multiplicative group of integers modulo n vs group of points in a elliptic curve

Then I got curious: how would the multiplication table of integers modulo n look like? This group is the group used in many cryptographic schemes, like RSA. This is the multiplication table for integers modulo 509:

Multiplicative table for integers modulo 509

Pretty (and trippy)!

What about the group of points on a elliptic curve over a finite field, which is also a group used in cryptographic schemes? This is the additive table for the points on y^2 = x^3 + 4x + 1 over GF(503):

Additive table for points in y^2 = x^3 +4x + 1 over GF(503)

The difference between them is striking; the elliptic group seems almost random. This is (intuitively speaking! I’m not being formal here) the reason why this group is used in cryptography in the first place: since the group structure is more “messed up”, you can get away with using groups of much smaller size (no smaller than 2^{160} elements) than with multiplicative groups of integers modulo n (no smaller than 2^{1024} elements). This is not set in stone though; maybe someday someone will come up with a better method to crack this seemingly random structure (for now the best method to solve the discrete log problem for elliptic groups is exponential, while the best method for integers modulo n is sub-exponential).

It’s worth mentioning that even this elliptic group is not that extraordinary: it is isomorphic to the very simple additive group of integers modulo 506:

Additive table of integers modulo 516

The big problem is to find the isomorphism! You can see this better with a small example. This is the elliptic group of y^2 = x^3 + 3x + 2 over GF(5) (left) which is isomorphic to the additive group modulo 5 (right):

Additive table of points on y^2 = x^3 + 3x + 2 over GF(5)Additive table for integers modulo 5

(OK, it’s not that easy to see)

Software

To generate those images, I’ve used Python with PIL and Sage. Sage aims to be a open source replacement for (expensive) software like Magma, Maple, Mathematica and Matlab. Since I’ve never used those, I can’t really say how it is going in its mission, but it’s really awesome. If you’re a Windows user you’ll probably be scared by the fact that the Windows version of Sage is actually an entire Linux virtual machine! They’re working to port it natively, but even until then, it’s worth it (and you’ll have an excuse to try Linux ;) )

Update

Someone asked for the source code used to generate those. It’s ugly (I’ve added comments at least) but you can download it here: the sage script and the python script. In the sage script, uncomment the lines representing what you want to plot, then run ./sage gentable.sage (or whichever path to were sage is). It will generate a data.txt in the same folder. Now run python plottable.py img.png to plot it on the img.png file (or omit it to show on the screen). You’ll need to have PIL installed.

If you don’t want to plot fancy stuff as elliptic groups, you can easily transform the gentable.sage into a normal Python script and write the addition/multiplication yourself (like a + b % n). Have fun, and feel free to ask anything.

By Conrado | Posted in Cryptography, Math | Tagged , , , , | Comments (2)

Access violation errors with callbacks in ctypes

2008-10-11 – 14:19

I’ve just spent a few hours trying to solve this bug, so I’m publishing this so maybe it will help someone with this issue…

Assume that you’re working with a DLL/.so library through ctypes in Python, and this library allows you to set a callback for some other function. In my case, I was working with unrar.dll. The code was something among these lines:

UNRARCALLBACK = ctypes.WINFUNCTYPE(ctypes.c_int, ctypes.c_uint, ctypes.c_long, ctypes.c_long, ctypes.c_long)
 
#in a class...
RARSetCallback(self.handle, UNRARCALLBACK(self.callback_fn), 0)
RARProcessFile(self.handle, RAR_TEST, None, None)

The first lines constructs the function prototype, the second sets the callback in a function of the DLL file, and the third calls a function in the DLL which will call the callback.

Can you spot the error?

The code worked fine in Python 2.5, but then I changed to 2.6 and it stopped working. I got a “WindowsError: exception: access violation reading…” (or writing) exception in the third call.

The reason, which is obvious in hindsight, is cleared explained in the docs:

Make sure you keep references to CFUNCTYPE objects as long as they are used from C code. ctypes doesn’t, and if you don’t, they may be garbage collected, crashing your program when a callback is made.

(Though it’s not explicit, it applies to WINFUNCTYPE objects too)

The WINFUNCTYPE object created in the second line no longer exists in the third line, so when the callback was called, it no longer pointed to a valid address. The solution is simple — just keep a reference to the object:

UNRARCALLBACK = ctypes.WINFUNCTYPE(ctypes.c_int, ctypes.c_uint, ctypes.c_long, ctypes.c_long, ctypes.c_long)
 
#inside a class...
self.callback_ref = UNRARCALLBACK(self.callback_fn)
RARSetCallback(self.rarFile.RAR._handle, self.callback_ref, 0)
RARProcessFile(self.rarFile.RAR._handle, RAR_TEST, None, None)

The only mystery left is why the old code worked on 2.5!

By Conrado | Posted in Programming | Tagged , | Comments (0)

Quivi 1.0 released

2008-09-21 – 22:40

I’ve just released the new version of my image viewer and manga / comic reader, Quivi (only for Windows right now, but it will be ported to Linux and maybe to Mac). I’ve rewritten it from scratch, check my last post for more info.

The new features added were:

  • Prefetching of the next image
  • Wallpaper dialog
  • Start directory option

But that is only the beginning; now it will be much more easy for me to work on Quivi.

There are many comic readers around; like CDisplay (outdated, but very popular), Comical and Comix. They have much more features than Quivi, and I must admit that I often thought on giving up on Quivi. But I just couldn’t.

I wrote it mainly for myself; when I started there was only CDisplay. The first version was written with Visual Basic (go on, laugh). Then I changed to C++. And now I changed to Python, and I hope this is the last language change :) It’s a hobby project that I grew to love. It suits my needs, but I’d really like to suit the needs of other people too!

It is scary when you realize that people are using your software. I feel responsible; wherever I find someone criticizing it, I feel guilty for not attending those people needs. Yes, that’s stupid, but it’s how I am. At the same time, though, it’s awesome to know that there are people who like it and find it useful.

If you have any suggestion, comment, complain about Quivi, please send it to me!

By Conrado | Posted in Software | Tagged | Comments (0)

Why I rewrote Quivi from scratch

2008-09-20 – 23:31

Joel Spolsky, popular software engineering, said in this blog:

(…) They [Netscape] did it by making the single worst strategic mistake that any software company can make:

They decided to rewrite the code from scratch.

I agree, mostly. Many projects market that they’ve been “rewritten from scratch” as if it was something marvelous, and most of time, it’s just a sign that the new version probably has more bugs than the previous. But, wait, I just rewrote Quivi (a image viewer and comic / manga reader) from scratch! Well, why?

Well, I thought I really had to justify this. So here are the reasons:

  • It is a small project. Rewriting it certainly isn’t as hard as rewriting a browser!
  • I couldn’t stand C++ anymore (the programming language I used before). Of course, this isn’t C++ fault per se. It has its uses — the right tool for the right job, and so on. But to write an desktop application? It’s overkill. If you manage to pull it of, hey, kudos to you. But I had no motivation to work on it anymore.
  • I love Python (the programming language I use now), and of course, I’m not the only one. Programming is fun in Python, so much that had the motivation to rewrite Quivi from scratch in the first place! And of course, it will be much more easier for me to keep working on Quivi.
  • I could change GUI libraries. SmartWin is a nice library, and uses templates in very interesting ways; when programming Quivi I ended up involved with its development too. But it has its bugs, and because it uses templates extensively, it’s awful slow to compile an application that uses it. I’ve changed to wxPython, which is a very mature GUI library - and cross platform to boot.

Of course, there are some downsides with the change. The whole software package is much bigger due to the dependencies (the installer jumped from 900K to 5MB!). And the program is a little bit slower, mainly when starting up, and uses more memory (9MB to 30MB with no images loaded). But I think it was a good enough trade-off.

Rewriting from scratch must be considered carefully, and in this case, I think it was a good idea. Quivi is a hobby project, and I guess the main point of it is to have fun writing it, and to make users happy. I hope I can do both with this new version (which will be released soon).

By Conrado | Posted in Programming, Software | Tagged , , , | Comments (2)

Closure gotcha (with Python)

2008-07-17 – 15:34

Do you know what a closure is? Basically, it’s a function created at runtime that references variables defined in a outer scope. For example:

def make_number_printer(n):
    def number_printer():
        print n
    return number_printer
 
printer = make_number_printer(5)
printer()

The function make_number_printer receives a number and returns a function which, when called, prints that same number. It’s not the most useful function in the world, but it does show how closures work. In this case, the number_printer function is a closure, because it references the variable n which is in an outer scope (of the make_number_printer function).

My intention here, though, it’s not to explain what closures are but to show a property of them which may cause some confusion (and made me spent quite some time hunting for a bug caused by it). What does this code prints when run?

printer_lst = []
for i in xrange(10):
    def number_printer():
        print i
    printer_lst.append(number_printer)
 
for printer in printer_lst:
    printer()

It loops between 0 and 10 creating a number_printer function and appending it to a list. Then it loops through the functions of the list, calling them. You would expect it to print the numbers 0 to 9, right?

Wrong! It prints the number 9 ten times.

The problem is that most people (including me, before learning this) think that closures work by evaluating the variables in the outer scope and storing their values to use when necessary. But actually they keep an reference to those variables, and if their contents change, the closure will use the new value. Since our variable i stores the value 9 after the closures are created, that is the value they will print. This happens even if the variable i goes out of scope after the closures are created (e.g., if the first for were inside a function).

So how to solve this? You can move the creation of the closure to another function, like this:

def make_number_printer(n):
    def number_printer():
        print n
    return number_printer
 
printer_lst = []
for i in xrange(10):
    printer_lst.append(make_number_printer(i))
 
for printer in printer_lst:
    printer()

Here the closure will reference the variable n, which has different instances for each different closure created. Another alternative is to use a somewhat contrived Python “feature” which is the fact that default parameter values are evaluated when the function is defined and not when they are called:

printer_lst = []
for i in xrange(10):
    def number_printer(x=i):
        print x
    printer_lst.append(number_printer)
 
for printer in printer_lst:
    printer()

When def number_printer(x=i): is run, the variable i is evaluated and its value is saved in the function definition; so, each time the function is defined (i.e., the closure is created), the current value of i is “frozen”.

If somebody is thinking, “but I’ll never run into this situation”, here is a little more real example (which actually happened to me when I was coding a Flash game, which uses ActionScript). Basically it’s the same code above and has the same issue:

class Button:
    #This is a dummy Button class; suppose
    #it's part of a GUI library and for some reason
    #you can't subclass it
 
    def __init__(self):
        self.listener = None
 
    def set_click_listener(self, fn):
        self.listener = fn
 
    def on_click(self):
        self.listener()
 
#Create 10 buttons...
buttons = [Button() for i in xrange(10)]
#And suppose the buttons are added to the GUI after
 
#Set the listeners to the click event.
#The number of buttons may change in the future
#and all of them have the same code, the
#only difference is the button index. So it's better
#to do this within a loop. 
for i in xrange(10):
    def on_click():
        #Suppose there is something more useful here
        print i
    buttons[i].set_click_listener(on_click)
 
#Simulate a click in each button
for j in xrange(10):
    buttons[j].on_click()
By Conrado | Posted in Programming | Tagged , | Comments (0)