How to generate a long number randomly in clojure

Question

There is long integer number m = 38941629971148227236N. I want to generate a number e between 1 < e < m, and check e if satisfy this requirement: gcd(e,m)=1. My method is to use (long (rand m)) to generate e randomly, I got a warning:

IllegalArgumentException Value out of range for long:
1.7166121075068025E19  clojure.lang.RT.longCast (RT.java:1254) 

My code is:

(defn find-e [m]
(loop [e (long (rand m))]
    (if (= 1 (gcd e m)) e
        (recur (long (rand m))))))

I know the result out of range for long, but I don't know is there any way to solve this problem?

Answer 1

The problem lies with (long (rand m)) because the random value you are selecting is often much larger than can fit inside a long. You want to make a bigint not a long. Here is one way around it:

(bigint (bigdec (rand 38941629971148227236N)))

Note that selecting random numbers in this way is really producing a double which is converted to a bigdec which is converted to a bigit. As such, the domain of possible random values is limited. Using a double as the base random number means not all possible bigints will be generated. If you want true bigint random selection, take a look at this answer... but if you don't care too much so long as you get a bigint in the right range this might work for you:

(defn find-e [m]
  (loop [e (bigint (bigdec (rand m)))]
    (if (= 1 (gcd e m))
      e
      (recur (bigint (bigdec (rand m)))))))

Answer 2

You could build it using the knowledge from the answer on generating random java.math.BigInteger to have a more efficient solution:

(defn random-bigint [limit]
  (let [bits (.bitLength limit)]
    (loop [result (BigInteger. bits (ThreadLocalRandom/current))]
      (if (< result limit)
        (bigint result)
        (recur (BigInteger. bits (ThreadLocalRandom/current)))))))

Then your code could reuse that function:

(defn find-e [m]
  (loop [e (random-bigint m)]
    (if (= 1 (gcd e m))
      e
      (recur (random-bigint m)))))

This approach to generate random numbers and then checking if it's within the desired range has a drawback that if you are very unlucky your loop will take a lot of iterations. You might extend it to have a limit on number of retries and fail with an exception when its exceeded.