Abstract Algebra presented in a non-intimidating way (esp. for developers) part 2

Hi!

If you haven't read the last one, I encourage you to do so, since I'll be using a lot of the terminology from the last post in this one, and I will be building on those topics.

This post is largely background info for the next post, which will be on cryptography, but, for you to understand the next post, it is essential that you understand this one quite thoroughly.

Lets begin with some history. Pure mathematicians when group theory was invented didn't really care what the physicists thought of them and how well they fared at parties, so, they developed all this theory about groups and none of them really cared about how it would apply to "real life".

Then of course, there were these pure mathematician misfits, who were also physicists, and they realized that group theory could actually be pretty useful, and there was this stream of physicists and chemists trying to get in on the abstract algebra action.

Up until then, most of the groups that were being studied were infinite (like $Z$ on addition), or something very specific that the physicists and chemists did not care about, and then mathematicians
Before we get into the group theory today, I want to introduce you to something I call "clock arithmetic".

Clock arithmetic is just like regular arithmetic, but, its carried out on a clock. I'll explain that with an example.

Let's try to find out what 12+6 would be, on a clock with the twelve numbers on it (not the weird Italian ones with 24 numbers on them, they don't deserve to be called clocks). Okay, so, thinking about this, we can see that this would not be 18, because 18 isn't on the twelve hour clock, and, what happens is, if we start at 12 and then rotate an additional 6 hours, we end up on the 6 mark.

Let's do another example. Let's try to find 6+9. Again, this is a similar case, where we set the hand to 6, it rotates around to 12 after 6 hours, and then, we still have 3 hours left to rotate a total of 9 hours, so, we end up at 3. 


Okay, that's not too bad.

As exercises, try finding out:

• 1+19 = ?
• 2+26 = ?

If we're doing $1+19$ on a twelve hour clock, we usually write it as:

$1+19 \equiv 8 (\mod{12})$

I can hear you saying, "What? Why does that equal sign have another line? This is heresy!"

That extra line is telling us that $1+19$ isn't necessarily equal to $8$, but, it is under this funny clock arithmetic with this twelve hour clock we've developed.

If you did those two exercises, you might have noticed something. The observation should have been that if you add 1 and 19 using the "regular" arithmetic, and then take the remainder by 12, you still get the same answer! 

Now, with a little bit of thought and some intuition, you can see why that's true (I encourage you to try this; hint, try starting at an arbitrary hour, like 1, and then seeing what happens in reference to this point). 

I won't bore you with the formal proof (it doesn't use any clever arguments), but, I would really like it if you would try to get some intuition about why the above is true.

Okay, now, not all clocks are 12 hours long, right? How about some clocks that are, eh, three hours long? It's still the same idea!

Say, we're doing $12+20$. We first find out its $32$, and then take $\mod 3$ (remainder by 3), to get $2$. 

Read the last sentence again. See how I used $mod$ to mean remainder? Okay, good. 

Because clock arithmetic are pretty much remainders, and mathematicians like using large words, this clock arithmetic is called modular arithmetic. 

You might have also noticed that we can take the remainder of the two numbers were adding up separately, and then add up those two remainders to get our answer. Let's try proving that in general (note: what matters isn't really the proof, but, how the reasoning goes in the proof, follow it closely). Stated "mathematically", this comes out to be:

If $a \equiv b (\mod {n})$ and $c \equiv d(\mod{n})$, then, $a + c \equiv b + d (\mod{n})$

Let's try to think of this in terms of remainders. Since $a$ has a remainder $b$ when divided by $n$, we get that $a$ can be written as $kn + b$, for an some integer $k$.

Then,

$a-b = (kn+b)-b = kn$

Therefore (since $a-b$ has to be divisible by $n$),

$a-b \equiv 0 (\mod{n})$

Similarly, we can argue that

$c-d \equiv 0 (\mod{n})$

Now, think about it this way, if we add two numbers that are divisible by a certain number $n$, you will always get a number that is divisible by $n$. A quick proof:

$p = k_1n, q=k_2n$
$p+q = n(k_1+k_2)$

So, we can add the two congruences we got, so that we have:

$(a-b) + (c-d) \equiv (a+c)-(b+d) \equiv 0 (\mod n)$

Again, we have to use a bit of thinking here. If you have a number $m$, and $m-k$ is divisible by $n$, then, that means that $m$ has a remainder $k$ when divided by $n$ (from the definition of a remainder).

So, we can use that to say:

$a+c \equiv b+d \mod(n)$

Nice!

You probably did not understand ALL of the proof, and if that was the case, please read it again. The approach that we're using, using algebra and divisibility at the same time is very important, and will probably show up again.

Alright, so, how has any of this got anything to do with abstract algebra and groups and stuff?

Well, let me introduce you to this concept of a cyclic group.

A cyclic group is a group in which all of the elements of the group can be generated by one element of the group on which the operation of the group is applied over and over.

What the heck does that mean?

This is best illustrated with an example.

Let's say we have a group, with the operation $+$. You know, like normal addition.
We start out with the element $1$, and add $1$ do it, and get $2$.

Then, we add $1$ to $2$ again. To get $3$. And so, so forth, until we've generated all the integers (we can also apply the inverse operation, which would be to subtract), so, we can say the the set of integers ($Z$) is cyclic under the operation of addition.

Then, there are cyclic subgroups.
Cyclic subgroups are groups whose elements are a subset of those of a cyclic group. Cyclic subgroups are (usually) finite.

Here's where you need to pay attention.

A cyclic group can be something like:

${1,2,3,4,5,6,7,8,9,10,11,12}$ on the addition operation.

Hey ... that's like a clock! So, cyclic groups can model modular arithmetic!


So, all the stuff we established in the last post is automatically applicable to this one :)
We can now prove some stuff about modular arithmetic using groups!

We can even prove that multiplication (i.e. repetitive addition) forms a cyclic group ($G$) under modular arithmetic with a $\mod p$ where $p$ is prime. This is so because:

