How can I convert from a ByteString to a positive Integer

Question

I am trying to generate large random prime numbers (1024 bit-ish) so I need a way to generate large positive random numbers.

I began with System.Random but want to move to Crypto.Random from the crypto-api package.

The Crypto.Random only produces bytestrings, so I need a way to convert to an Integer type. What is the best way to do this?

Sentiment

Not an exact duplicate, but did you see #2283619? – Hamish

@Thomas, I saw that, it's converting in the other direction and I had some trouble using Data.Binary. I can easily convert Integer types to bytestrings, but often converting from random bytestrings to Integer type causes an error. I don't know the internal representation of Integer but I assume generating random bytes can make invalid numbers. – Sentiment

@Sentiment The Binary instance for Integer writes a tag for whether it's a small integer that fits in a few bytes or a big one that is in many bytes, and for large integers writes a sign byte and a list of bytes preceded with a length; if the length doesn't match the number of bytes you'd get an error. – Dumah

@Cirdec, thank you, I wasn't sure how Integers were represented. Do you know how the Natural integer type is represented? – Sentiment

The Binary instance for Natural is in the same file. Neither of these is how they're represented in memory. Both end up reading a list of bytes and folding it one byte at a time. Instead of mucking around in formatting your byte string into one of these formats, fold it yourself as shown in my answer. – Dumah

Answer 1

Without poking around in the internals of GHC.Integer you can fold the bytestring into an Integer one byte at a time.

import qualified Data.ByteString as BS
import Data.Bits

fromBytes :: ByteString -> Integer
fromBytes = BS.foldl' f 0
  where
    f a b = a `shiftL` 8 .|. fromIntegral b

If you want to read Natural numbers instead of Integers you can give this a more general type signature.

-- Read bytes in big-endian order (most significant byte first)
-- Little-endian order is fromBytes . BS.reverse
fromBytes :: (Bits a, Num a) => ByteString -> a
fromBytes = BS.foldl' f 0
  where
    f a b = a `shiftL` 8 .|. fromIntegral b

Dumah

This seems like the best way to do this in general. I also found the monadcryptorandom package. It allows one to bypass the bytestring part of the Crypto.Random module entirely and get integers. – Sentiment