Wikipedia

Redukcja Pohliga-Hellmana: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m drobne redakcyjne
B11Blanco (dyskusja | edycje)
141 edycji
m drobne merytoryczne
Linia 26:
Które następnie możemy rozwiązać przy pomocy [[chińskie twierdzenie o resztach|chińskiego twierdzenia o resztach]].
 
'''KROK 2''': Jeżeli w rozkładzie p-1 występuje jakaś duża liczbapotęga pierwszaliczby pierwszej ''q''<sup>'''''α'''''</sup>, redukujemy DLP w grupie rzędu ''pq''<sup>'''''α'''''</sup> do kilku problemów w grupach rzędu ''pq'':
 
Przyjmijmy ''q := p<sub>''i''</sub>'' i
Załóżmy, że ''p''<sub>''i''</sub> jest dużą liczbą pierwszą, dla której '''''α''' > 1'' oraz przyjmijmy ''q := p''<sub>''i''</sub> oraz
: <math>
(a:=g^{r_i})^x \equivpmod h^{r_i}p
</math>
oraz
jako:
: <math>
ab:=h^x{r_i} \equivpmod bp
</math>
wówczas:
Źródło: „https://pl.wikipedia.org/wiki/Redukcja_Pohliga-Hellmana”