5

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?

Chris Martin
  • 30,334
  • 10
  • 78
  • 137
Xiufen Xu
  • 531
  • 1
  • 3
  • 19

2 Answers2

5

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)))))))
Community
  • 1
  • 1
Timothy Pratley
  • 10,586
  • 3
  • 34
  • 63
4

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.

Community
  • 1
  • 1
Piotrek Bzdyl
  • 12,965
  • 1
  • 31
  • 49
  • Really good answer. For large `limit`s, # of retries shouldn't be an issue. – muhuk Mar 07 '16 at 09:40
  • 1
    Actually I was wrong, it can be an issue as every bit doubles the search space. And the bigger `limit` gets, the worse it becomes. – muhuk Mar 07 '16 at 09:51