Archive
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.
Optimized parity testing
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 
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
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
