Archive for 2011

Factoring Integers: Part 1 - Pollard's rho Method

I'll be developing a program for factoring numbers (especially RSA numbers), the goal is to have a parallel quadratic sieve program running on GPUs (using CUDA or OpenCL) to factorize RSA numbers.

I have just started playing around GMP so I implemented a naive version (in C) of the Pollard's rho factoring method, it uses the optimisation technique proposed by Pollard and Brent, however it doesn't check for cases that may cause the algorithm to fail.

In order to compile this program, you need to have GMP installed.
You can invoke the program with ./pollard-rho NUMBER or ./pollard-rho p q where the number to factorize is p*q.

Compile : gcc pollard-rho.c -o pollard-rho -lgmp -lm

Rolling Back a Project to Windows Phone OS 7.0 After an Upgrade to 7.1 (Mango)

If you had a project that was developed before the Mango SDK was available, or a project that was created with the Windows Phone 7.0 as the target platform and wanted to upgrade to 7.1, then there is no way to roll back to 7.0 again, which means that your app will be available only for those who have Mango updated devices.

On creating a new Windows Phone project with the Mango 7.1 SDK tools installed, Visual Studio prompts you for the target platform:
If for any reason, you want to upgrade the app to take advantage of the 7.1 SDK (use background agents, live tiles' animations etc..), you go to Project -> Project properties and set the target to OS7.1:
Once the Windows Phone OS7.1 version is selected, Visual Studio shows the following warning stating that once upgraded, the application cannot roll back to Windows Phone OS 7.0 anymore :

Because the referenced projects are not upgraded with the app, there is actually a way to roll back anyways, even if Visual Studio warns it is not possible.

First in the WPAppManifest.xml you need to change the AppPlatformVersion back to "7.0". Then unload the project from Visual Studio and open your *.csproj with a text editor. Locate <TargetFrameworkProfile>WindowsPhone71</TargetFrameworkProfile> and change it to <TargetFrameworkProfile>WindowsPhone</TargetFrameworkProfile>.

Reload the project in Visual Studio, and voila, it's back to version 7.0.

Hope this helps.

Posted in , |

Bloginto 2.1 Now Available

Bloginto 2.1 is available for download from the Google Chrome Web Store, the 2.1 version is a patch to the 2.0 version after the (abrupt) changes of Bloginy Algeria.

Bloginto is a Chrome extension that brings Bloginy Algeria and Morocco feeds to the browser. With Bloginto you can:

  • Read the live feeds of Bloginy Algeria and Morocco
  • Keep track of the new feeds and get notified whenever newer news are available
  • Keep track of the read and unread feed entries
  • Vote for the feed entries directly from the browser with 1 mouse click
  • Tweet directly through the extension

Bloginto is an open source extension, you can grab the source code from here, you can suggest amelioration and patches too.

nanosleep(), usleep() and sleep() Precision Tests

Working on some Amazon EC2 benchmarks I run through few problems of having my processes to run with a high time precision where a more than 1ms shift between operations is not acceptable.

My program accumulates work time and sleep time, ideally, it would work for time t, sleeps for T - t microseconds and loop again. The problem is that in the sleep routine, a shift of few microseconds can be accumulated to become a shift of milliseconds after few loops.

After investigating the problem a little, I did some tests on how precise are the sleep functions in C, here is the code I used to test nanosleep(), usleep() and sleep().

Running these tests on my machine with Fedora 15 gives me these results :

As you can see, there is always an overhead of 100µs to 180µs, a call to printf inside the function will take about 70 µs more to execute. The call to the function itself (the nsleep function) takes at worst 1µs. With this accumulation of  microseconds, a program would get to a state where it is late by some milliseconds after a dozen of iterations and calls to these sleep functions.

On the other side gettimeofday() behaves pretty well considering precision, the benchmark below (found here) gives the following results:

$ ./gettimeofday_benchmark
50000000 cycles in 2315879542 ns = 46.317591 ns/cycle
Which is satisfying for its precision.

A solution (that is not applicable in all cases) is to have a global program independent clock regarding to which the sleep period is adapted. For example instead of waiting T - t microseconds, one will use every second tick on the system as a landmark, and thus any microseconds lost in the last loop iteration are discarded in the next one since the wait time is not dependent on the time the loop has started.

NYTimes Newsreader and LeParisien Journal for #WP7

I've developped lately two new Windows Phone apps which are newsreaders based on RSS for the New York Times newspaper and Journal.

The two apps come in two versions,a free version which is ad-powered and a paid version which is ad-free. Following is a brief description and download links for the two apps.

NY Times Newsreader :

Read the NY Times newspaper directly on your Windows Phone device.

The NYTimes Newsreader gives you access to all the major sections of the NY Times newspaper organized in categories for easy and fast navigation with full articles view using the NYTimes' RSS feature.

- Browse news by categories (7 categories and more than 40 sections)
- Front page news
- Articles thumbnails
- Share articles by email and SMS
- Favorite your articles to read them later
- Read full articles directly from NYTimes Newsreader

- World
- Op-Extra (Opinion, Columnists, Editorials, Magazine ...)
- Technology
- Science
- Sports
- Arts
- Business


Download (FREE version)

LeParisien :
Suivez toute l'actualité française et internationale avec Journal sur votre Windows Phone

Accédez à l’intégralité des articles de classés par rubrique (5 rubriques et plus de 30 catégories)

> Sauvegardez vos articles favoris pour une consultation ultérieure
> Partagez l’information avec vos amis via Email ou SMS

Accédez en un clic aux dernières news :
- L'info du Parisien
* Politique
* International
* Faits divers
* Economie
* Société
* Loisirs et spectacles
* Médias et people
* Automobile


Download (FREE version)

Posted in , |

Beta SMS 2.0 Now Available On Windows Phone 7

Beta SMS 2.0 is now available on the Windows Phone 7 Market place with a lot of enhancements and new features.

Beta SMS lets you send very cheap and even free^ short text messages internationally by using your favorite web SMS or VoIP provider. It offers a very intuitive way to send SMS directly from your Windows Phone, without having to log into your provider's website each time you want to send an SMS.


- SMS History
- Contacts support
- Balance check on all the supported services
- Managing and sending SMS from multiple providers at the same time
- Switch between multiple account in one tap
- A beautiful user interface that looks and feels like the native WP7 SMS app.

Supported services

In order to user Beta SMS, you need an account with one of the following providers:

- SMS Global
- Cherry-SMS
- Sloono

If your favorite service is not supported yet by Beta SMS, please request it here.

s1             s2             s3s4             History new

You can download Beta SMS from here :
Downlaod Beta SMS
More info on

Win a Free Domain Name (Registered For 3 Years), 3rd & Last Message

This is the 3rd and last message of the series to win a domain name registered for 3 years.

Once decoded, send the clear message and your email from the “contact me” page, remember, first to decipher the 3 messages wins.





Instructions :


You need to decipher the first (fairly easy) two messages (the second is easier than the first). Message 1 here, message 2 here.


(competition always open closed)

Winner : Mohieddine Abd-kader,

Posted in |

Cracking The Vigenere Cipher

I wanted to use Vigenere as the cipher for the 3rd message on the competition to win a domain name, but changed my mind due to the number of online tools that might help decode this cipher easily even if you know nothing about how Vigenere works.

Before you start reading about how deciphering Veginere works, I invite you to take a look how Vigenere is used to cipher messages from the Wikipedia article here. In fact, Vigenere was called “le chiffre indéchiffrable” or the undecipherable cipher, because any means of cryptanalysis invented before it was defeated, till Charles Babbage found a clever, very clever, way to crack it.

After finishing reading the Code Book the last week, I started decoding the different enigmas proposed at the end of the book; and yesterday I started deciphering the 4th enigma which is a Vigenere cipher (that I finished yesterday too), and I find it pretty amazing for starters to try. I must mention that this short article will contain the solution to the enigma.

I chose to go old way while deciphering this, finding the key by hand, then decoding the message step by step.

0. The message to decode :


The complete message can be found here.

1. Finding the key length:

Babbage’s method for finding the key length was that the repeated text in the ciphered message is probably produced from the same repeated letters from the clear message and which are ciphered with the same part of the key. Hence, finding an estimate between the repeated series of letters in the ciphered message would give us a good hint about the length of the key.

Clear : T H I S I S A C L E A R T E X T T H I S C A N B E E A S L Y D E C
Key :   C O D E C O D E C O D E C O D E C O D E C O D E C O D E C O D E C
Crypt : V V L W K G D G N S D V V S A X V V L W E O Q F G S D W N M G I E

As you can see the series of letters T, H, I is ciphered to the same series V, V, L, because they were situated at the same relative position according the key; notice also that E, A is ciphered to the same S, D.
The key length is at worst the spacing between these repetitions in the ciphered text, and usually it is the greatest common divisor of the spacing of (most) the repetitions (why? give it a second thought.).


Posted in , |

Win a Free Domain Name (Registered For 3 Years), 2nd Message

By decrypting the message and following the rules you reveal, or just have fun!

After decrypting the first one, you won’t find any difficulty decrypting this one.

Sans titre

Hint: Phonemic, Linear, starting from the end is a good idea sometimes.

Hint 2 : This was a widely used code (language) in the past.

(if you decode the message, don’t forget to send your answer from the “contact me” page along with your email).

Decoded by : @oh_la_love, @27_hope, @mowahed23 , Mohieddine Abd-kader, @zirconias (competition always open closed).


Winner : Mohieddine Abd-kader,

Posted in |

Win a Free Domain Name (Registered For 3 Years)

By decrypting the message and following the rules you reveal, or just have fun!

Sans titre

Hint : People used to love playing Angry Birds in ancient Rome.


Decoded by : @oh_la_love, @27_hope, @mowahed23, Mohieddine Abd-kader, @zirconias (competition always open closed).


Winner : Mohieddine Abd-kader,

Posted in |

WP7 Samsung Devices Unlocked Forever?

Update :

No they are not ;), You can use Heathcliff74's tool from XDA here to gain root access to the Registry and change whatever you want

