Converting from binary to integer

The following is an updated and edited version of my posts to this sage-support thread.

Problem

You have a bitstring as output by

sage.crypto.stream.blum_blum_shub

and you want to convert that bitstring to an integer. Or in general, you want to convert a bit vector to its integer representation.

Solution

Here are two ways, assuming that you want the bits in little-endian order, i.e. you read the bits from right to left in increasing order of powers of 2.

sage: version()
'Sage Version 4.5.3, Release Date: 2010-09-04'
sage: from sage.crypto.stream import blum_blum_shub
sage: b = blum_blum_shub(length=6, lbound=10**4, ubound=10**5); b
100110
sage: type(b)
<class 'sage.monoids.string_monoid_element.StringMonoidElement'>
sage: # read in little-endian order
sage: # conversion using Python's built-in int()
sage: int(str(b), base=2)
38
sage: # conversion using Sage's built-in Integer()
sage: Integer(str(b), base=2)
38

Now assume you read the bitstring as output by blum_blum_shub in big-endian order, i.e. from left to right in increasing order of powers of 2. You simply convert the bitstring to a string, reverse that string, and apply any of the above two methods.

sage: # reversing a string
sage: str(b)
'100110'
sage: str(b)[::-1]
'011001'
sage: # read in big-endian order
sage: int(str(b)[::-1], base=2)
25
sage: Integer(str(b)[::-1], base=2)
25

Or you can do as follows:

sage: b = "100110"
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b))
25
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b[::-1]))
38

Another way is to use Horner’s method. Here’s a Sage function that computes the integer representation of a bit vector read using big-endian order. A usage example is also shown.

sage: def horner(A, x0):
...       # Evaluate the polynomial P(x) at x = x_0.
...       #
...       # INPUT
...       #
...       # - A -- list of coefficients of P where A[i] is the coefficient of
...       #   x_i.
...       # - x0 -- the value x_0 at which to evaluate P(x).
...       #
...       # OUTPUT
...       #
...       # An evaluation of P(x) using Horner's method.
...       i = len(A) - 1
...       b = A[i]
...       i -= 1
...       while i >= 0:
...           b = b*x0 + A[i]
...           i -= 1
...       return b
sage: A = [1, 0, 0, 1, 1, 0]
sage: horner(A, 2)
25

As an exercise, modify the function horner to output the integer representation of a bit vector that is read using little-endian order.

About these ads