### Archive

Posts Tagged ‘programming’

Just some snippet of Haskell code today to return the last but one element of a list. The first implementation uses the built-in functions `last` and `take`.

```-- Return the last but one element of a list.  This implementation uses
-- last and take.
penlast :: [a] -> a
penlast xs = if null xs || length xs <= 2
else last (take ((length xs) - 1) xs)
```

The second implementation below uses the built-in functions `head` and `drop`.

```-- Return the penultimate element of a list.  This implementation uses
penhead xs = if null xs || length xs <= 2
else head (drop ((length xs) - 2) xs)
```

In science, mathematics, and informatics there are various problem solving competitions aimed at challenging and expanding the talents of high school students. In the biological science, we have the International Biology Olympiad, in mathematics the International Mathematical Olympiad, and in informatics the International Olympiad in Informatics and the Internet Problem Solving Contest.

But cryptology is very much at the intersection of mathematics and informatics. There are some famous competitions in cryptology such as the National Institute of Standards and Technology (NIST) call in 1997 for a new encryption standard, a challenge that was met in late 2001 with the adoption of the Rijndael cipher as the Advanced Encryption Standard (AES) to replace the aging Data Encryption Standard (DES). The latest cryptology competition from NIST is a call for a new hash algorithm, called the Cryptographic Hash Algorithm Competition. As of this writing, the competition is in its third round of selection of a new hash algorithm.

The latter two competitions are oddly out of place for high school students. What comes close to a cryptology challenge for high school students is a competition I very recently learned about: the Crypto Challenge Contest. The contest is not really designed exclusively for high school students. You can find cryptology challenges suitable for high school students and up to cryptology researchers. However, many of the problems in Level I of the Crypto Challenge Contest are suitable for high school students. For those students who love a programming challenge, you might want to have a go at the problems in Level II. Happy problem solving.

Categories: cryptography, programming

## Converting from binary to integer

26 October 2010 1 comment

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.