Profiling in Python

16 Sep 2012 - 1 minute read

I was trying to implement the Miller-Rabin algorithm for one of my home-works, in Python. I had already done this in C++ to solve PON, but I wanted to try out Python, and see how fast I can get it to. I wrote a function to do $a\^b$ mod $n $ which used repeated squaring to get the result. However, the implementation wasn’t fast enough. Dhruv suggested that I profile the code.

Here is how you profile a python script: python -m cProfile script.py

And this is what I came to know

172 function calls (66 primitive calls) in 31.492 seconds
    
       Ordered by: standard name
    
       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
            1    0.000    0.000    0.000    0.000 __future__.py:48(<module>)
            1    0.000    0.000    0.000    0.000 __future__.py:74(_Feature)
            7    0.000    0.000    0.000    0.000 __future__.py:75(__init__)
            1    0.020    0.020    0.020    0.020 hashlib.py:55(<module>)
            6    0.000    0.000    0.000    0.000 hashlib.py:94(__get_openssl_constructor)
            1    0.063    0.063   31.492   31.492 millerRabin.py:1(<module>)
        108/2   16.644    0.154   16.644    8.322 millerRabin.py:12(fastModularExp)
            2    0.008    0.004   16.672    8.336 millerRabin.py:21(millerRabin)
            1    0.000    0.000    0.000    0.000 os.py:743(urandom)

Note how the fastModularExp() function took a staggering 16 seconds. Now we came to know that the builtin pow function in Python already does fast modular exponentiation. And since it is a part of a C library, it is quite fast. After doing this, I submitted it as a solution for PON and got accepted with 0.35 seconds, which was faster than my 0.90 submission with C++ :-)

On Doing Well In Coding Interviews

16 Sep 2012 - less than 1 minute read

Though I am no expert myself, but having gone through a couple of coding interviews, people ask me suggestions on how to prepare for such interviews. Here is a course that was taught at MIT, on how to do well in Google (and, other companies’) coding interviews. This is good at giving you feelers about the level of the questions in such interviews.

A cool way to look at Symmetric Key Cryptography

15 Sep 2012 - less than 1 minute read

“Why encrypting twice with two symmetric keys using the same algorithm doesn’t give you twice the security?” was the question that was asked in a recent CSE509 (System Security) class. I had the intuition that encrypting with the same algorithm twice with two different keys, K1 and K2, is essentially equivalent to encrypting with one key (say, K3). However, I didn’t know how to convince others about this.

Someone pointed out that, since Symmetric Cryptography is essentially a combination of Permutation and Substitution at a very basic level (the person was referring to P-Boxes and S-Boxes, found in many algorithms), doing it twice is essentially equivalent to doing it once with some other key.

I found that this was a more convincing argument (though very informal), about the security of the proposed mechanism.

Newer Older