Witam,
nie wiem jak ugryźć temat - szukam informacji (szczególnie rozwiązań w c#), ale nic konkretnego nie znajduję.
Otóż mam dużą liczbę pierwszą p (160 bitową) i chcę znaleźć jej generator (jak najmniejszy).
Za każdą pomoc wielkie dzięki :)
0
0
słyszałem o generatorach dużych losowych liczb pierwszych,
ale o najmniejszym generatorze konkretnej liczby pierwszej pierwsze słyszę i nawet nie jestem w stanie domyśleć się co to znaczy!
2
Faktycznie, zdecydowanie nieprecyzyjne pytanie/temat.
Wnioskując po temacie Generator Grupy:
Strzelam że chcesz znaleźć najmniejszą liczbę będącą generatorem grupy liczb modulo n (tzn. liczb całkowitych modulo n), jako że to pierwsza grupa przychodząca mi na myśl w połączeniu ze słowami 'generator' i 'liczby pierwsze'. Ciekawe czy trafiłem dobrze...
Jeśli tak, pytanie jest dość trywialne bo najmniejszym generatorem dowolnej takiej grupy jest <1>.
Co więcej i co ciekawsze - każda inna liczba < n w grupie modulo n gdzie n jest liczbą pierwszą jest generatorem.
Wynika to z tego że liczba d jest generatorem grupy modulo n wtedy i tylko wtedy kiedy d jest względnie pierwsze z n - a że n jest liczbą pierwszą...
A jeśli pominiesz i warunek że n jest liczbą pierwszą i założysz że n > 1, generatorem jest najmniejsza liczba będąca względnie pierwszą z n.
--edit--
Hmm, przypomniałem sobie o jednym - założyłem że chodzi o grupę addytywną (czyli tam gdzie dodajemy elementy).
W grupie multyplikatywnej (czyli mnożymy) jest trochę trudniej, ale również jeśli n jest liczbą pierwszą możemy być pewni że generator istnieje.
No więc d jest generatorem grupy modulo n wtedy i tylko wtedy, gdy liczba d jest pierwiastkiem pierwotnym liczby n (czyli że potęgi p generują wszystkie możliwe reszty modulo n).
Z tego co wiem nie ma jakiegoś ogólnego, prostego algorytmu na wyszukiwanie pierwiastków pierwotnych, ale da się to mimo to jakoś sensownie zrobić.
W skrócie - zaczynasz od d = 2, idziesz w górę i sprawdzasz d^( (n-1) / p) mod n dla każdego p znajdującego się w rozkładzie na czynniki pierwsze liczby n - 1. Jeśli nie wyjdzie ci 1 dla żadnego p, to znaczy że d jest pierwiastkiem pierwotnym.
Czytelniejszy i pełniejszy opis na przykład tutaj - http://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number
--koniec edita--
Jeśli nie trafiłem, sprecyzuj pytanie może.