Efektywne liczenie rzędu m modulo M / Okres generatora MWC

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
piotrek86
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 14 paź 2007, o 13:45
Płeć: Mężczyzna
Lokalizacja: Gdynia

Efektywne liczenie rzędu m modulo M / Okres generatora MWC

Post autor: piotrek86 » 14 paź 2007, o 13:46

Witam,

Chciałbym dla danego m (2 ^ 32 i 2 ^ 10) znaleźć takie a, dla którego okres generatora MWC będzie maksymalny.
Generator MWC:
X(n) = a * X(n-1) + c(n-1) (mod m)
c(n) = ZAOKR.DÓŁ(a * X(n-1) + c(n-1) / m)

Nie mogę znaleźć już obliczonych wartości a, dla których okres ten będzie maksymalny, toteż sięgnąłem do teorii, jak osiągnąć maksymalny okres:

Należy dobrać a, tak by M = a * m - 1 było liczbą pierwszą. Ten podpunkt jest prosty, mogą ściągnąć z internetu listę dużych liczb pierwszych i sprawdzać wszystkie po kolei.

Aczkolwiek gdy uzyskamy powyżej liczbę pierwszą, to okresem generatora dla takich parametrów jest najmniejsza liczba k, taka, że m ^ k =(przystaje) 1 (mod M)

Czyli szukamy RZĘDU m MODULO M. Wie ktoś może jak efektywnie można to obliczyć?

ODPOWIEDZ