Thursday, December 22, 2016

Repeating decimals and encoding messages

I have another math nurd post. 

It has a loose relationship with a branch of mathematics called number theory, and a close relationship to a sleepless night.

I was (for no obvious reason) thinking about repeating decimal numbers that are the result of dividing one number by another.  A good example:  .33333.... = 1/3.

I started wondering if would be possible to define two numbers A and B to generate any arbitrary sequence of repeating decimal numbers when calculating A/B.  Oh yes, those dark winter nights!  For a triplet of repeating digits, my initial mental math went like this:

A/B = .WXYWXYWXY.....

where W,X and Y are numbers between 0 and 9

Multiply A/B by 1000 and we get:  1000*A/B = WXY.WXYWXYWXY....

The value behind the decimal, clearly, is the same as A/B so we can write:

1000*A/B = WXY*A/B.  If we divide both sides by A/B we get:  1000 = WXY.  Clearly, there is no sequence of 3 digits that can equal 1000 (999 is the closest we can get).  So it would appear that there is no solution for this. 

Not so.   Let's say WXY = 123.  Now set A = 123 and B = 999.  Get out the old 4-banger calculator and what do we see?  123/999 = 0.123123....

So what is the problem here?  Unfortunately, simple math (remember I mentioned it was a late night).  The real equation for this relationship is as follows:  1000*A/B = WXY + A/B.  Where WXY really equals W*10^2 + X*10^1 + Y*10^0

If we go back to setting WXY = 123, we get:  1000*A/B = 123 +A/B, or 999A/B=123.  I.E., 999A = 123B, or A/B = 123/999.  Do the division again, and you get:  .123123....

A straightforward generalization tells us that we can generate any arbitrary repeating-decimal number by multiplying the sequence of numbers by the power of 10 equal to the length of the sequence and dividing it by 10^K -1, where K is the length of the sequence.

An interesting possibility raises itself in this discussion of rudimentary numerical analysis.  Suppose we encode the alphabet by setting A = 01, B = 02....Z = 26.  If you have a message you want to send securely, encode it into a string of tuples (2 digits each) and treat the whole thing as your repeating rational number.  Unfortunately, not too hard to decyper, right?  Well, now multiply the W-wide number (equal to 2*the number of characters in your message) by another number, large enough to ensure some carries between each tuple.  NOW we have a more interesting thing to decode, because the resulting tuples depend on each other.  It becomes a context-dependent code.  The keys to the code are the multiplier....and the length of the message.  In today's age, the two could be sent separately without too much trouble so time-sensitive information (which would take some time to decode) would be relatively secure.  Attempts to crack the code would be complicated by the fact that the encoded message string is unique due to the context dependency.

Suppose we choose the multiplier to be 11.  This is an interesting example because it is equivalent to shifting the original code over by one, and adding the result to the original code.  It would completely alter the cypher.

Is this completely original?  Hah --- close to a zero chance of that.  But it is an interesting illustration of how easily a simple encoding scheme could be turned into a nontrivial decyphering problem, except for government level expertise.  Also, due to the fact that certain letter sequences occur pretty often, the encoding scheme would be susceptible to statistical analysis -- if long enough.

Relatively simple obsfucation techniques like reversing the digit sequence would still yield to this type of analysis, if the analysis is thorough enough.  Possibilities are endless though -- consider encoding some well-known text in the same fashion and adding its digit sequence to the message.  This is an example of the use of a code book, in addition to the mathematical encoding.  Without knowledge of the code book (and where the code string begins), things get difficult in a big hurry.  The code book string itself could be mathematically obsfucated by using yet a different multiplier.  And maybe reversed (or not) as well.  Ouch!




No comments:

Post a Comment