Dear reader: Try it!

The solution is simple, straight forward and very nice. And I didn’t find it.

I found something else. My approach was to look at the largest-number-so-far (max) and the smallest-number-so-far (min) as the boundaries of a region. A number outside this region must be larger than max or smaller than min and causes that boundary to change.

To check if a number (a) was outside that region a little computation came to my mind:

check = (max - a)*(min - a);

You would expect n to be smaller than max, so (max-n) should be positive.

You would expect n to be larger than min, so (n-min) should be positive, too.

Two positive numbers multiplied result in a positive number again.

So, if n was outside the boundaries, check would become negative. I only had to check which boundary was exceeded and that’s it:

if (check < 0)
    if (a > max)
        max = a;
    else
        min = a;

Using this approach the number of comparisons  converges to 1 when the length of the list grows. So I found a solution that is way better than 1,5 comparisons per number, didn’t I?

Boooooh

No, I didn’t. I cheated. In fact  (max-a) and (min-a) are comparisons, they just don’t use > or <.

(Actually it’s the other way around: To compute < or > most processors do a subtraction and compare the result to 0.)

So – if you count the subtractions as well you get 3+ comparisons per number…

The intended solution to the challenge (and the code you should provide in your exam) is:

a = list[count++];
b = list[count++];

if (a<b)
{
    if (a<min) min = a;
    if (b>max) max = b;
}
else
{
    if (b < min) min = b;
    if (a > max) max = a;                    
}

So – what’s the point of this post?

The point is: My silly approach can be faster than the standard solution. Depending on the type and range of the numbers in the list calculating and probing check needs less time than the comparisons in the standard solution.

It may not be much, but sometimes small advantages matter.  For example: For an integer-list of length 10^8 with values from -10.000 to 10.000 my approach is 0.02 seconds faster (on my current laptop). And has less code.

So if you feel like using it – I won’t charge you.

Let’s say x and y are digits and ‘xy’ is not ‘x*y’, but the number that consist of the digits x and y.

xy – yx = multiple of 9.

Is it always true? Yes, it is:

(10x + 1y) – (10y + 1x) = multiple of 9?
9x – 9y = multiple of 9?
9(x-y) = multiple of 9? Yes, for sure.

I calculated the numeric values of xy and yx by "10 times the higher position + 1 time the lower position", just like we all do every day in our beloved decimal-system. More formally we describe the factor for the position (1, 10, 100…) by

10^position, (position is zero-based, counting from right to left, of course)

Now, when we change the position of a single digit within a number we change its numeric value from

x*10^(old position) to x*10^(new position).

We can neglect x here, because it’s a factor that occurs in both values, so we can get rid of it by division.
The remaining part for building the difference is

10^p1 – 10^p2, a formula that always produces multiples of 9: 10-1, 1000-100, 10-1000000.

Conclusion

Since the difference of a number and one of it’s permutations is a sum of (10^p1-10^p2)-parts, which are all multiples of 9, the total also can be divided by 9.

It works with a any length. Some examples:

Length 2
23 – 32 = -9 
84 – 48 = 36
60 – 06 = 54

Length 3
123 – 132 = -9
and so on…

It still works for changing the front position:
123 – 213 = -90

In fact it works for changing any position:
123 – 321 = -198 (-22*9)

This leads to the conclusion I stated in the beginning. The difference of any permutation of the same number is a multiple of 9. Feel free to check it with you favorite numbers.

It’s not a great mathematical invention (if it is, please let me know), but I didn’t know it, didn’t expect it und find it kind of fascinating. I asked a couple of friends and no one was aware of this.

I still try to find a way to use these fact, maybe for spell-check-like for numbers or a fast calculation of permutations, but so far it seems just useless

Instead I can provide a proof for numbers of any length and I’ll post it here in ten days from today. Meanwhile I want you to try it yourself. The proof is really, really simple, almost trivial and it won’t cost you more than five minutes to understand it all.

Please email or comment your solution!

How do we get our private-and-public-key-pair?

1. Choose two distinct (large) random prime numbers p and q
   p = 7,   q = 3.
   
2. Compute n = p*q. This n is used as the modulus for both the public and private keys
   n = 7*3 = 21.