• Closure: any two elements that we take in this set and multiply them together cannot give a result which $0$ and therefore not in the set.
• Associative: Its multiplication; not much work here.
• We have an identity, and its 1
• All of them have an inverse so that they have a remainder of 1 $\mod {p}$

This allows us to say:

$m^{p-1} \equiv 1 (\mod {p})$, for all $m \epsilon G$

Why? Because if you think about, the multiplication sort of "wraps around" the set, because all of the results of the multiplication are a part of the set of the group $G$ (if you are confused about this, drop a comment below and I'll definitely help, this confused me for a really long time).

So, let me pose a problem:

Find the $7^{37} \mod {13}$. Don't reach for that calculator. And, no, you can't use Python.

That looks really hard!

But, we can simplify that a bit. From what we know from above, we can say ($13$ is a prime):

$7^{12} \equiv 1 (\mod {13})$


Okay, that helps us, because we can write $7^37$ as:

$7^{37} \equiv (7^{36})\cdot(7) \equiv (7^{12})^3\cdot(7) \equiv 1\cdot7 \equiv 7 \mod{13}$

Nice!

On top of that, all cyclic groups are abelian/commutative (try proving this; its a good exercise), which opens up an entire new set of possibilites.

But, why does any of this matter? But does this "modular arithmetic" idea matter aside from solving problems like the one above, which you would have probably plugged into a computer?

Let me tell you, cyclic groups are not-so-abstract-algebra. They have a TON of applications.

Well, if you've ever written a website (or, even used one), or logged into SSH, or logged into a computer, it definitely does matter.

There's this "little subject" called cryptography, which deals with storing information in different forms, and it uses modular arithmetic intensively.

And, if you are a physics type person, Lie groups and such are quite similar to cyclic/symmetric groups.

If you liked the $7^37$ problem, and would like to continue in this direction, I highly recommend you check out this free set of problems (not by me). They are much more advanced than these, but, if you get some background on number theory, they should be fun.

I promise the next one will be much cooler in terms of CS related stuff, but, I had to provide some background on cyclic groups, otherwise the next one wouldn't have made any sense.

Also, I've started a project called NimbleNotes here, and I really am trying to get it off the ground, so pledges and tweets are highly appreciated :) This blog entry was written with NimbleNotes, with a MathJax plugin I wrote.

Small update to followers

Yeah ... I messed up.

Once  I wrote the Abstract Algebra post, and got a bunch of feedback on it, I immediately set out on writing another one, and the reason that went all wrong was that I decided I would introduce Automata theory, and I wrote two posts on it, then, I realized that Automata theory is pretty abstract, and would be hard to understand without a thorough knowledge of groups and rings, so, I'll be postponing that.

I'm currently writing the next post; should be up by tomorrow. Thanks :)

Abstract Algebra presented in a non-intimidating way (esp. for developers)

Hi.

I think math is really cool, but, most people (sadly) don't think so. This includes many programmers who in fact enjoy many of the same things that mathematicians do, but, are more practical for most of the time.

I'll show you why abstract algebra (in particular, group theory) is really cool, and why you don't have to be a freaking genius to get it.

Firstly, in order to understand most of this, you'll need to understand a tiny bit of Set theory, and to save time, I'll just refer you to wikipedia for that one (you just need to understand basic unions and intersections).

Let's begin with a simple definition, of a group (note: for hardcore types, this isn't fully rigorous because I haven't defined what an operation is, but, you get the idea).

A group is defined:

1)

A set (usually called $S$) with an operation attached (we call the operation $*$), so, if $G$ is a group,
$G = <S, *>$

2) Closure is one property that all groups must have in order for them to be a group. Closure means:

If $G = <S, *>$ and $x \epsilon S$ and $y \epsilon S$, then $x*y \epsilon S$

Note: $*$ does NOT NECESSARILY MEAN MULTIPLICATION!

3)

All groups have an identity element $e$, such that ( we are still considering the group $G$ with operation $*$):

For all $x \epsilon S$, $x*e = x$

4)

All elements in a group have an inverse,

If $a \epsilon S$, $a^{-1} \epsilon S$ such that:

$a * a^{-1} = e$

5)

The operation $*$ is associative. That means:

$(a*b)*c = a*(b*c)$

Alright, why in the world would anyone in their right mind define something like that?!

Let's take a step back, and understand where this comes from.

Around the 19th century or so, people realized that elementary algebra wasn't the only type of algebra that existed. There were all kinds of other algebras, like matrix algebra, and vector algebra and boolean algebra, and all these new all these new kinds of algebras kept cropping up with all these new rules (like, matrix multplication isn't commutative, that means: $A*B$ is not necessarily equal to $B*A$ when $B$ and $A$ are matrices) because mathematicians now had to solve all kinds of new problems.

And, the problem was, mathematics was losing its "connectivity", all these new algebras had little to no connection to each other, and it was very difficult to make progress in a few of these algebras at once.

Then, there was a clever idea. All of these algebras still were only doing a few operations on a set (or crossproducts of sets) and then were equating those operations on sets. That's how abstract algebra came along. Mathematicians realized that they could define "algebraic structures" (i.e. define algebraic systems so they followed a few axioms), and prove things about those algebraic structures, and any algebra that was then invented that could be proven to fit that algebraic structure would automatically have all the properties that people had proved about those structures!

Basically, if you came up with a new algebra, called "Cheese Algebra" and it has all these funny rules, but, it handles only one operation and you can prove that Cheese Algebra has all the properties of a Group, you're done! That means that all the things people have proven for Groups are automatically true for Cheese Algebra!

Isn't that awesome?

Let's try it.

The definition of a group is pretty simple, but, there are a few catches. First and foremost, the $*$ operation is not multiplication. Read the sentence over again. And again.

Secondly, in a group $a*b$ is not necessarily equal to $b*a$. Groups in which this is true are called Abelian groups and they make your life much easier, but, not all groups are like that.

