基于 ANU 量子随机数服务器的随机数

Question

我被要求使用 ANU Quantum Random Numbers Service 来创建随机数并仅使用 Random.rand 作为后备。

 module QRandom

   def next
     RestClient.get('http://qrng.anu.edu.au/API/jsonI.php?type=uint16&length=1'){ |response, request, result, &block|
       case response.code
         when 200
           _json=JSON.parse(response)
           if _json["success"]==true && _json["data"] 
             _json["data"].first || Random.rand(65535)
           else
             Random.rand(65535) #fallback
           end
         else
           puts response #log problem
           Random.rand(65535)   #fallback
       end
     }
   end

 end

他们的 API 服务给我一个 0-65535 之间的数字。为了为更大的集合创建随机数，比如 0-99999 之间的随机数，我必须执行以下操作：

(QRandom.next.to_f*(99999.to_f/65535)).round

我觉得这是错误的做法，因为如果我要使用从 0-3 创建数字并将它们转换为 0-9999 的 space 的服务（无论是否为量子），我有我总是得到 4 个数字的选择。如何使用生成 0-65535 之间数字的服务为更大的数字集创建随机数？

Answer 1

将您获得的单个数字视为 16 位随机数。要生成更大的随机数，您只需要更多位即可。棘手的一点是弄清楚多少位就足够了。例如，如果您想从 0 到 65000 的绝对公平分布中生成数字，那么很明显 16 位是不够的；即使您覆盖了范围，某些数字被选中的概率也会是其他数字的两倍。

有几种方法可以解决这个问题。使用 Ruby 的 Bignum（技术上发生在幕后，它在 Ruby 中运行良好，因为你不会溢出你的 Integer 类型）可以使用简单收集的方法更多的位，直到除法的结果永远不会模棱两可——也就是说，当你在除法中添加更多的有效位时，差异永远不会改变结果。

这看起来像，使用您的 QRandom.next 方法以 16 个为一组获取位：

def QRandom.rand max
  max = max.to_i # This approach requires integers
  power = 1
  sum = 0

  loop do
    sum = 2**16 * sum + QRandom.next
    power *= 2**16
    lower_bound = sum * max / power
    break lower_bound if lower_bound == ( (sum + 1) * max ) / power
  end
end

因为从你选择的源中获取随机位会花费你很多，你可能会从尽可能最有效的形式中受益，这在原则上类似于 Arithmetic Coding 并挤出最大在 0...max 中生成无偏数字时可能来自您的源的熵。您需要实现一个方法 QRandom.next_bits( num )，该方法返回一个整数，该整数由源自您的 16 位数字的比特流缓冲区构成：

def QRandom.rand max
  max = max.to_i # This approach requires integers
  # I prefer this:  start_bits = Math.log2( max ).floor
  # But this also works (and avoids suggestions the algo uses FP):
  start_bits = max.to_s(2).length
  sum = QRandom.next_bits( start_bits )
  power = 2 ** start_bits

  # No need for fractional bits if max is power of 2
  return sum if power == max

  # Draw 1 bit at a time to resolve fractional powers of 2
  loop do
    lower_bound = (sum * max) / power
    break lower_bound if lower_bound == ((sum + 1) * max)/ power
    sum = 2 * sum + QRandom.next_bits(1) # 0 or 1
    power *= 2
  end
end

这是对您的来源中比特的最有效使用。它总是与重试方案一样有效或更好。每次调用 QRandom.rand( max ) 时使用的预期位数是 1 + Math.log2( max ) - 也就是说，平均而言，这允许您绘制刚好超过代表您的范围所需的小数位数。

Answer 2

索要更多号码如何？使用那个 API 的 length 参数，你可以只要求额外的数字并对它们求和，这样你就可以得到你想要的更大的数字。

http://qrng.anu.edu.au/API/jsonI.php?type=uint16&length=2

您可以使用 inject 进行求和和模运算，以确保数字不大于您想要的。

json["data"].inject(:+) % MAX_NUMBER

我对您的代码做了一些其他更改，例如使用 SecureRandom 而不是常规的 Random。您可以在此处找到代码：

https://gist.github.com/matugm/bee45bfe637f0abf8f29#file-qrandom-rb

Answer 3

由于65535在二进制中是1111111111111111，所以你可以把随机数服务器当成随机位的来源。它以 16 位为单位向您提供位这一事实并不重要，因为您可以发出多个请求，也可以忽略响应中的某些位。

因此，在执行该抽象之后，我们现在拥有的是一项服务，可在您需要时为您提供随机位（0 或 1）。

算出你需要多少位随机性。由于你想要一个0到99999之间的数，你只需要找到一个全为1且大于或等于99999的二进制数。十进制99999等于二进制11000011010011111，它有17位长，所以你需要17一些随机性。

现在从服务中获取 17 位随机数并将它们 assemble 转换为二进制数。该数字将在 0 和 2**17-1 (131071) 之间，并且会均匀分布。如果随机数恰好大于 99999，则丢弃您拥有的位并重试。（需要重试的概率应该小于50%。）

最终你会得到一个 0 到 99999 之间的数字，这个算法应该给你一个完全均匀的分布。

基于 ANU 量子随机数服务器的随机数

Random Numbers based on the ANU Quantum Random Numbers Server

ruby

random