Получение уникальных случайных чисел
Формулировка теоремы:
Если p — простое число, a — целое число, не делящееся на p, то a^(p — 1) = 1 (mod p).
Каждое из p — 1 чисел a, 2a, . . ., (p-1)a даёт при делении на p ненулевой остаток:
a = k_1*p + r1, 2a = k_2*p + r2, . . . . . . . . . . . . . . . (p — 1)a = k_{p-1}*p + r_{p — 1}
Если число различных встречающихся здесь остатков меньше p — 1, то среди них найдутся по крайней мере два одинаковых. Но это невозможно, так как при r_n = r_m число (n-m)a = (k_n-k_m)p делится на p, что противоречиво, ибо |n-m| < p и a взаимно просто с p. Значит, все остатки r_1, . . . , r_{p — 1} между собой различны и образуют перестановку чисел 1, 2, . . . , p — 1. Перемножая все предыдущие равенства, получаем
(p-1)! * a^(p — 1) = N·p + r_1*r_2*...*r_{p — 1} = N*p + (p-1)!,
где N — некоторое целое число. Следовательно, (p-1)! * [a^(p-1) — 1] делится на p, а тогда и a^(p — 1) — 1 делится на p, поскольку (p-1)! не кратно p. Теорема доказана.
Таким образом, все-таки можно реализовать простой алгоритм генерации кодов не запоминая списка предыдущих кодов, а помня только номер последнего сгенеренного кода.
Вот тогда будет работающий алгоритм:
• берем большое десятизначное простое число. на наше счастье это будет 9999999997.
• берем любое число < 9999999997. К примеру 5678901234 — тоже десятизначное, чтобы в примере получить сразу приличные коды.
• начинаем генерацию:
1: 1 * 5678901234 = 5678901234 mod 9999999997
2: 2 * 5678901234 = 1357802471 mod 9999999997
3: 3 * 5678901234 = 7036703705 mod 9999999997
4: 4 * 5678901234 = 2715604942 mod 9999999997
5: 5 * 5678901234 = 8394506176 mod 9999999997
6: 6 * 5678901234 = 4073407413 mod 9999999997
7: 7 * 5678901234 = 9752308647 mod 9999999997
8: 8 * 5678901234 = 5431209884 mod 9999999997
9: 9 * 5678901234 = 1110111121 mod 9999999997
10: 10 * 5678901234 = 6789012355 mod 9999999997
11: 11 * 5678901234 = 2467913592 mod 9999999997
12: 12 * 5678901234 = 8146814826 mod 9999999997
13: 13 * 5678901234 = 3825716063 mod 9999999997
14: 14 * 5678901234 = 9504617297 mod 9999999997
...
Итак, будут получаться большие числа. Последнее сгенеренное большое число будет равно (p-1)*a = (9999999997 — 1) * 5678901234 = 56789012317284395064 — 20 цифр, что влезает в UInt64.
Ничего не надо помнить, ничего не надо искать. И главное — есть гарантия от ошибки, поскольку уникальность строго доказана.
Конечно, у этого алгоритма есть недостаток — при помощи него никогда не будут получены коды 0000000000, 9999999997, 9999999998 и 9999999999.