## Visualizing group structure, part 2: prime vs. composite, CRT

Some time ago I’ve generated colored addition/multiplication tables in order to visualize group structure. My idea was to compare extension fields of same order with different reduction polynomials, and to compare elliptic curve groups with groups of integers modulo a prime ($\mathbb{Z}_p$). However, as pointed out by an attentive reader, I’ve messed up claiming that the latter group is used by RSA. It is not, it’s used for e.g. DSA, while RSA uses a composite modulus: the product of two prime numbers.

So, how do $\mathbb{Z}_p^*$ and $\mathbb{Z}_n^*$ compare?

## The C language still surprises me

What does this code print?

 1 2 3 4 5 6 7 8 9 10 11 12 #include   int main() { signed char x = -128;   if (x < 0) { x = -x; } printf("x = %d\n", (int) x); return 0; }

I’ve been reading Matters Computational, an excellent (free) book by Jörg Arndt about programming and algorithms. It surprised me in the very first pages with this pitfall in two’s complement – there is always a number that is equal to its own negative, besides zero. The code above prints −128!

In hindsight, it’s pretty obvious. A signed char can hold values from −128 to 127 — that is, there are 127 positive numbers and 128 negative numbers! Therefore, it’s impossible to the unary negative operator to be one-to-one. The smallest negative number will always be mapped to itself. Of course, this also applies to int, etc.

The main implication of this fact is that, after the innocent-looking code

 if (x < 0) x = -x;

x is not guaranteed to be positive!

## Understanding the Montgomery reduction algorithm

The Montgomery reduction algorithm finds the remainder of a division. Many cryptographic schemes work with numbers modulo a prime. When you have to multiply two numbers with e.g. 128 bits each, first you multiply them the usual way (there are many techniques for this) to obtain a 256-bit (“double precision”) number. Then you need to reduce this result modulo the prime you’re working with, that is, compute the remainder of the division of this number over the prime.

You can compute the remainder of a division with the “schoolbook” technique everyone learns in school, but that is expensive and requires divisions, with are costly in many platforms (some microcontrollers don’t even have a division instruction). Montgomery reduction only needs a division by a powers of the integer size, which are cheap for computers.

Here I’ll try to explain how it works, in an informal approach. For detailed proofs of its correctness, check e.g. the chapter 14 of the Handbook of Applied Cryptography or the original paper.

## Understanding the extended Euclidean algorithm

The Euclidean algorithm finds the greatest common divisor of two numbers a and b. There is an extended version of it that also finds two numbers x and y such that ax + by = gcd(a,b). This is useful when searching for modular multiplicative inverses.

The algorithm is simple, but I’ve never bothered to study why and how it works (a shame, really, but sometimes you have to postpone the understanding of some basic things in order to go on…). Finally I’ve decide to put some thought on it and came up with this (this is not a proof; it’s just some intuitive thinking to grasp the inner workings of the algorithm).

## The black magic of GDI+

One of the things I am most ashamed of on Quivi is its speed when opening large images (which are not uncommon nowadays, specially with digital photos). It’s embarrassing that the lame Windows Picture and Fax Viewer is lightning fast when opening those images!

I’ve always wondered how the Viewer did that. I’ve searched about it in the past but could never find anything about it. Then one of these days I was browsing the Wikipedia page about the Viewer and there I learned that it uses GDI+.

GDI+ is a C++ library, but it is built upon a flat C API which I could easily use in Python via ctypes. Long story short, I was able to modify Quivi to add support for viewing images with GDI+. And the result was amazing!

What about Linux? Well, something “equivalent” to GDI+ would be Cairo, so I did some tests with it too (luckily, support for it was included in wxPython recently).

Here are the results for the time to load a huge 5704px x 5659px PNG image and rescale it to 1/20 of its size:

Time to load and scale a PNG image
Library Time (s)
FreeImage 10.38
PIL 9.90
GDI+ 2.22
Cairo (from FreeImage) 3.60
Cairo (direct) 3.28

The reason for the two Cairo timings is that it supports reading directly from a PNG file but for e.g. JPG files you need to read the image with another library and to the format Cairo uses. I’ve used FreeImage to load the image and converted it to a Cairo surface.

Here are the results for the time to load and scaling the same image, but as a JPG:

Time to load and scale a JPG image
Library Time (s)
FreeImage 6.91
PIL 8.38
GDI+ 0.19
Cairo (from FreeImage) 1.43

