I ran across binary expansion from Friendly Introduction to Number Theory, A (3rd Edition) while I was studying the successive squaring technique and thought it was worth writing a little python code for it. All you do with binary expansion is write the number in terms of base 2 powers. For example

Notice how each number is a combination of powers of 2. We are just adding different combinations of power of 2 to get the desired number. If we look at as 'n' increases from 0 to infinity. Then the sequence would look like this:

=

With binary expansion we can produce all the numbers that are in between natural powers of 2. We subtract the biggest power of 2 from the desired number, then we repeat this process with the remainder. We keep repeating the process until a remainder of 0 is obtained. This process resembles the same steps you do in long division, except our final remainder will always be 0.

Lets take the number 133333, which we are using for our RSA:

- 1.) We see what power of 2 is bigger than or equal to 133333, so we try a couple of powers of 2.

, , , , , , , , , , , , , , , , , ,

- 2.) We see that 2^18 is to large so we have to use 2^17. We subtract 2^17 from 133333.

- 3.) So we can rewrite 133333 as follows:

- 4.) Now we lets do the same thing for 2261, we look for the biggest power of 2 less than or equal to 2261.

so

- 5.) Now we can rewrite as follows:

- 6.) So then we do the same thing to 213 now, we look for a power of 2 less than or equal to 213.

so

- 7.) Then our 133333 now looks like this:

- 8.) We still can keep going, so we continue to go along with this method. We look for a power of 2 less than or equal to 85.

so

- 9.) We then express 133333 as follows:

- 10.) Again, we keep going with our new number 21. We look for a power of 2 less than or equal to 21.

so

- 11.) 133333 now is expressed like this:

- 12.) We are close to the end here, we just need to keep going. We now look for a base 2 less than or equal to 5:

so

- 13.) Now our expression looks like this:

- 14.) We get to the final step for writing 133333 in base 2. We need to find a base 2 less than or equal to 1. We know from the rules of exponents that

so

- 15.) Now we are done, we can finally write 133333 in terms of base 2. Starting from the beginning, it looks like this:

So now we covered a easy example and a little more complicated one. It does not really take that much work to calculate all this, because of how fast powers of 2 can grow. So lets write a little python code that can do it for us. Again, any code I write here is to help understand mathematical methods. If you really want to program a more efficient code then at the top of your code write this line

import up down up down left right left right a b a b select start

This code will instantly improve any code you can write. So anyway, we began our code with finding the highest power of 2 that is less than or equal to our given number.

def highest_base_2(temporary_exponent): highest_base_2 = False list_of_powers_of_2 = [] power = 0 while highest_base_2 &lt;&gt; True: if 2**power &lt; temporary_exponent: power += 1 else: power -= 1 list_of_powers_of_2.append(power) highest_base_2 = True return 2**power,list_of_powers_of_2[-1]

Now this code returns the highest power of 2 less than or equal to our number already evaluated. So if the highest power of 2 is 2^8 then the code will return 256. Now we can write the main function that will expand our number in powers of 2. One list will contain the evaluated numbers like in our examples. The other list will contain the exponents of 2 that we raise 2 with.

def highest_base_2(temporary_exponent): highest_base_2 = False list_of_powers_of_2 = [] power = 0 while highest_base_2 &lt;&gt; True: if 2**power &lt; temporary_exponent: power += 1 else: power -= 1 list_of_powers_of_2.append(power) highest_base_2 = True return 2**power,list_of_powers_of_2[-1] def binary_expansion(): number = input('Enter the number: ') temporary_number = number list_of_base_2 = [] list_of_powers_of_2 = [] while temporary_number &lt;&gt; 1: base_2,powers_of_2 = highest_base_2(temporary_number) list_of_powers_of_2.append(powers_of_2) list_of_base_2.append(base_2) temporary_number = temporary_number - base_2 list_of_base_2.append(temporary_number) print 'this is our binary expansion list', list_of_base_2 print 'this is our powers of 2 list', list_of_powers_of_2 binary_expansion()

After that the output would look like this:

So our 133333 would look like this:

Already, I noticed with this code I don't actually put the 2^0 in our list of powers. Its in the calculations, but its just not in the list. That needs to be fixed if you want a complete list of powers of 2.

References:

- Silverman, Joseph H.
*A Friendly Introduction To Number Theory*. 3rd ed. Upper Saddle River, New Jersey: Pearson Prentice Hall, 2006. 106-107. Print. - "Exponentiation."
*Wikipedia, the free encyclopedia*. N.p., n.d. Web. 26 Jan. 2013. <http://en.wikipedia.org>. Path: http://en.wikipedia.org/wiki/Exponentiation.