Fun(c) with OCaml and Mazes

So today I stumbled upon a post I've wrote almost 3 years ago about solving mazes using OCaml (with graphics yes), and it was actually cool to download the code, type the compiling command and see it run without any issues (C programmers! behold).

So I decided to put the code on github for anyone to test and use (and fall in love with OCaml probably afterwards).

The code is available here https://github.com/martani/ocaml-maze, and it requires no more than a command to compile and run, it solves mazes with square and hexagon shapes.

Twitter on Windows Phone vs Twitter on Android

They say A picture is worth a thousand words, here is a comparison of the twitter app on Windows Phone and on Android. If they were both application on a desktop Windows computer for example!

Twitter on Windows Phone vs Android (Click to enlarge) 

Stealing Private Data of Facebook Messenger Users

I've received a few moments ago a message prompt on my facebook profile informing me that I can chat with my friends using the all new Facebook Messenger app on Windows. Lovely I said! something exciting should be behind this app.

Firstly my aim was to see if the app is stealing any data from its users (it turns out that it hashes the username and the mac address of the user to construct a unique identifier but this seems to be of no use after being hashed). After a little playing around, I've found that Facebook Messenger saves the UserID and the AccessToken in a file in the local application directory! Level of protection? facebook!

A quick look at the facebook graph API shows how easy it is to do whatever you want once you are armed with an AccessToken. Better yet! this application has by nature permissions to read the most sensitive piece of information on facebook, which is users' private messages.

Following are few lines of code that extract the UserId and the AccessToken used by the Facebook Messenger and then send a request to extract the user's favorite books, you can simply replace the fbObject variable with the value "Threads" to read all the user's private messages!

All one needs is access to a victim machine where Facebook Messenger is installed.

Example of this code running on my machine:

Panoramic View of Paris [Xperia Arc S]

I've received the Xperia™ arc S yesterday which I love very much. One of the features I like about this phone is the fact that one can take panoramic photos on the fly, and the great HD video shots along with the great screen.

Here are some shots I took today around Paris, use the mouse to navigate left/right; enjoy.
(You can view the pics in better dimensions here.)

Workaround to Access Windows 8 Start Menu Programs Again

If you have already tried the Windows 8 consumer preview, you have surely noticed that there is no start button anymore, which means no easy way to access your programs using the start menu as we used to do since forever.

Start Button missing in Windows 8

This is impractical since it means: whether you have to put some shortcuts on the desktop, or go to the metro start screen each time hoping to find the application icon there.

However, you can do a simple trick to access the whole start menu again.

To do this, right click the Super Bar and choose Toolbars -> New toolbar. In the dialog, choose the folder C:\ProgramData\Microsoft\Windows\Start Menu\Programs and click "Select folder".

Once added, you can click the arrows to access the programs and folders of the start menu, you can also drag it to the left so that it takes the start button's original place.

Start Menu items without a start button on Windows 8

You can also still access some parameters without having to go through the Control Panel shortcuts etc. by hovering over the left bottom corner of the screen and right clicking to get the following menu :

Factoring Large Numbers With Distributed Quadratic Sieve

Integer factorization is a problem that has its roots in the very far history, it is a fascinating problem (to me especially) that has gained a lot of attention in the recent years for cracking the RSA cryptosystem for example.

While having no time to blog about the internals of one of the very efficient methods to factorize relatively large numbers, I present here a simple implementation I have developed of the Quadratic Sieve to factorize relatively big RSA numbers. For a reference about the mathematical premises, the 6th chapter entitled Subexponential Factoring Algorithms of the Prime Numbers, A Computational Perspective book is pretty great.

The program available here is composed of 4 different versions, 3 centralized (sequential) and 1 distributed using MPI. The distributed version needs to be run on at least 2 nodes. The centralized versions consist of different implementation experiments : 

• The first one keeps the exponent vector of each smooth number (impractical due to the huge memory needed to keep the vectors).
• The second one sieves at an interval centralized at sqrt(N); according to my testing, this has no visible improvements over the standard one. 
• The last version which is the same as the first one but which uses only a binary exponent vector (saving one bit for each prime in the base) for the smooth numbers.

One of the caveats of this implementation is the linear algebra step that performs the Gaussian elimination. The method I am using is the most naive one (though goes pretty fast using XOR operations on GMP integers) which keeps an identity matrix besides the effective matrix while performing the Gaussian elimination, and hence the program needs twice the memory needed for the matrix.

The distributed version spawns as many nodes as needed and makes them all perform the sieving step, after some very hundreds of thousands of steps, the slaves communicate their found smooth numbers to the master which decides if they must stop or should continue sieving for more numbers. Sending GMP integers mpz_t over MPI was very challenging due to the way MPI handles the string representation of these numbers (sometimes '\0' are included at the end and the length returned does not represent exactly the number of characters in the string).  You can take a look at the functions doing the MPI send/receive of mpz_t here.

You will need the mpfr library too (for logarithm calculations) in case you want to test the programs, for the distributed version, compile with mpicc and run with mpirun as usual.

Results:

Centralized version:

Distributed version (60 intel i7 nodes):