Parametry w generatorze Lehmera

[Borneq]

W angielskiej Wikipedii mamy

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Lehmer_random_number_generator

Co oznacza:

g is an element of high multiplicative order modulo n

?

[Mruczek]

Liczba \(\displaystyle{ g}\) ma wysoki rząd modulo \(\displaystyle{ n}\), czyli \(\displaystyle{ g}\) jest taką liczbą, że dopiero dla dużego całkowitego dodatniego \(\displaystyle{ k}\) zachodzi \(\displaystyle{ g^{k} \equiv 1 \pmod{n}}\) (z czego wynika, że \(\displaystyle{ NWD\left( g, n\right)=1}\)).

[Borneq]

A jak to się ma do tego że \(\displaystyle{ g}\) jest pierwiastkiem pierwotnym modulo \(\displaystyle{ n}\)? Pierwiastek to szczególny przypadek powyższego?

[Mruczek]

Tak, bo potęgi pierwiastka są wszystkimi resztami względnie pierwszymi z \(\displaystyle{ n}\), w szczególności pewną z tych reszt jest \(\displaystyle{ 1}\). Ponadto pierwiastek ma maksymalny możliwy rząd, bo w \(\displaystyle{ g^{k} \equiv a \pmod{n}}\) gdzie \(\displaystyle{ NWD\left( g, n \right) = 1}\) zachodzi \(\displaystyle{ NWD\left( a, n\right)=1}\), więc kolejne reszty które daje pierwiastek są wszystkimi możliwymi resztami.

[Borneq]

Chcę zrozumieć na przykładzie, dla modulusa 7:

1: 1
2: 2 4 1
3: 3 2 6 4 5 1
4: 4 2 1
5: 5 4 6 2 3 1
6: 6 1

3 i 5 mają pełną długość =6 aż do jedynki, więc 3 i 5 są pierwiastkami. A które poza tym spełniają ten słabszy warunek?

Dla modulusa (czy jak to się nazywa? ) 17:

1: 1
2: 2 4 8 16 15 13 9 1
3: 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 1
4: 4 16 13 1
5: 5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1
6: 6 2 12 4 7 8 14 16 11 15 5 13 10 9 3 1
7: 7 15 3 4 11 9 12 16 10 2 14 13 6 8 5 1
8: 8 13 2 16 9 4 15 1
9: 9 13 15 16 8 4 2 1
10: 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 1
11: 11 2 5 4 10 8 3 16 6 15 12 13 7 9 14 1
12: 12 8 11 13 3 2 7 16 5 9 6 4 14 15 10 1
13: 13 16 4 1
14: 14 9 7 13 12 15 6 16 3 8 10 4 5 2 11 1
15: 15 4 9 16 2 13 8 1
16: 16 1

A które poza tym spełniają ten słabszy warunek?

Natomiast nie dla liczby pierwszej ale kwadratu liczby pierwszej jest zupełnie inaczej: dla modulusa (jak to się nazywa?) = 9, czy liczba 3 jest pierwiastkiem pierwotnym? bo utyka na zerze, podczas gdy dla liczby pierwszej nie musieliśmy się zerem przejmować.

2.
Ja używam kodu :

Kod: Zaznacz cały

int modulus = 9;

int main()
{
	for (int candidate = 1; candidate < modulus; candidate++)
	{
		int rest = 1;
		printf("%d: ", candidate);
		do
		{
			rest = (rest*candidate) % modulus;
			printf("%d ",rest);
		} while (rest != 1);
		printf("
");
	}
    return 0;
}

Ale czy jest szybszy sposób na obliczenie dla wartości rzędu \(\displaystyle{ 2^{32}}\) ?

[Mruczek]

To nie jest żaden modulus tylko modulo
Pojęcie dużego rzędu jest względne.

Dla modulo \(\displaystyle{ 9}\), liczba \(\displaystyle{ 3}\) nie jest pierwiastkiem pierwotnym, bo przecież warunek mówi, że musi być \(\displaystyle{ NWD\left( g,n\right) =1}\), a tutaj \(\displaystyle{ NWD(3, 9) = 3}\).

Potęgę modulo można policzyć tzw. szybkim potęgowaniem modularnym, albo rekurencyjnie, w czasie logarytmicznym ze względu na wykładnik.

Wersja rekurencyjna:

Kod: Zaznacz cały

const int MOD = 1e9;

// Podnosi n do potęgi pot w czasie O(log pot). Wynik jest modulo MOD.
long long potega(int n, int pot) {
	if (pot == 0)
		return 1;
	long long wynik = 1;
	if (pot % 2 == 1)
		wynik = (wynik * n) % MOD;
	long long pom = potega(n, pot / 2);
	return (((wynik * pom) % MOD) * pom) % MOD;	
}

[Borneq]

Liczba \(\displaystyle{ g}\) ma wysoki rząd modulo \(\displaystyle{ n}\), czyli \(\displaystyle{ g}\) jest taką liczbą, że dopiero dla dużego całkowitego dodatniego \(\displaystyle{ k}\) zachodzi \(\displaystyle{ g^{k} \equiv 1 \pmod{n}}\) (z czego wynika, że \(\displaystyle{ NWD\left( g, n\right)=1}\)).

Ja tak to rozumiem: ma wysoki rząd modulo wtedy gdy dla dużego k zachodzi, a pierwiastek pierwotny wtedy gdy dla maksymalnego k zachodzi, więc skoro jest pierwiastkiem to na pewno ma wysoki rząd modulo. Nie wiem dlaczego takie nieostre kryterium przyjęto w generatorze Lehmera zamiast bycia pierwiastkiem pierwotnym (jeśli to prawda co piszą w Wiki angielskiej)