6

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?

user668074
  • 1,111
  • 10
  • 16
  • Not an exact duplicate, but did you see https://stackoverflow.com/questions/2283119/how-to-convert-a-integer-to-a-bytestring-in-haskell? – Thomas Nov 01 '17 at 07:26
  • @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. – user668074 Nov 01 '17 at 07:30
  • @user668074 The [`Binary` instance for `Integer`](https://hackage.haskell.org/package/binary-0.8.5.1/docs/src/Data.Binary.Class.html#line-311) 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. – Cirdec Nov 01 '17 at 08:53
  • @Cirdec, thank you, I wasn't sure how Integers were represented. Do you know how the Natural integer type is represented? – user668074 Nov 01 '17 at 09:03
  • The [`Binary` instance for `Natural`](https://hackage.haskell.org/package/binary-0.8.5.1/docs/src/Data.Binary.Class.html#line-368) 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](https://stackoverflow.com/a/47050983/414413). – Cirdec Nov 01 '17 at 15:34

1 Answers1

5

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
Cirdec
  • 24,019
  • 2
  • 50
  • 100
  • 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. – user668074 Nov 02 '17 at 06:50