[szpkmsil] random rational

suppose you want a random positive rational number 0 < N/D < 1 with D less than some bound DMAX.  sample (D,N) uniformly within the triangle of permitted pairs.  reject and resample (D,N) if gcd(N,D) != 1.

the above random sampling procedure uses rejection sampling to avoid how tricky it would be to sample D by itself first.  between a prime D and a smooth D both about the same size, the prime offers many more coprime possibilities of N so would need to be sampled more frequently.

what should DMAX the bound of D be to have at least E possible distinct answers (E for "entropy") of N/D?  for large D, the probability that gcd(N,D) == 1 is 6/pi^2 ~= 0.6079 (Basel problem).  there are D*(D-1)/2 possible choices of fraction before rejection, so solve the resulting quadratic equation, yielding

DMAX = (-b + sqrt(b^2-4*a*c))/(2*a)

where a = 1 , b = -1 , c = -E*(pi^2/3) .

for E = 2^256, DMAX ~= 617203940781313027888293782794925861324.1 ~= 1.8138 * 2^128 ~= (pi/sqrt(3)) * 2^128.  two random rationals with D < DMAX will be cryptographically unlikely to collide: probability approximately 2^-128 by the birthday paradox.

previously on why we want a random rational.