Then, there are some basic theorems about groups that can be proven, and these are some important ones:

• A group has a single, unique identity element
• Every element of a group has a single, unique inverse
• $(a_1*a_2*a_3* ... * a_n)^ {-1} = (a_n^{-1} * a_{n-1}^{-1} * a_{n-2}^{-1} * ... * a_1^{-1})$
• $(a^{-1})^{-1} = a$

Let's prove a couple of them.

The first one is pretty easy, we assume there are two identities, $e_1$ and $e_2$ for a group $G = <S, *>$ and this would mean,

$e_1*e_2 = e_1$ (consider $e_2$ as the identity element)
$e_1*e_2 = e_2$ (consider $e_1$ as the identity element)

Which means $e_1=e_2$, which is a contradiction.

The second one is really similar, so, I won't go into the details.

The third one is a bit different, you first prove $(a*b)^-1 = b^{-1} * a^{-1}$ and then use the associative property of groups.

Okay, so, what does this mean?

Well, each of these properties hold for every algebraic system that's a group!

So, for example, matrices (the ones that do have inverses) form a group under the operation of multiplication, so, we've figured out a bunch of cool properties about matrices, like

The inverse of the inverse of a matrix is the matrix itself.

And, we haven't dealt with a single $a_ij$ component (although we would in proving that "inverseable" matrices do indeed form a group under multiplication)!

Also, the real numbers (excluding zero) form a group under multiplication, so, we can say this, too,

The reciprocal of the recipocral of a real number is the real number itself.