3. Compute the totient: phi(n) = (p-1)(q-1)
   phi(21) = (7-1) * (3-1) = 12.
4. Choose an integer e such that 1<e<phi(n) and that e and phi(n) share no factors other than 1 (i.e. e and phi(n) are coprime.). e is released as the public key exponent.
   In order to chose an e I will factorize my phi(12) first: 12 = 2*2*3.
   I chose e=5. e does not necessarily have to be prime but it makes it easier to avoid sharing a factor.
5. Compute an integer d to satisfy the congruence relation d*e mod phi(n) = 1; d is kept as the private key exponent.
   “congruence relation” sounds more complicated than it actually is: Take two different numbers and apply the same modulo-operation to them (like mod 3). If the result is the same for both you may call your integers congruent modulo 5.  Like 11 and 16 are congruent modulo 5, since 11 mod 5 = 1 and 16 mod 5 = 1.
   So we are looking for a integer d that fits into
   d * 5  mod 12 = 1.
   I needed some tries here and wrote some lines to find the lowest d = 5. With one d found you can find all but just adding 12 :-). I didn’t want to take 5 as the private key exponent, since having the same exponent for encryption and decryption is… well… stupid. So I’ll choose 17.
   17 * 5 mod 12 = 1.
   85 mod 12 = 1.  Correct!

Do we have our private and our public key now? Yes, we have. Note that a key is not one single number but a pair of two numbers. Both are needed in the processes of encryption und decryption. One is the exponent and the other the modulus. Just a second and you’ll see why.

public key: e =5 (exponent) / n = 21 (modulus).

private key: d = 17 (exponent) / n = 21 (modulus). 

Let’s encrypt something

We have given our public key to anyone we know. And we kept our private key hidden somewhere under the bed. Now a beautiful and clever girl named Alice wants to send me a message. Fortunately the letters of her message can be represented as a stream of bits and we interpret this stream as a number. So her message is 10. It is important that her message is lower than our modulus, we’ll later see why. Let’s call her original message m and the encrypted message c.

m=10

The encryption it a simple formula: c = m^e mod n.

c = 10^5 mod 21

c = 100000 mod 21

c = 19.

So Alice hands me a little note saying “19”. 19? What the hack is that supposed to mean?

Now the magic happens

I rush back home to find my private key and apply it to “19”

The formula for the decryption look very similar: m = c^d mod n.

m = 19^17 mod 21.

m = 5480386857784802185939 mod 21. (Try it using calc.exe)

m = 10!

Wow! Alice says “10” to us. Isn’t 10 the international code for “I would like to date you?” I think so.

Signing

To encrypt with the public key means you can decrypt only with the private key. The converse is also true – to encrypt with the private key means you can decrypt only with the public key. Try it!

How can utilize this? We can use it to guarantee that a message is from a specific sender.

I have been dating Alice for some time now and we are used to leave messages to each other at a hidden place. Unfortunately another girl – Eve – is very jealous and has spied our secret mailbox. One week ago she found a message from Alice to me. She couldn’t read it, but she threw it away and replaced it by a mean offense against me. She encrypted it using my public key (which is public ) and I thought it was written by Alice. The message started a little fight but luckily we found about Eve’s intention and started signing our messages. Now we transfer messages like this:

1. Alice writes me a message m.
2. She encrypts m using my public key, the result is c.
3. Now she encrypts c using her own private key, the result is cs (c signed)
4. She leaves me the message
5. I decrypt cs using her public key, getting c. (Eve can do this as well – but that’s it. She can’t read c and she can’t leave me a fake cs because she doesn’t have Alice’s private key.
6. I decrypt c using my private key and get back m – bingo!

Padding

Breaking this code (meaning “decrypt without having the private key”) is always a lot of work and hard trying. But is becomes much easier, when you know that m is short. That’s because you only have check that little fraction of configurations where m = c^d mod n leads to small ms. To avoid this small messages are artificially made longer until they are close to n. That process is called padding and even padding can be a tricky task.

Last question

We know what happens to short messages. But what happens to long messages? It is obvious that messages – seen as a number – can’t be greater than n-1, since the mod n – part of the decryption formula will never return values >n-1. I guess the message is split up in parts, but couldn’t find a satisfying answer. If I do, I’ll let you know.

Take care, 
Bob