How do we unit-test functions which use randomness?

I am interested in best-practice techniques, if any, for unit-testing functions which use randomness. To be clear, I am not concerned with testing the distribution of random number generators.

As a toy example, let's consider this function:

// Returns a random element from @array. @array may not be empty.
int GetRandomElement(int[] array);

Answers to this question suggest that we may inject a mock source of randomness, which makes sense. But I'm not sure exactly how I might use the mock. For example, let's assume that we have this interface:

// A mock-friendly source of randomness.
interface RandomnessSource {
  // Returns a random int between @min (inclusive) and @max (exclusive).
  int RandomInt(int min, int max);
}

...And change the signature of GetRandomElement() to this:

// Returns a random element from @array, chosen with @randomness_source.
// @array may not be empty.
int GetRandomElement(int[] array, RandomnessSource randomness_source);

All right, now a test could look like:

MockRandomnessSource mock = new MockRandomnessSource();
mock.ExpectCall(RandomnessSource::RandomInt(0, 5)).Return(2);
AssertEquals(GetRandomElement({0, 10, 20, 30, 40}, mock), 20);

...which could work fine, but only if the implementation looks like this:

// A fairly intuitive implementation.
int GetRandomElement(int[] array, RandomnessSource randomness_source) {
  // Pick a random number between [0..n), where @n is the @array's legnth.
  return array.Get(randomness_source.RandomInt(0, array.Length()));
}

...But nothing in the function specification prevents an implementation like this:

// Less intuitive, but still a conforming implementation.
int GetRandomElement(int[] array, RandomnessSource randomness_source) {
  // Pick a random number between [1..n+1), only to subtract 1 from it.
  return array.Get(randomness_source.RandomInt(1, array.Length() + 1) - 1);
}

One idea which leaps to mind is that we may further constrain the function's contract, like this:

// Returns a random element from @array, chosen with @randomness_source by
// by calling @RandomnessSource::RandomInt to pick a random index between
// 0 and the length of @array.
int GetRandomElement(int[] array, RandomnessSource randomness_source);

...But I can't quite get over the impression that this is placing too heavy a constraint on the function contract.

I also suspect that there might be better ways to define the interface RandomnessSource to make its callers more amenable to unit tests, but I'm not quite sure what/how.

...Which brings me to the question: What are the best-practice techniques (if any) for unit-testing functions which use randomness?