The source code this blog mentioned is here: https://github.com/Anduin2017/SuperRandom

The traditional methods for obtaining `n` non-repeating random numbers are:

- The random number is generated by the linear congruence method, and each random number is generated and compared in the database. If it already exists, the number is discarded.
- Randomly generate a linear sequence, and then shuffle the sequence.

The time complexity of the above traditional method is `O (n ^ 2)`. Especially in the case of larger data, for the first algorithm: after the generation of a large number of numbers already exists, the performance will become slower and slower. For the second method, it will take up a very high memory space.

My solution is based on the RSA algorithm, whose time complexity is `O (n)` and space complexity is `O (1)`. It is only linearly related to the number of random numbers required and does not need to be compared with any data set. So the performance is fast. Especially when it is over one million, it is obviously superior to any random number algorithm that depends on storage.

```
N is a positive integer.
Let a positive integer A be distributed in the set [2, (N-1)]
C = (A ^ D) mod N
And meet the following conditions:
D is prime
N is the product of two prime numbers (P, Q)
P! = Q
(D * E) mod ((P-1) * (Q-1)) = 1
∵ C = (A ^ D) mod N
∴ A = (C ^ E) mod N
∴ C and A are one-to-one mapping
∵ A is distributed in the set [2, (N-1)]
∴ A does not repeat, no omission
∴ C does not repeat, no omission
```

First, we gonna build a simple prime detect method:

```
public bool IsPrime(int input)
{
var testSize = Math.Sqrt(input);
for (int i = 2; i <= testSize; i++)
{
if (input % i == 0)
return false;
}
return true;
}
```

And a method that returns a prime sequence:

```
public IEnumerable<int> PrimeNumbers()
{
yield return 2;
for (int i = 3; true; i += 2)
{
if (IsPrime(i))
{
yield return i;
}
}
}
```

A method to detect if the value of E is correct:

```
public bool IsValidE(int d, int e, int p, int q)
{
return (d * e) % ((p - 1) * (q - 1)) == 1;
}
```

So we can find a valid E from natural numbers:

```
public IEnumerable<int> GetNaturalNumbers()
{
for (int i = 0; true; i++)
{
yield return i;
}
}
public bool HaveValidE(int d, int p, int q, out int e)
{
foreach (var naturalNumber in GetNaturalNumbers())
{
if (naturalNumber > d * (p - 1) * (q - 1))
{
break;
}
if (IsValidE(d, naturalNumber, p, q))
{
e = naturalNumber;
return true;
}
}
e = 0;
return false;
}
```

Before we can get the E, we need p and q calculated.

P and Q are two primes in which multis values the input N. Just write a method to break N to P and Q.

```
public bool TryBreakNumber(int x, out int left, out int right)
{
if (IsPrime(x))
{
left = right = 0;
return false;
}
var testMax = Math.Sqrt(x);
foreach (var leftPrime in PrimeNumbers())
{
if (leftPrime > testMax) break;
var rightPrime = x / leftPrime;
if (leftPrime * rightPrime == x && IsPrime(rightPrime))
{
left = leftPrime;
right = rightPrime;
return true;
}
else continue;
}
left = right = 0;
return false;
}
```

And get valid D and E from Q and P.

```
public (int d, int e) GetDAndE(int p, int q)
{
foreach (int d in PrimeNumbers())
{
if (HaveValidE(d, p, q, out int e))
{
return (d, e);
}
}
throw new InvalidOperationException("WTF!");
}
```

Now that check if what we got from those methods is valid.

```
public bool TryGetRSAParameters(int n, out int p, out int q, out int d, out int e)
{
p = 0;
q = 0;
d = 0;
e = 0;
if (IsPrime(n))
{
return false;
}
if (!TryBreakNumber(n, out p, out q))
{
return false;
}
if (p == q)
{
return false;
}
(d, e) = GetDAndE(p, q);
return true;
}
```

That function returns true if it can get correct p, q, d, and e. And returns false when failed.

To get our final random sequence, just call I ^ d % N.

```
public static IEnumerable<int> GetRandomNumbersRaw(int n, int d)
{
for (int i = 2; i < n; i++)
{
var mod = BigInteger.ModPow(BigInteger.Pow(i, d), 1, n);
yield return (int)mod;
}
}
```

As I mentioned, the input N might not be valid. We need to skip all invalid inputs and find the nearest N around it.

```
public IEnumerable<int> GetRandomNumbers(int max)
{
int n, d;
for (n = max + 2; !TryGetRSAParameters(n, out int p, out int q, out d, out int e); n++)
{
}
return GetRandomNumbersRaw(n, d)
.Select(t => t - 2)
.Where(t => t < max);
}
```

Now everything is done. This method returns all valid random numbers.

Test it in your Main method.

```
static void Main(string[] args)
{
while (true)
{
Console.WriteLine("How many unique random numbers do you want?");
if (!int.TryParse(Console.ReadLine(), out int counts))
{
break;
}
var array = new int[counts];
foreach (var rand in new Randomizer().GetRandomNumbers(counts))
{
Console.WriteLine("Got random number: " + rand);
array[rand] += 1;
}
foreach (var bit in array)
{
if (bit > 1)
{
Console.WriteLine("Bit set twice! Wrong code!");
}
if (bit < 1)
{
Console.WriteLine("Bit not set! Wrong code!");
}
}
}
}
```

Outputs demo:

Very random, and unique. Cool!

Edi WangThis is so halal

GPT-4In this blog post, the author presents a method to generate unique random numbers in C# using RSA encryption algorithm. The core idea is to utilize prime numbers and RSA parameters (p, q, d, and e) to create a random sequence that is both unique and non-repeating.

The author provides a step-by-step guide to implement this method, starting with simple prime detection and generating prime sequences. Then, they demonstrate how to validate the value of E, calculate P and Q, and find valid D and E from P and Q. Finally, the author shares a method to get the random sequence and handle invalid input values.

One of the strengths of this blog post is the clear and detailed explanation of each step, making it easy for readers to follow and understand the logic behind the method. The author also provides code snippets for each step, which can be helpful for readers who want to implement this method in their own projects.

However, there are a few areas where the blog post could be improved. First, it would be helpful to provide some context and background on the RSA encryption algorithm, as some readers may not be familiar with it. Additionally, the author could explain the reasoning behind choosing this specific method for generating unique random numbers, compared to other approaches.

Second, the code snippets provided could benefit from some additional comments to help readers understand the purpose of each line of code. This would make it easier for readers to follow the logic and adapt the code to their own needs.

Lastly, the author could provide some performance analysis and discuss the efficiency of this method compared to other random number generation techniques. This would give readers a better understanding of the trade-offs involved and help them decide if this approach is suitable for their specific use case.

Overall, this blog post presents an interesting and unique method for generating random numbers in C#. With some additional context, explanations, and performance analysis, it could become an even more valuable resource for developers looking to implement unique random number generation in their projects.