Puncte:1

Găsiți un prim $p$ vulnerabil la pohlig-Hellman

drapel kg

Trebuie să găsesc un număr prim $p$ cu următoarele constrângeri:

  • $p$ este cel puțin $1000$ biți lungi
  • $p-1$ este un număr neted cu cel mai mare factor de mai jos $1000$
  • orice factor de $p-1$ poate fi prezent de mai multe ori

Există acest număr? și dacă da, există un algoritm pentru a-l găsi?

fgrieu avatar
drapel ng
Bine ați venit la crypto-SE.Aceasta arată ca temele pentru acasă, așa că voi da doar un indiciu (puternic): propune un algoritm simplu care construiește $r$ însămânțat aleatoriu cu caracteristicile cerute pentru $p-1$ (inclusiv dimensiunea), ignorând deocamdată cerința ca $p$ este prim; apoi deduceți folosind [Teorema numărului prim](https://en.wikipedia.org/wiki/Prime_number_theorem) o limită inferioară plauzibilă pentru probabilitatea ca $p=r+1$ să fie prim, și din aceasta o limită superioară plauzibilă. a costului aşteptat al algoritmului probabilistic acum evident. Este inteligent să răspunzi la propria întrebare.

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.