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
The following is an updated and edited version of my posts to this sage-support thread.
You have a bitstring as output by
and you want to convert that bitstring to an integer. Or in general, you want to convert a bit vector to its integer representation.
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.
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 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.