Puncte:1

Recuperarea soluțiilor alternative la un logaritm discret care poate fi atacat folosind Pohlig-Hellman

drapel in

În procesul de studiu a logaritmilor discreti și a abordărilor care ar putea fi luate, am văzut algoritmul Pohlig-Hellman.

Mai târziu, când lucram cu $h = g^x \mod p$ Unde $p-1$ este neted, folosind Pohlig-Hellman nu a dat rezultatul așteptat și a returnat ceva mult mai mare decât se aștepta. Presupun că acest lucru se datorează faptului că Pohlig-Hellman omite ocazional cel mai mic răspuns.

Întrebări:

  1. Cum pot recupera cel mai mic posibil $x$ corect?
  2. Eu am cea mai mare $x$; ar putea fi folosit pentru a recupera un mai mic $x'$?
kelalaka avatar
drapel in
Ați văzut [Algoritmul PohligâHellman: algoritm general](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm#The_general_algorithm)
drapel in
@kelalaka Am citit asta. Arată ca modul general de utilizare a algoritmului. Totuși, nu văd cum asta permite soluții alternative. Îmi poți indica ceea ce ar trebui să mă uit?
meshcollider avatar
drapel gb
Cel mai mic ar fi $x \bmod{(p-1)}$ dacă $p$ este prim
drapel et
Toate soluțiile fac parte dintr-o clasă de echivalență dată de $\bmod (p-1)$. Deci $x' = x \bmod (p-1)$. Acestea fiind spuse, pasul final în algo-ul PH este combinarea soluțiilor în subgrupuri folosind teorema chineză a restului și soluția ar fi sub forma $x = ceva \bmod (p-1)$. Deci veți ajunge întotdeauna cu cea mai mică soluție. Ați putea enumera diferitele soluții de subgrup pe care le combinați cu CRT?
drapel in
@user93353 Am ajuns să rezolv din mesajul tău. Mulțumiri!

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.