Archive

Posts Tagged ‘number theory’

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

14 October 2010 Leave a comment

I have released version 1.1 of the Sage tutorial “Number theory and the RSA public key cryptosystem”. There is little change in terms of content. However, note that I now use the GNU Free Documentation License v1.3+ for the tutorial. Here are the relevant files you can download for your reading pleasure.

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.

The tutorial is meant to be educational. I don’t pretend that it is complete in any way. Any suggestions and/or criticisms for improving the tutorial are more than welcome. Enjoy and happy Sage’ing.

Optimized parity testing

6 October 2010 Leave a comment

To test the parity of an integer is to determine whether it is even or odd. Letting n = 132469, we can test the parity of n by computing its value modulo 2. This can be done either by using the Sage built-in mod function, the Python modulo operator %, or by using the Python bitwise operator &. The operator & is bitwise conjunction, i.e. it corresponds to multiplication over the Galois field \mathbf{F}_2 of two elements. The integer n = 132469 is odd, hence the result of parity testing via mod, %, and & should each return 1.

sage: n = 132469
sage: mod(n, 2).lift()
1
sage: mod(n, 2)
1
sage: n % 2
1
sage: n & 1
1

However, the test using the bitwise operator & is the fastest of all:

sage: %timeit mod(n, 2).lift()
625 loops, best of 3: 42.2 micro second per loop
sage: %timeit mod(n, 2)
625 loops, best of 3: 42.2 micro second per loop
sage: %timeit n % 2
625 loops, best of 3: 1.22 micro second per loop
sage: %timeit n & 1
625 loops, best of 3: 1.02 micro second per loop

The program below demonstrates how to do parity testing using C.

#include <stdio.h>

/* Parity testing using bitwise AND.
 */
static void parity_and(int n)
{
    if (n & 1)
        printf("%i is odd\n", n);
    else
        printf("%i is even\n", n);
}

/* Parity testing using the modulus operator.
 */
static void parity_mod(int n)
{
    if (n % 2)
        printf("%i is odd\n", n);
    else
        printf("%i is even\n", n);
}

int main(void)
{
    int n = 132469;
    int m = 132470;

    printf("Parity testing using modulus operator\n");
    parity_mod(n);
    parity_mod(m);
    printf("Parity testing using bitwise AND\n");
    parity_and(n);
    parity_and(m);

    return 0;
}

The output of the program is:

Parity testing using modulus operator
132469 is odd
132470 is even
Parity testing using bitwise AND
132469 is odd
132470 is even

List within a list

15 September 2010 Leave a comment

The problem below was asked on the AskSage forum. Below I restate the problem and three possible solutions.

Problem

I have a short list of primes

sage: L = [2, 5, 23]

and a longer list of primes

sage: P = primes_first_n(20); P
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

How do I check that all members of L are contained within P?

Solution

You can use a brute-force search by defining your own custom function. This option doesn’t assume that elements in your lists are unique. Your lists can contain duplicate elements if you want.

sage: def is_sublist(shortlist, longlist):
....:     for e in shortlist:
....:         if not (e in longlist):
....:             return False
....:     return True
....: 
sage: L = [2, 5, 23]
sage: P = primes_first_n(20); P
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
sage: is_sublist(L, P)
True
sage: L + [23]
[2, 5, 23, 23]
sage: is_sublist(L + [23], P)
True
sage: L.append(next_prime(P[-1])); L
[2, 5, 23, 73]
sage: is_sublist(L, P)
False
sage: is_sublist(L + [23], P)
False

Alternatively, you can use the built-in functions itertools.imap and all. The function itertools.imap is efficient when your lists are large, e.g. having hundreds or even hundreds of thousands of elements. This second option doesn’t care if your lists have duplicate elements.

sage: import itertools
sage: L = [2, 5, 23]
sage: P = primes_first_n(20); P
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
sage: L + [23]
[2, 5, 23, 23]
sage: all(itertools.imap(lambda x: x in P, L))
True
sage: all(itertools.imap(lambda x: x in P, L + [23]))
True
sage: L.append(next_prime(P[-1])); L
[2, 5, 23, 73]
sage: all(itertools.imap(lambda x: x in P, L))
False
sage: all(itertools.imap(lambda x: x in P, L + [23]))
False

Or, as Mitesh Patel said, you could use set. This third approach assumes that the elements in each list are unique, i.e. each list doesn’t contain duplicate elements.

sage: L = [2, 5, 23]
sage: P = set(primes_first_n(20))
sage: set(L)
set([2, 5, 23])
sage: set(L).issubset(P)
True
sage: set(L + [23])
set([2, 5, 23])
sage: set(L + [23]).issubset(P)
True
sage: L.append(111); L
[2, 5, 23, 111]
sage: set(L)
set([2, 111, 5, 23])
sage: set(L + [111])
set([2, 111, 5, 23])
sage: set(L + [111]).issubset(P)
False
sage: set(L).issubset(P)
False

Version 0.4 of book “Sage for High School” released

31 July 2010 1 comment

I’m happy to announce the release of version 0.4 of the book Sage for High School. My primary concern in this version was to flesh out the chapter “Vectors and Matrices”. The PDF and source tarball are available for download. The chapter outline is as follows:

  • Scalars and vectors
  • Add, subtract, and multiply vectors
  • Three-dimensional vectors
  • The dot product
  • Parallel and perpendicular vectors
  • Matrices and determinants
  • The cross product

Version 0.4 adds another section to the chapter “Number Theory”, called “Kid RSA”. This additional section explains a simplified version of the RSA cryptosystem, using number theoretic concepts introduced in the chapter “Number Theory”. The simplified cryptosystem is called “Kid RSA”, developed by Neal Koblitz. You can find Kid RSA in his book:

  • N. Koblitz. Algebraic Aspects of Cryptography. Springer, 1998.

Version 0.3 of book “Sage for High School” released

30 July 2010 Leave a comment

I have released version 0.3 of the book Sage for High School. Both the PDF and source tarball are available for download. This version fleshes out the chapter “Number Theory”, with materials for the following sections:

  1. Integers
  2. Prime numbers
  3. Divisibility
  4. Greatest common divisors: relatively prime integers
  5. Least common multiples: Simplifying fractions
  6. Clock arithmetic

Primes and Factorization Book

26 June 2010 Leave a comment

It’s the weekend over here. I had the whole of Saturday devoted to procrastination, the result of which is version 0.1 of a new book project. Currently, the book is called “Primes and Factorization”. Its aim is to describe theory and present algorithms relating to factorization. The first chapter “Unique Factorization” shows that every integer n > 1 has a unique prime factorization. The book is licensed under the terms of the GNU Free Documentation License. Any source code is licensed under the terms of the GPLv2+. I have uploaded a source tarball and PDF of version 0.1. Enjoy.

Follow

Get every new post delivered to your Inbox.