Efektywne liczenie rzędu m modulo M / Okres generatora MWC
: 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ć?
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ć?