Finding Collisions

Some time ago, a friend was trying to find an efficient way (storage and time complexity) to find collisions for a (secure) hash function. Hashing random keys until you get a collision is reminiscent of von Mises’ birthday paradox.

In is simplest form, the birthday paradox states that, amongst (randomly) gathered people, the probability that (at least) two share a birthday increases counter-intuitively fast with the number of gathered people. This mean that even if your hash function is random (i.e., strong), you may not have to try a very large number of random keys before finding collisions. Or does it?

OpenMP and The N Queens Problem

Now that we all have multi-core CPUs (multiple cores, simultaneous multi-threading, with uniform memory, etc.) I think it’s about time we really get the hang of it.

However, correctly threading applications is hard in general, and not all applications can gain significantly from parallelism. But some applications are embarrassingly parallel by their nature, and in this case, breaking down the problems into independent sub-problem is not hard at all, often requiring little more synchronization than waiting for all worker threads to finish.

Wallpaper: Concrete Art

(Concrete Art, 1920×1200)

Wallpaper: Fast Forward

(Fast Forward, 1920×1200)

Wallpaper: Stainless Entity

(Stainless Entity, 1920×1200)

Wallpaper: Moria

(Moria, 1920×1200)

Drawing Random Numbers from Disjoint Ranges (Generating Random Sequences V)

On a number of previous installment of this series, I’ve discussed permutations, generating uniform random points in a triangle, on a sphere, the inversion method, even recycling expensive random bits. In this entry, I will use the rejection method to generate random numbers from disjoint ranges.

For simplicity, let us consider only the uniform case, where all values are equally likely to be drawn. So instead of drawing a number from a range, say , we’re interested in the case where the set is composed from several intervals, something like . We may think of drawing uniformly from and retry if we “fall in the gaps”, that is, if we draw a number in or .

A first, it doesn’t seem like a bad plan, especially if the “holes” are rather small and easy to miss—that is, we have a good chance of hitting in an allowable range in a very few tries. For example, if the ranges we’re interested in look like and , drawing from really doesn’t sound like a good idea.

But what if we compacted the ranges?

UEID (Unique Enough IDs, part 2)

As part of an open-source project I’m working on (right now, we are still at the technical feasibility stage where we explore and eliminate technical risks, full disclosure will come later) we have to issue session numbers. They’re not session numbers in the usual sense, but they still need to be unique, and not amenable to simple attacks.

There are a couple of ways of generating unique session numbers. RFC 4122-compliant unique IDs is one possible way.

Quadrature Encoding

The nice thing about the trigonometric circle is that it is, quite so indeed, a circle. But it’s also a disadvantage when you consider the implementations of functions manipulating angles, especially .

This is particularly a problem when you’re not so much interested by a specific angle (which is at all time always well-defined) than by a series of angles varying in time. If you’re certain that your angle is always within or within , you do not expect problems. What if, on the contrary the angle wraps around?