Most of the WP7 users who unlocked their devices using the ChevronWP7 tool have applied a registry hack to prevent their devices from relocking again, something that I applied myself, but had never thought it would unlock the device forever (till now at least).

For HTC users, they can use provxml to do this, and the Samsung users have the ability to do the same with a little app that can be found here.

The hack is pretty simple actually, it just clears the URLs the phone uses to ring back Microsoft and asks if it should be unlocked or not, there URLs can be found in the Registry at this location :
   1: [HKEY_LOCAL_MACHINE\Software\Microsoft\DeviceReg]
   2: "PortalUrlProd"=""
   4: PortalUrlInt"=""
By setting these two values to null (a void string), the phone will never be able to synchronize with Microsoft servers and hence won’t relock again.

Now if you want  to relock your phone again for whatever reason, with HTC device it is just applying a provxml that will revert the process and insert the URLs back, but on Samsung devices it is not that easy.

Writing on Samsung registry (take a look at my previous post about this) is done using the CHybridClass_FCRProxy class that comes with the native Samsung DLL FCRouterProxy.dll (this DLL has access to some privileged Registry keys).

To write a value on the registry, you basically call something like this :

   1: Samsung.RegistryWrite(Samsung.RegistryKey.LocalMachine, @"Software\Microsoft\DeviceReg", "PortalUrlProd", "VALUE HERE");

