# Starting MD5 hash like Pi

I found a problem on here that ask to find an MD5 hash whose hexdigits starts like decimal digits of Pi. Is there a faster program or method to solve this than my program? This uses brute force search. The site says that a has with 12 first digits like Pi exists but I was unable to find 10 correct digits from the beginning. How can one optimize this program?

# -*- coding: utf-8 -*-
import calendar
import time
import hashlib

def next_string(s):
strip_zs = s.rstrip('z')
if strip_zs:
return strip_zs[:-1] + chr(ord(strip_zs[-1]) + 1) + 'a' * (len(s) - len(strip_zs))
else:
return 'a' * (len(s) + 1)

starttime = calendar.timegm(time.gmtime())
fo = open("testfile.txt", "r+")
print("Putkaposti Piinkova salasana thus 39b.")
print("Find a MD5-hash whose hexrepresentation starts like the decimal representation of pi.")
print("Let us continue from the string "+a+".")
print("Ctrl+C quits the program and saves the results to the file result.txt.")
try:
while True:
# Let us save the results every half an hour.
now = calendar.timegm(time.gmtime())
if now - starttime > 30*60:
f = open("testfile.txt","w")
f.write(a)
f.close()
starttime = now

if str(hashlib.md5(a.encode('utf-8')).hexdigest())[0:10] == "3141592653":
f = open("result.txt","w")
f.write(a)
f.close()
print("Found! Print result to the screen and to the file result.txt.")
print(a)
a = next_string(a)
except KeyboardInterrupt:
f = open("testfile.txt","w")
f.write(a)
f.close()


When speeding up code, you need to measure the performance of the code on a standard test case, and then try many experiments focussing on the hot spots (the bits of code that are executed most often and take the majority of the time).

So the first thing to do is to refactor the code so that it is easily measurable.

def test1(key='a', target='3141592653'):
"""Return a string whose MD5 hexdigest starts with target. The search
starts at the string key.

"""
target_len = len(target)
starttime = calendar.timegm(time.gmtime())
while True:
now = calendar.timegm(time.gmtime())
if now - starttime > 30*60:
starttime = now
if str(hashlib.md5(key.encode('utf-8')).hexdigest())[0:target_len] == target:
return key
strip_zs = key.rstrip('z')
if strip_zs:
key = strip_zs[:-1] + chr(ord(strip_zs[-1]) + 1) + 'a' * (len(key) - len(strip_zs))
else:
key = 'a' * (len(key) + 1)


I've stripped the file-reading and writing code, and the exception handling, because it's not important for testing performance, and I've inlined the code for next_string so that we can improve that along with the rest of the code.

The refactored code is designed to be easy to measure — you can pass different values for target to get different levels of difficulty. Here's my chosen test case:

>>> from timeit import timeit
>>> timeit(lambda:test1(target='000000'), number=1)
10.682760871015489


The first thing we can try is to skip the code for periodic saving — if the KeyboardInterrupt handling is reliable, then there's no need for a second mechanism to save your progress.

def test2(key='a', target='3141592653'):
"""Return a string whose MD5 hexdigest starts with target. The search
starts at the string key.

"""
target_len = len(target)
while True:
if str(hashlib.md5(key.encode('utf-8')).hexdigest())[0:target_len] == target:
return key
strip_zs = key.rstrip('z')
if strip_zs:
key = strip_zs[:-1] + chr(ord(strip_zs[-1]) + 1) + 'a' * (len(key) - len(strip_zs))
else:
key = 'a' * (len(key) + 1)


This is about twice as fast as test1:

>>> timeit(lambda:test2(target='000000'), number=1)
5.272445386042818


This means that about half the time in test1 was being spent in calendar.timegm and time.gmtime!

The next thing to try is to avoid the encoding and decoding steps. The only characters you use are lower-case "a" to "z", and these all encode to UTF-8 as single bytes. So we could maintain a bytearray instead of a string.

def test3(key='a', target='3141592653'):
"""Return a string whose MD5 hexdigest starts with target. The search
starts at the string key.

"""
key = bytearray(key.encode('ascii'))
key_indexes = range(len(key) - 1, -1, -1)
md5 = hashlib.md5
a, z = b'az'
while True:
if md5(key).hexdigest().startswith(target):
return key.decode('ascii')
for i in key_indexes:
key[i] += 1
if key[i] > z:
key[i] = a
if i == 0:
key.append(a)
key_indexes = range(len(key) - 1, -1, -1)
else:
break


Note that I've also cached hashlib.md5 in a local variable to avoid having to look it up on each iteration.

This is about three times as fast as test1:

>>> timeit(lambda:test3(target='000000'), number=1)
3.3292323709465563


Instead of calling the hexdigest method, we could call digest instead:

import binascii

def test4(key='a', target='3141592653'):
"""Return a string whose MD5 hexdigest starts with target. The search
starts at the string key.

"""
key = bytearray(key.encode('ascii'))
key_indexes = range(len(key) - 1, -1, -1)
target_digest = binascii.unhexlify(target)
md5 = hashlib.md5
a, z = b'az'
while True:
if md5(key).digest().startswith(target_digest):
return key.decode('ascii')
for i in key_indexes:
key[i] += 1
if key[i] > z:
key[i] = a
if i == 0:
key.append(a)
key_indexes = range(len(key) - 1, -1, -1)
else:
break


(Note that this imposes the limitation that the target has an even number of hexadecimal digits.)

This gives a small further improvement:

>>> timeit(lambda:test4(target='000000'), number=1)
3.105254566995427


That's the limit of piecewise improvements that I can spot, so it doesn't look as though this approach is going to get you anywhere near to 12 digits. We expect the time taken to grow by about 16 times for each additional hexadecimal digit, so the expected runtime of test4(target='314159265358') would be well over a year.