### Archive

Archive for the ‘number theory’ Category

Problem: Implement a primality test in Haskell. Below is the code. The first implementation of the function divides uses a homemade function for finding the remainder when an integer is divided by another integer.

```-- The remainder when a is divided by b.
remainder :: Integer -> Integer -> Integer
remainder a b | a < b = a
| a == b = 0
| otherwise = remainder (a - b) b

-- Whether d divides n.
divides :: Integer -> Integer -> Bool
divides d n = remainder n d == 0
```

The second implementation of divides uses the built-in function rem to find the remainder upon division by an integer.

```-- Whether d divides n.  A more efficient version that uses the built-in
-- function rem.
divides :: Integer -> Integer -> Bool
divides d n = rem n d == 0
```

The full primality test follows:

```-- Whether d divides n.  A more efficient version that uses the built-in
-- function rem.
divides :: Integer -> Integer -> Bool
divides d n = rem n d == 0

-- The least divisor of n that is at least k.
ldf :: Integer -> Integer -> Integer
ldf k n | divides k n = k
| k^2 > n = n
| otherwise = ldf (k + 1) n

-- The least divisor of n.
ld :: Integer -> Integer
ld n = ldf 2 n

-- Primality test.
prime :: Integer -> Bool
prime n | n < 1 = error "must be a positive integer"
| n == 1 = False
| otherwise = ld n == n
```

## 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.

## Number theory & RSA public key cryptography

All versions of the tutorial are available from the download page on its website. For the adventurous of heart, I have also made the full $\LaTeX$ source of the document available.