Scary! How does GDI+ manages to do that? According to Wikipedia it uses hardware acceleration… Cairo doesn’t lag begind considering that the scaling only takes 0.015 (!) but I did notice that even its best quality scaling isn’t so good in comparison to the others, which is kinda odd.

Anyway, I’ll try to release a new version of Quivi with GDI+ and Cairo support soon. Stay tuned.

## VirtualBox rocks

I’ve just tried VirtualBox and it simply rocks. I was using VMWare Player and got sick the lack of features. Yes, there’s VMWare Server, but it lacks desktop friendliness. VirtualBox provides the best of both worlds.

(For those not familiar, VirtualBox is a virtualization software: it allows you to create virtual machines, so you can, for example, run Ubuntu inside Windows as a “normal” program, or run Windows inside Ubuntu, or whatever.)

Its “Seamless mode” is very nice: it allows you to treat windows in the guest OS like they were windows in your host OS. (VMWare Player has a “Unity mode” which should do the same thing, but I couldn’t get it to work).

It’s incredibly easy to use, allows you to create your own virtual machines, easily install “Guest Addition” (the equivalent of VMWare Tools, which is a pain to install), mount iso images, use USB drives, etc.

The only downsides I could notice so far is that it’s very slow to suspend/resume and its seamless mode is not that seamless: for example, if you maximize a window after entering seamless mode, the growth area will be invisible; you have to maximize it prior to changing to seamless. Also, Alt+Tab is not “seamless”; it would be so nice if you could switch between host and guest applications with it! It would be probably hard to implement, though…

## Yet another silly Python vs Java comparison

I’ve been hacking the mspsim (a simulator) source to add support for a couple of stuffs in its profiler. At a certain point I had a hash table mapping functions to how many times they were called, and I had to sort them by that number of times. How to do that?

Collections.sort(list, new Comparator<entry>() {
@Override
public int compare(Entry o1, Entry o2) {
return o2.getValue().compareTo(o1.getValue());
}
});

And if it were Python:

lst = sorted(((n, fn) for fn, n in callers.iteritems()), reverse=True)

Yep, Java can be a pain.

Of course it’s not that simple, though. I’ve tested another simulator in Python and its code is very nice and readable and warm and fuzzy…

…but it’s 30 times slower than the Java one.

The Sandbox WordPress theme is a nice bare bones theme which can be easily used as a base to your own themes (preferably with a style.css file only, following the zen). The only problem is that its development is kinda frozen and it does not support new WordPress 2.7 features like threaded and paged comments.

There are already some hacks to support them but I decided to take another approach. Since the comment loop was changed drastically, those hacks had to… well, hack away in order to keep backward compatibility with Sandbox-based themes. Instead, I decided to embrace the new comment loop in WP (which is simple and doesn’t allow much customization without resorting to the hackish callback, but it generates code very close to what Sandbox does).

If you like the idea, feel free to download my customization (just overwrite the comments.php and header.php in Sandbox). You’ll probably have to tweak your previous themes a little, though.

Tip: if you want do get rid of the “says:” in the comments (e.g. “Alice says:”), put this in your stylesheet:

.says { display: none; }

…and I’ve not activated it in this blog for now, since it barely gets comments. Sorry, no live preview 🙂

## The Frobenius endomorphism with finite fields

The Frobenius endomorphism is defined as:

$\Phi(x)=x^p$

where p is the characteristic of the ring you’re working with. Simple, right?

If you’re working with a field with prime order, then Frobenius is actually the identity map. Since the order of the multiplicative subgroup is p, when you raise to the power of p you get back to x due to Fermat’s little theorem. Things get more interesting when you’re working with a extension field (i.e. a field which order is a prime power).

I’m studying pairings for my master’s degree and the Frobenius endomorphism appears all the time in their computation. For example, you need to do a “final exponentation” which can be split in multiple exponentiations, and some of them are to the power of p. This is good because powering to p is “easy” due to Frobenius, or at least all the papers I read said so. But for a while I couldn’t see why, and that’s the reason I’m posting this. It’s really easy; it’s just not that obvious to see why.

## Quivi for Linux released

I’ve just released the Linux version of Quivi:

Quivi is an image viewer (specialized for comic/manga reading) for Windows which supports many file formats and compressed (zip, rar) files. It is aimed for fast & easy file browsing with keyboard or mouse.

It was working on Linux for a while, but now it’s “official”. I’ve released a .deb package which was tested on Ubuntu and may work on Debian. There’s also, of course, the source code, which requires some dependencies to be installed. You can grab both at the download page.

Help on packaging is much welcome, since I don’t have any experience releasing stuff for Linux. And please tell me if there is anything wrong with the release.