• Example : all Gaussian primes with norm less than 50 are

  (1, 0), (3, 0), (2, 1), (7, 0), (11, 0), (3, 2), (1, 4), (19, 0), (23, 0), (2, 5), (31, 0), (1, 6), (4, 5), (43, 0), (47, 0)
  

  2 + i, 2 - i, 1 - 2i... satisfy conditions, but choose only one of them.

  It should be

  (1, 1), (1, 2), (2, 1), (3, 0), (2, 3), (3, 2), (1, 4), (4, 1), (2, 5), (5, 2), (1, 6), (6, 1), (4, 5), (5, 4), (7, 0)
  

• When two different Gaussian primes have the same norm, you should specify how to sort them.

The description is still pretty disorienting about safe primes:

Prime number p is called Sophie Germain's prime if associated with it number 2p + 1 (called safe prime) is also prime.

For given p, your task is to find the smallest primitive root modulo p.

If given modulus is not safe prime, return -1.

Since the valid input we need to handle are safe primes, the description of what a safe prime is should have safe prime as the subject/topic of the sentence, not the other way around (we don't need to know what Sophie Germain primes are anyway for the purpose of the kata, so including it is just noise). For example, this page from top Google search results describes safe prime as this:

Safe primes: A safe prime is a prime number of the form 2p + 1, where p is also a prime.

Your task is to find the smallest primitive root modulo n.

Given n, presumably? The task might be stated more clearly as a function ( signature ).

Reference solution is probabilistic, but the false negative rate is unacceptable. Under the current setup, when tested against 5000-10000 fibonacci numbers, the reference solution fails most of the time. It's even failing the unmodified tests some of the times.

Randoms tests are sometimes passing in negative values. This is not expected (nor are we told how to handle them. It seems that they all expect false)

Tests are still too weak. I don't know if it is possible to invalidate solutions like this one.

The C# ref sol is invalidated (wrong class name). You should fix it.