And, vectors form a group under addition (this one's really easy to prove, I suggest you try with the axioms given, hint: the identity is the vector <0,0,0>), too:

If you negate the negative of a vector, you get the vector itself.

Notice that the inverse operations change with each of them, but, the idea is still the same, so, with the single idea of a group, we've solved problems in a bunch of different areas of mathematics.

Let's try something a bit more complex, let's solve an equation on a group. What does that mean? Well, we can't use our knowledge of existing algebra, we can only use the axioms about groups, and the things we proved from them in order to solve the equation.

Now, I'll show you the equation, but, try solving it first if you can before looking at the solution, it'll give you a different kind of appreciation for the solution.

Solve the equation $a*x*b = c$ for $x$ in terms of $a, b, c$, which are constants.




Solution
=======
Multiply both sides by $b^{-1}$,

$a*x*b*b^{-1} = c*b^{-1}$

Since $b*b^{-1} = e$,

$a*x*e = c*b^{-1}$

Since, $a*x*e = (a*x)*e = a*x$,

$a*x = c*b^{-1}$

Now, since each element of the group has a unique inverse, we can take the inverse of both sides of the equation, and the equation will still hold true:

$(a*x)^-1 = (c*b^{-1})^{-1}$

Which is the same as:

$x^{-1}*a^{-1} = b*c^{-1}$

Multiply both sides by $a$,

$x^{-1} = b*c^{-1}*a$

Take the inverse of both sides again, and notcie $(a^{-1})^{-1}$,

$x = a^{-1}*c*b^{-1}$

Yay!

Now, what's (again) really cool, is that this works for every, single freaking algebraic system that you can think of that's a group. Matrices with multiplication? Done. Real numbers with multiplication (aside from 0)? Done. Vectors with addition? Done.

Abstract algebra doesn't stop there, it defines all these structures that have similar properties like Rings and Fields that you can use to prove things in a bunch of different algebras in one fell swoop.

I hope you liked this article, and I'd love your feedback, email me at dhaivatpandya at g mail dot com, or comment below :)

EDIT: I forgot to mention some applications to CS.

Alright, you guys know how Haskell?

Haskell (and any ML-type language, really) uses something known as Algebraic data types, which basically let you specify datatypes that follow certain axioms, in a way.

Even though it is completely your responsibility to make sure that these structures form some kind of helpful algebra, the relation is still there.

And, about classes in OOP languages, there's a very close correlation.

You can very nearly think of classes as a algebraic structure that have many operations (methods) and elements (fields, variables, etc.), but, this isn't a perfect correlation because of many things that OOP languages let you do that are functionally "impure", and mathematics is a completely pure functional language (which is why it maps to Haskell so nicely), there is no state.

Node.js is pretty awesome

This'll be a small post, so, yeah.

I first started event-based loops with Twisted (http://twistedmatrix.com/trac/), and I had absolutely NO idea what I was doing.

I was doing all kinds of nonsensical things (I still have my code), like trying to read user input from stdin with raw_input() in a callback function. I slowly got better, and gradually learned more about what types of functions blocked, etc. etc. But, that took a while. And, if I needed to write production-ready code straight off the bat, I wouldn't have been able to do it (i.e. I would have written the code, it just would really, really suck).

Then, I tried out eventmachine and libeio, and they were all pretty similar, and I still had to be pretty careful about what type of code I was writing (one has to think less and less about this type of stuff the more you do it), and it wasn't really flowing.

Then, I found out about node.js.

Unlike a lot of people, I wasn't drooling over it or anything, mostly because it uses Javascript, and I didn't really think that moving Javascript over to the server side would help any. This conclusion was mostly rooted from the fact that I always troubled myself with writing cross-browser JS, and that's a painful task. But, with node, that disappears. There's only V8, to hell with all the other parsers and compilers that developers have come up with.

Javascript, if written for only one interpreter/compiler, is pretty usuable, and actually pretty fun. The prototype object system stops getting in the way, because you're provided with Object.create() which IE ... let's not talk about IE :)

The point with node is, its really, really hard to write completely blocking code, because javascript doesn't have anything like File IO that blocks with which you can shoot yourself in the foot!

The things I could write in a short amount of time literally skyrocketed, because I didn't have to worry so much about putting the wrong call in the wrong place, and could just concentrate on getting the application logic down.

There are, however, a few cinches that you have to deal with. Firstly, there's no tail call optimization in v8, even though it has been requested (http://code.google.com/p/v8/issues/detail?id=457). This is mostly because of some stupid things done in the spec, but, Node would be a lot better for me if this request was fulfilled. Secondly, if you are a server-side developer, getting used to JS will be pretty ... different, that's not really bad, but, it might slow you down.

So, all in all, I highly recommend you check out Node.js, and try writing something simple (like a chatroom or something).

Feedback welcome.

PHP sucks (but, some frameworks don't)

I started web development with PHP, and I've decided I've had enough. Why? Keep reading.


PHP (the language) sucks. There, I said it. 

• 1029380128301928301823 Globals
• Object system hacked on
• C extension system sucks
• Documentation sucks (read more; no, I'm not drunk)
• Has a terrible community
• All in all, designed by total idiots. 

You've probably heard this a ton of times before, but, here it is again. THERE ARE JUST WAY TOO MANY GLOBALS. Why in the world does md5() need to be global? Do you seriously use md5() in every single file?


This is also a common occurrence, why on the planet are things like the order of  haystack and needle the same everywhere? Is it really that hard to do?

All in all, the language lacks continuity; it lacks grace. It doesn't have any precise definitions for anything, there are always exceptions (a bit like the English language), unlike something like Python, which tries its best to be properly defined and easy to relay to someone. In my eyes, if a language has a simple grammar, but, it is still powerful enough for use, I consider it excellent (Lisp/Clojure comes to mind).

The Object System. Everyone's probably saying, "Hey! Its just like Java, what's wrong with it?!". Firstly, Java isn't the all-glorious object system everyone wants. Secondly, atleast most libraries and APIs in Java are based around objects and classes, whereas for PHP, its just a few bajillion globals, with classes if anyone wants to use them (which new programmers conveniently ignore because they can, and it leads to projects with a few hundred functions, and no classes and everything held together with <?require's and <?include's and global mutable state).

Another horrific massacre is the C extension system for PHP. If you haven't tried (I have), don't do it, you'll regret it in your later years when macros will show up as nightmares. It shows you that the interpreter is this humongous blob of macros, held together by large if-else statements and switch'es, and it also tells you that you have to deal with this if you want to get any work done with the so-called "API". And, there's all this stuff that's dependent on Zend, and if they change their mind about something in the API, it all comes crashing down on you. Almost NOTHING is optimized. The things that have been optimized turn out to be this convoluted mess of unnecessary variables and unused heap space.

Documentation. Everyone seems to be telling me that the documentation for PHP is absolutely wonderful. When I type in "php mysql" into google, I get http://php.net/manual/en/book.mysql.php. Which would be all fine and dandy if I was a new web developer that just needed to get my darn code to connect to mysql, but, dig deeper and you'll find out that this actually references the dangerous "mysql_" set of functions, which should have never been invented, and everyone should have been using PDO instead. Of course, the documentation doesn't tell me ANY of this, and just tells me how to install it, and how to go about making dangerous commands to MySQL. And, the comments on the documentation contain possibly the worst code that has ever put foot on planet earth, and newbies (especially on #php on Freenode) use them quite freely and get very confused and disappointed when their website gets hacked, or the code refuses to work when another user is running, etc.

The community is also terrible. Every time I try to tell someone that they should maybe put the cryptographic functions in their own class, they (basically) accuse me of heresy and remind me what the Spanish Inquisition did to heretics. The community loves newbies, definitely, but, the people who aren't experts with PHP end up giving really bad advice (like not using PDO because its too complicated for small projects), and the ignorance just keeps spreading.

If you look at the interpreter code, it'll be quite obvious why I say my last bullet point. The lexing code has a ton of repeated rules, crap that's never actually used in the parse tree and even more inconsistencies that are defaulted, and, whenever an elegant solution is possible the code is instead splattered with regular expressions. The parser gets even worse in this regard, with part of the lexing done in the parser.


Now, here's another statement I'm making about PHP.

(some of) PHP's frameworks and their developers are excellent.


A good example is Kohana (http://kohanaframework.org/). This framework is well thought out, expressive, and easy to use. Takes a couple of hours to learn and gives you full MVC out of the box, with database connectivity and everything. The developers really know what they're doing, and they try to make sure that Kohana is top quality code and stays well maintained. These developers have climbed the difficult hills of PHP with all its intricacies, and have come out victorious and you can see that in their code.

But, that still doesn't cut it for me.

Its a bit like trying to build the Eiffel Tower on top of a wooden log house. Yes, the eiffel tower is a great feat of engineering, but, its built on a log house, you can't expect it to be too stable. That's the case here, Kohana is AWESOME, but, its built on PHP, and I'd still be much more productive in Python or Ruby or maybe even Perl!

What's the alternative?

I highly suggest Python and Flask (http://flask.pocoo.org/) as an excellent combination for beginners, and Django for more experienced Python developers.

There are also many other options, such as Ruby on Rails (I like this too, but, the lack of documentation sort of makes it difficult for me), Node.JS, Web::Simple (for Perl, not too popular, but excellent, IMO), etc. etc.


Stay away from PHP if you're a freelancer if $10/hr seems bad


Because PHP has such a low barrier for entry, there are hordes of terrible developers that are up for hire on websites such as freelancer.com, and others. They sink to bottom prices, deliver terrible quality work, and there's thousands of them.

There's this funny story that I usually use to give an example. Before I realized I wouldn't make any money, I used to be quite active on freelancer.com, usually bidding on PHP projects. For one such project (it basically consisted of writing PHP for a AJAX app that needed to continuously poll), I bid $\$150$ (which is quite low for all the code I had to write, about $\$15$/hr), and there was another man (who had not-so-good ratings), who said he would do it for $\$40$. I warned the employer that he would not do the job properly, and you'd have to hire someone for a rewrite of the code, but, he (obviously) disregarded my arguments, and hired the $\$40$ guy. And, what happened? The $\$40$ guy procrastinated and delayed, wrote a bunch of crap code that basically checked the server every 10 seconds for this static file, which he modified with this Perl script that he set up a cronjob for, and it was overall a terrible hackjob. After 2 weeks, the employer had to hire again (he did hire me this time around).

Because of these types of scenarios, its very difficult to do well as a freelancer in PHP, IMHO.

So, I'm moving away from PHP to greener pastures, and I hopefully won't have to come back.

Encryption/Ciphers Part 3 - Knapsack Cryptosystem (a)

Encryption/Ciphers Part 3 - Knapsack Cryptosystem (a)

Hi everyone. As always, if you haven't done so, I highly recommend atleast skimming through the last two articles, as I use terminology from them in this article. And, I'll be adding more posts about the encryption series, so, if you would like to keep updated, I would suggest you follow this blog.

Also, the Knapsack Cryptosystem will be broken into two parts, one that describes the Knapsack problem and the next that shows Knapsack cryptography.

Also, I made a mistake last time (which, unfortunately, no one noticed early enough), I forgot to do a push on the github repo, so the Vigenere code was not up, well, now it is.

So, lets get started.

The Knapsack Cryptosystem was invented in the late 70's, and now has been broken, but, it still is an awesome introduction to public key cryptography, and is quite a bit more elegant than RSA, which involves a lot more complicated math.

So far, we've talked about a monoalphabetic cipher (the Caesar Cipher), and a polyalphabetic cipher, which both require one piece of information to encrypt and decrypt. Now, we will consider a new type of cryptography, known as a public key cryptosystem. The most simple (in my opinion) example of this type of system is known as the Knapsack Cryptosystem, or Backpack Cryptosystem, or Volumes Cryptosystem, you'll see why these why all these names mean the same thing in just a minute.

Firstly, what's a public key cryptosystem? Well, in such a system, there is not just one piece of information needed to encrypt and decrypt (the shift index in the Caesar Cipher or the passphrase in the Vigenere cihper), there are two things needed, one key to encrypt the plaintext, and another to decrypt the ciphertext. Usually, the two keys are called public keys and private keys. Every recipient in the system has a public key that everyone knows about (including possible attackers), but, messages encrypted with that public key can only be decrypted with the recipient's personal private key, which is kept secret from everyone.

That concept is sometimes hard to bend your mind around, and there's no better way to understand it than an example given by Wikipedia (http://en.wikipedia.org/wiki/Public-key_cryptography), so, I'll just quote it:

"An analogy to public-key encryption is that of a locked mailbox with a mail slot. The mail slot is exposed and accessible to the public; its location (the street address) is in essence the public key. Anyone knowing the street address can go to the door and drop a written message through the slot; however, only the person who possesses the key can open the mailbox and read the message."

Notice I said usually a lot for the definition of public key cryptosystems, because there are other uses known as digital signatures, which aren't the focus of this article (but, maybe later on).

So, getting more particular, what's a Knapsack cryposystem? Well, firstly, we'll look at the Knapsack problem.

Say you have Knapsack (or backpack, or bag, or whatever the heck you call it in your country) of volume $V$, and you have $n$ items of various volumes $a_1, a_2, a_3 ... a_n$, using none or multiple of each of these items, is it possible to completely fill the Knapsack?

Lets make an equation out of that:

$V = a_1x_1 + a_2x_2 + a_3x_3 ... a_nx_n$

This problem, when given $V$ and $\{a_1, a_2, ... , a_n\}$, may have none, one or many solutions. Finding a solution to an arbitrary Knapsack problem is extremely difficult, in fact, all the approaches currently available (more on this later) are not very far from just using bruteforce to try out all $2^n$ combinations. That makes it an ideal candidate to base an encryption system on.

But, due to reasons that you'll find out about, if the equation has multiple solutions, it doesn't work for public key cryptography. So, when does it have a unique solution (if any at all)?

Lets call a sequence of $a_i$ "superincreasing" when each $a_i$ is larger than the sum of all the preceding ones; that is,

$a_i > a_1 + a_2 + a_3 + ... a_{i-1}$

If the $a_i$ are superincreasing, the Knapsack problem has a unique solution (again, if any). Let's look at an example to see why this is true:

Say we have the equation

$11 = 2x_1 + 3x_2+6x_3+13x_4$

Since $13>11$, $x_4 = 0$. So,

$11 = 2x_1 + 3x_2 + 6x_3$

$2+3<6$, so, we must include atleast one item of volume $6$, so $x_3 = 1$.

$5 = 2x_1 + 3x_2$

Again, we operate the same way, noting $2<3$, and then getting $x_1 = 1, x_2 = 1$.

And, we've solved it! A proof of why all Knapsack problems containing $a_i$ that are superincreasing is not difficult to formulate, and I encourage you to try it yourself (consider it an excercise, if you'd like). Also, the Knapsack problem is an excellent introduction to dynamic programming (that's how I learned DP), and, if you care about such things, I would check this out: http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

I'll be posting the next part of the Knapsack cryposystem blog in a day or two. I split it into two parts because the Knapsack problem and the cryptosystem both together are at on of material to have to digest so quickly.

As always, feedback extremely welcome, and thanks for the upvotes, Redditors. If you would like to keep updated with this series, I highly encourage you to follow this blog.

Encryption and Ciphers - Part 2

Welcome back (or just "welcome" to the people that didn't read the last entry, if you are one of those, I highly encourage you to atleast skim it since I use a lot of that terminology here). 

So, last time, we discussed the Caesar Cipher  and why it is so easy to be cracked. So, if it is easy exploitable, what's the alternative, well, the next step up would be a polyalphabetic cipher. 

One such famous cipher is called the Vigenere Cipher. To use it, both parties must agree on a passphrase, such as "EYE". Let the converted-to-numbers passphrase be represented by the set $M$. To get the ciphertext (say the plaintext is "ATTACK") , we repeated the set $M$ inside set $N$ until the length of $N$ is the same as the length of the plaintext set $P$, and then:

$P_i + N_i \equiv S_i (\mod{26})$

Lets do an example. With the plaintext "ATTACK", and the keyphrase "EYE", we write down the following:

$P = \{1, 20, 20,1, 3, 11\}$

$N = \{3,25, 3, 3,25, 3\}$

Now, to get the ciphertext in integers ,$S$, we just add them up, modulo 26:

$S = \{4,19, 23,4, 2, 14\}$

Which translates to: "DSWDBN"

Now, why is this better? In the plaintext, we have two T's, but, in the ciphertext, there are no letters that are repeated twice. This means that this cipher does not preserve frequency. Why is that important? That means that one cannot use frequency histograms anymore, because the ciphertext no longer has the same frequencies of letters as the plaintext! 

So, that means that the Vigenere Cipher is more resilient to statistical methods of attack than the Caesar Cipher, but, what about the dictionary/brute-force attack we covered last time? Well, lets see. 

For the Caesar Cipher, we only have to cover 26 shifts, whereas for the Vignere cipher, things are much more complicated. We must consider every possible passphrase, so, if we are given the ciphertext, 

and it is 12 characters long, for example, we must test for all passphrases that are 1 character long, 2 characters long and so on until 12 characters long. So, if we have a ciphertext and it is length is $n$ characters, we see that the number of tries we must do is:

$26^1 + 26^2 + 26^3 + ... + 26^n = \sum_{i=1}^{n}26^i$

Since that's a geometric series,

$\frac{26(1-26^n)}{(1-26)}$

That's a lot, even for a computer. If implement a cracking algorithm, it'll run in exponential time, which is really bad.

But, what happens if you can guess how large the length of the passphrase is (just imagine, for a moment)? That becomes only $26^n$ tries, and it would turn into a sort of modified Caesar Cipher. That's not too bad, right? 

Well, but, how would we guess the length of the passphrase? A clever chap named Friedrich Kasiski figured this one out for us. Its not always effective, but, when it is, it reduces computation time greatly. Basically, repeated words in the plaintext may by chance have the same letters in the passphrase they were encrypted by. Where this is true, frequency is preserved, and we can see how long the passphrase is. Of course, this would only work if there were any repeated words at all, and also if the repeated words coincided exactly with the passphrase used. So, it obviously isn't precise, but, if it does work, it works brilliantly.  

In the next post, we'll take a big jump, and take a look at the Knapsack Cryptosystem. 

As always, feedback is greatly welcomed, whether negative or positive doesn't matter. 

Also, if you guys have any other ideas for articles you would like me to do, please comment below. 

I  haven't updated the github repo (https://github.com/Poincare/cryptoBlog) as of now, so, if someone could do that, that would be awesome (I'll probably do it before the end of today, my git needs reinstalling). 

Encryption and Ciphers - Part 1

This is starting a three or four part series on encryption and ciphers, going from simple ciphers such as the Caesar Cipher to industry strength encryption methods like RSA (maybe even Blowfish if I cover that much stuff). This assumes that you're familiar with atleast a little bit of modular arithmetic (http://en.wikipedia.org/wiki/Modular_arithmetic).

So, lets get started.

Firstly, what is encryption? Let's get a definition down. Encryption is taking "plaintext" (text everyone concerned can read and understand, including people that you would rather wouldn't read your message) and converting it to "ciphertext", which only you and the parties that understand how to go from ciphertext to plaintext (a.k.a the recipient) should understand.

That sounds pretty good, right? 

Now, for some basic knowledge I'll be using throughout the article, so, pay attention. When I say string, I mean a string of characters (which should be self-explanatory for the developers here). When I say convert a string to numbers/integers, I mean that we map "a" to "1", "b" to "2", "c" to "3" and so on, until "z" to "26". It would be a good idea to make a table of this mapping on a piece of paper, because you'll be using it a lot if you follow along.

Despite encryption sounding like something invented in the 20th century (or maybe even more recent than that), encryption originated a long time ago. A really long time ago. Caesar (yeah, that dude from Rome you learned about in high school) needed to send secret messages to his allies that could not read even if the messenger was attacked. His men invented a system called the Caesar Cipher. Its a very simple idea, you convert the message to numbers (and call the resulting set of numbers $P$), and you decide on a shift value, $n$ (which the other party knows of as well), and you do this:

$P_i+n \equiv S_i (mod 26)  ....      (1)$

where $i$ ranges from 1 to the length of $P$ and the set $S$ gives us the numbers for our ciphertext, and, from the numbers we get the actual ciphertext. This might look complicated, but, its quite clear with a little bit of thought. Basically, this, instead of mapping from letters to numbers, we map from letters to other letters. For example, with a shift of 3, we would map "a" to "d", "b" to "e" and so on (and because of the $mod 26$ the z wraps around) all the way to "z" to "c". Similarly, the decryption algorithm would be:

$S_i-n \equiv P_i (mod 26)$ 

This we can get just by manipulating (1) a bit.

Lets do a quick example. Encrypt "attack" with a shift of three. 

Convert to numbers:

$P = \{1,20,20,1,3,11\}$

Apply shift, and mod:

$S = \{1+3,20+3,20+3,1+3,3+3,11+3\}  (mod 26)$

$S = \{4, 23, 23, 4, 6, 14\}$

Result (this is why I told you to make the table): "DWWDFN"

Okay, great, now we know how to use a Caesar Cipher. Of course, it were bulletproof, we wouldn't have people that do PhD's on encryption. The Caesar Cipher is what is known as a substitution cipher, it takes one letter and replaces it with a different one. The problem is, it doesn't change the frequency of the letters,  we can see in the "attack" example that the two T's are now represented as two W's. This is easy to "crack" (going from ciphertext to plaintext without having the shift) by statistical methods. If we have this chart: 

We can try ever shift value (only 26 of them, can't be too hard) and check if the suggested plaintext has a letter distribution matching the one above. The closest match should be the right one!

And, we can also dictionary force it. If we try all the shift values and get a suggested plaintext for each one and check how many dictionary words are formed for each of these, the plaintext with the most matched dictionary words is most likely the one we are looking for.

It may seem a bit cumbersome to go through 26 different shift indices, and it would probably take some time, but, computers can do it before you can say "Caesar was a liar". Literally.

So, how would we solve this problem? 

That's the topic for the next one :)

Code for this article is located here: https://github.com/Poincare/cryptoBlog

Only in Python right now, but, I should have a C version up soon, and I would love ports to other languages, please fork and submit a pull request and I will accept it.

Comments are highly appreciated, and I would love it if you guys gave me any feedback at all (even if it is negative). Redditors, upvotes are very welcome.

I know this one was a bit light, and did not cover a ton of material, but, I aim to remedy that with the next one (I assume starting slow would be better). 

Not having TCO pretty much kills Javascript

Javascript is a funny language to me. I have things that I really like about it, like higher order functions and being a prototype based language (more on that later). There are also things that I absolutely hate about it like the + and === operators, and how the prototype based things really only half work. The thing that really ruins my experience with the language, however, is tail call optimization.

As many of you now know, Ecmascript 4 does not support tail call optimization. For those that don't know, tail call recursion is where the interpreter takes a recursive function and turns it into one that isn't recursive, so, you aren't limited by stack size. Tail call optimization (TCO) is the heartbeat of functional programming languages and the functional paradigm, without it, functional programming really isn't possible on the current type of processors and memory models we have (I swear I'll be the first one on the planet to get myself a graph reduction processor).

So, basically, by not supporting TCO, Javascript turns from a language that you could (if you tried a little) write functional code in, into a language that  really wants to be functional, but can't, and one that really wants to be prototypal and can't.

Now, about prototypes. If you want to understand why Javascript's prototypes really, really suck, go learn a language like Io. Javascript basically ruins that elegance by trying to make it easier for Java/C++ programmers to understand, which would be okay, if it actually did that, but, as we all know, prototypes in Javascript are probably the most misunderstood concept in the entire language.

I would okay with all of the bad things of Javascript, if only it had TCO. If it had TCO, I would have probably never learned Scheme, and I would have loved to write form validators and login pages all day long with all the recursive goodness, but, someone went and screwed that up, so, we're all stuck with what we have.

Flask

Flask  is awesome.

Why do I think so? Well, read on.

Firstly, what is it? If you didn't click the Flask link at the top of the page despite the pain I took in putting it there, here's what the website says

Flask is a microframework for Python based on Werkzeug, Jinja 2 and good intentions. And before you ask: It's BSD Licensed!

Whenever you buy anything, you usually consider the brand behind it. For example, if you have to choose between two pairs of shoes priced the same, one being Nike and the other being some unknown brand that has a golden colored "Made in China" sticker, it is obvious which one you would select. Similarly, for Flask, I see that it has been developed by the Pocoo team, whose code is excellent quality and they are also the people behind Sphinx, which, as most of the people in the Python crowd know, is used for the Python Documentation.

Next up, is installation. Not much explaining to do here, the instructions are on the front page! Flask is installed with easy_install, and runs with no configuration (this matters when you've done J2EE in the past *shudders*).

The Flask people know their way around docs. There's a quickstart, which gets you up and running quickly, and shows you enough for you to write a few simple pages. Then, there's a tutorial which builds a blog system from ground up using Flask. Both of these are extremely well written, and are very easy to follow. Also, Flask is dependent on two other Pocoo projects, Jinja2 (templating) and Werkzeug (WSGI), which are both also extremely well documented. As for the API, there are few projects that have everything so well documented. Almost every method call has an example, and all of them are coded very well.

Another thing I like (which Ruby on Rails folks may not), is that Flask doesn't tie you in, it doesn't make you name certain things certain ways, it doesn't assume things about the way you work, and everything is very transparent in the way it works, and this helps you find bugs quickly, even if you are new to the system.

Even though Flask is a microframework, it doesn't make you write all the code on your own. There's proper AJAX support, there's encrypted sessions, etc. etc.

Of course, no programming related article is complete without code, so, lets get to it.


(in case you can't see the embedded Gist, https://gist.github.com/1173206)

This is the code on the Flask main page. As you can see, the idea is dead simple. Flask maps requests onto the functions you tell it to, and your functions return HTML (or whatever the heck you want). There isn't a separate routes file.

Okay, so, say you've gotten tired of cramming all the HTML onto a string, you can use this:


(https://gist.github.com/1173212)


Just stuff "index.html" into the "templates/" folder in the same directory. The templating engine is Jinja2, and you can change this, too, if you'd like. Say, you want to parse a form and put some stuff on the session cookie, like you would when someone logs in: (I'm going to omit the app.run() stuff, its getting annoying):


(https://gist.github.com/1173225)

Where you use request.form[] to get data from the form (with the key being the name of field), and session[] to set/get things on the session cookie.

And, that's not all. Flask does message flashing, logging, WSGI middlewares, cookies, redirects, per-request objects, etc. all out of the box. And, it doesn't stop there. You can write extensions, or use extensions people have already written, such as the SQLAlchemy extension.

Database access is not part of the framework, which keeps it away from all the junk that involves getting multiple databases to work, but, the SQLAlchemy extension is quite well tested. My favorite database these days is MongoDB (with pyMongo), mostly because of its ease of use and its compatibility with the way Flask works.

Last, but, definitely not the least, is the code quality of Flask. The project is hosted on Github, and has over 1300 watchers. The code is layed out excellently, everything is broken into quite digestible pieces. If you encounter a problem (that for some odd reason you can't find in the docs), a few glances through the code will help you out. The code is very readable, isn't overengineered, and quite small to top it off. If you spend two hours, you could probably understand nearly all of the things that make up Flask, and this gives you something that you don't get with something as large as Django, a complete understanding. You know what happens when you call a blueprint, and you know how globals work, so, when something goes wrong, you know how to fix it, or at least an idea of where the problem is occurring. Another thing is that unlike "one file frameworks" (I'm looking at you, Bottle), that stuff all their dependencies in one file, Flask spreads everything out evenly, so people can actually read the code.

All in all, I really love Flask, and I hope you will too, just give it a try.

In case you're looking for a webhost that supports it, I like Webfaction (I'm not affiliated with them or anything).

PhoneGap and jQuery Mobile

I recently started working on a project with phonegap and jquery mobile, and I'll tell you how it went.

When I first started off, I did not know about jQuery Mobile, and I decided I would just write the app in plain ol' Javascript and HTML5. I wrote part of the app, but, I kept getting the lingering feeling that it did not look on par with some of the mobile apps I have seen. I am basically terrible at design, so, I tried to find a way to solve this problem. Then, I found this. I got jQuery mobile, wrote a sample app, and I was amazed.

The declarative interface is no short of AWESOME. This is how concise it is.

With 15 lines of code, here's what we have. Firstly, gradients. I hate doing gradients, I hate all the webkit and moz stuff, and jquery mobile conveniently deals with it. Next up, we have rounded corners. I also hate rounded corners, I've never gotten them right. Yet again, they're here by default. We also have sliding transitions between the pages, and the pages are all defined in one file, instead of being plastered all over the place. Icons are also present, and a large collection of them, too. And, it looks like a mobile app. That's the most important part, if I had written this without any help from jQuery, it would look like a very ugly web app. jQuery mobile is almost like a friggin' design team! The themes provided are also excellent, and, of course, if you would like something extra, you can always customize everything.

Now, onto jQuery mobile's documentation. Of course, despite everything, I did run into a problem. The problem was that I was populating a ListView with AJAX, and, for some weird reason, jQuery mobile would refuse to style it for me. So, I took a quick look at Google, within 10 minutes, I figured out the solution to my problem with jQuery mobile's excellent documentation (its this in case you're interested, scroll down to the updating lists part).

Now, I still have a question I have been unable to solve, its posted here. Can any of you help? Comments or answers on StackOverflow would be great.

Lets go onto PhoneGap. Me, being lazy, did not want to install the SDK's for Android, Blackberry, and iPhone, so, I tried out the PhoneGap Build. It was overall very good, still some rough edges, like, on some days, Blackberry builds did not work, but, their developers are very good at responding to bug reports.
PhoneGap did not get in the way, and let me work in pretty much transparent Javascript. LocalStorage and WebSQL facilities are very good.

One thing I would like to see is good IDE support for Jquery Mobile, and Javascript overall.

But, aside from that, it was a very pleasurable experience, and I would definitely develop with the toolset again.

ShinyCar into MicroJS

I got a small localStorage HTML5 library I wrote into MicroJS, its called ShinyCar.

ShinyCar is very simple, it lets you set objects as keys and values of HTML5 localStorage with JSON, and it lets you either have functions for this, or, you can add this functionality to your localStorage object. Its very simple, not many LOC, but, I have used it a lot, and will continue using it in the future.

Fork me at Github!

Experience with Writing a Chrome Extension for Flipkart, Flipkart API

Even though I live in the USA, my family and I maintain contacts with India and often visit. And, when I am there, I have started using Flipkart to order books, and I find it quite a bit cheaper than competitors.

I also want to quickly look up books, see results and availability on Flipkart, and, I also use Google Chrome (and Firefox, but, I'm moving to Chrome slowly). So, I wrote my first Chrome Extension, and I will try to describe my experience.

Right off the bat, the introductory tutorial was excellent, and I was up and running within 10 minutes. By this time, I had a very basic Flipkart extension going, and was pretty excited with the progress.

Ten minutes later, I ran into a small problem. I was trying to use the DOM to turn a button's value from "Search" to "Loading...", and I had written the code, but, it wasn't working. So, I tried to figure out how to debug it. For 20 or so minutes and bashed my head against the problem with console.log() statements scattered throughout the code. Then, I read the debugging tutorial which was also excellently written by the very clever people over at Google.

I have been a Firebug devotee, but, once I started moving over slowly to Chromium/Chrome, I am liking the developer tools more and more. And, for writing the chrome extension, I could use the developer tools. The debugger is very good, and the syntax checker is extremely useful. I had a ton of trouble getting AJAX to work properly without a ton of lag, and the developer tools have excellent AJAX debugging, and I had absolutely no trouble.

Now, for the bad parts. The biggest annoyance in developing the extension wasn't really chrome or any of that, it was just that I would have saved myself a lot of page scraping if Flipkart provided a simple API that let me access its product database, I think I might start a project, so I can write an external one. The next annoyance (completely unrelated to Chrome), was weak typing. Javascript just totally ruined my life on this project, because I was doing a few things very stupidly,
a) Not using jQuery
b) Using the "+" operator without type checking
c) Not properly looking at Flipkart's DOM before trying to implement code that uses it

This isn't Javascript's fault (except b, which the world hates it for), more like my fault.

All in all, writing a chrome extension was a very good experience, and I would happily write another, I just need any ideas you have :)

About me

• I like computer science (algorithms are cool), here's what I don't like about it:
• SQL
• PHP (although this does get better with frameworks and OOP)
• Objective-C (it turns a simple syntax of C into something very complicated)
• Here's what I really like about it:
• Algorithms 
• Python
• C/C++
• Haskell and Lisp (I'm not very good at these, but, getting better)
• I also like mathematics
• Why?
• It sharpens reasoning skills
• I participate in mathematics competitions
• OCW MIT is like a gateway drug
• Mathematics problems (not exercises as found in most textbooks), are fun.
• I'm also 13, so, I have more time to spend on hobbies than someone that has to work.