Strangely, the native Samsung methods don’t allow writing values that are more than 30 characters length, which makes it impossible to write back the original URLs that point to Microsoft servers.

So if a Samsung user locks its phone after this, he will never be able to unlock it again even with a valid developer account (just happened to me).

Heathcliff74 over XDA forums has promised me that his future Registry utility for Samsung devices will have root access, so let’s hope it will come soon. Another solution would be putting a less than 30 chars url that redirects to or something I didn’t try (won’t risk yet) and that would require more work (domain certificates?…)

Posted in , , |

Beta SMS for Windows Phone 7 is here

I’ve developed Beta SMS for Windows Phone 7 back in January, but due to delays and problems with the GeoTrust registration process to publish apps on the Marketplace, the app has been published only yesterday on the WP7 Marketplace, available for $1.29.

Beta SMS allows you to send cheap or free SMS from your favorite BetaMax and VoIP provider directly from your windows Phone 7 device. It supports more than a dozen of SMS services like 'WebCallDirect' and 'Voip Discount' and still counting.

In order to use Beta SMS, you need to have an account in one of these services:


In case your favorite provider is not listed here, please contact me (the contact information are available on the Marketplace with the app description) and I’ll make sure to include them in the coming updates.

You can download Beta SMS from here :

Downlaod Beta SMS

More info on

Posted in , , |

#WP7 Hacks, Reading / Writing the registry on Samsung Devices

The folks over xda are doing a great job with all the new Windows Phone 7 hacks, but it seems that the HTC devices are the ones getting all the fun there.

For instance, the member xboxmod have found a way to install provxml on WP7, and hence total access to the registry, which allowed them to change the WP7 themes with custom colors, disable relocking the phone once unlocked with ChevronWP7 and a lot of other stuff.

On the other hand, a lot of the member have been asking if there is a way to do so on Samsung devices (Omnia 7 and the Focus). While we have access for read/write on the registry for Samsung devices, it is so limited compares to the provxml method on HTC devices.

I developed a simple app showing how to write the registry using the Samsung native DLLs, so hopefully some guys will pick this up till we come up with a full functioning method to manage the registry on Samsung Devices.

This is the link to the application (the XAP file with the source code), you find in the same thread a homebrew registry viewer too which allows the traversal of registry keys.

Sans titre

Happy hacking!

Posted in |

Huffman Compression / Decompression in OCaml

I worked lately on a simple application in OCaml that compresses files using the Huffman compression algorithms. The application is a showcase of how to use the Huffman’s Static compression, decompression algorithms compared to the dynamic (adaptive) algorithms (Vitter algorithm is used in the application).

The source code is available on github here Although the code is not as elegant as it should be, we have used excessively the imperative features of OCaml for optimization reasons, especially for the adaptive algorithm where the tree changes with every introduction of a new symbol to code. So it is not really the best place for OCaml beginners who should be baptized with the functional beauty of the language before they see its evil imperative side :).

Although, It might be a great place too to see how the imperative and functional programming could be done on the same land, I don’t promise anything though, since we did the project in the hurry with just few days in our hands to prepare for exams and … you know the rest of the story.

So the project uses only the primitive OCaml modules, there is no libraries to install or anything, there is also an associated Makefile to compile and test the executable.

The Makefile has a make test directive to test the executable on a file named ”input” in the working directory (that you should include yourself obviously), basically it stars a static compression followed by a decompression then compares the original and the decompressed files to ensure the program works correctly. It does the same with the dynamic method too.

On a side note, we were surprised that while compiling the code with ocamlopt, we get sometimes programs that run 15x times faster than the same program compiled with ocamlc.

For a file about 5.8 MB we got some executing time around

   1: ***@****-Studio-1558:~/workspace/huffman$ make test
   3: Testing... static huffman
   4: Compress:
   5: 1.18 user 
   6: 0.00 system
   7: 0:01.19 elapsed 
   8: 99% CPU (0avgtext+0avgdata 5504maxresident)
  10: Uncompress
  11: 2.26 user 
  12: 0.00 system 
  13: 0:02.27 elapsed 
  14: 99% CPU 
  15: <<<<<<<<<<<<<<<<Compressed = Uncompress ??>>>>>>>>>>>>>>>>
  17: Testing... dynamic huffman
  18: Compress
  19: 8.11 user 
  20: 0.01 system 
  21: 0:08.13 elapsed 
  22: 99%CPU 
  24: Uncompress
  25: 4.04 user 
  26: 0.00 system 
  27: 0:04.05 elapsed 
  28: 99%CPU 
  29: <<<<<<<<<<<<<<<Compressed = Uncompress ??>>>>>>>>>>>>>>>>>

As you can notice, the static version of the program is faster than the dynamic one, this is due to the fact that we optimized the the static version to use actual bits on compression / decompression, but we used lists to represent the bits (0’s and 1’s as actual 32 bit integers!!), so that was expected.

Link for the source code :

Posted in , , |

Swedish Greys - a WordPress theme from Nordic Themepark. Converted by