Nu cred că acesta este locul unde să dau un tutorial despre teoria elementară a numerelor, așa că voi aborda doar aspectele care se referă imediat la întrebarea ta.
Când luăm un prim $p$ si o valoare $g$ (care nu este un multiplu al $p$), atunci dacă luăm în considerare șirul de valori $g^0 \bmod p, g^1 \bmod p, g^2 \bmod p, ...$, apoi aflăm că la un moment dat, secvența se va întoarce la 1 și, după aceea, începe de la capăt. Numim ordinea de $g$ numărul de valori prin care trecem înainte de a atinge 1, adică $g^q \bmod p = 1$, și aceasta este cea mai mică valoare a $q > 0$ care satisface acest lucru.
Deci, când Smart spune asta $g$ și $h$ au aceeași ordine primară, el spune asta $g^q \bmod p = 1$, $h^q \bmod p = 1$ și $q$ este prim (și în ambele cazuri, nu există o valoare mai mică a $q$).
Cum găsești un astfel de $g, h, q$? De fapt, se dovedește a nu fi atât de dificil; $q$ se va împărți întotdeauna $p-1$ uniform; putem alege un prim $p$ pentru a face găsirea unei astfel de valori primare $q$ uşor. În plus, dacă $q$ este un astfel de prim, atunci pentru orice valoare $u$ fără $p$ ca factor, valoarea $j = u^{(p-1)/q} \bmod p$ va fi fie 1, fie are comandă $q$; deci găsirea valorilor $g, h$ este usor.
Ai cerut un exemplu, îți dau unul de jucărie - vom alege $p=23$ și $q=11$ (Rețineți că $11$ desparte $23-1$ uniform), și $g=4$ și $h=9$ (este usor de verificat ca ambele au ordinea 11). Alegem și o valoare secretă $x$ (vom alege 6) și publică $y_1 = g^x \bmod p = 4^6 \bmod 23 = 2$ și $y_2 = h^x \bmod p = 9^6 \bmod 23 = 3$
Apoi, probatorul alege o aleatorie $k$, vom selecta în mod arbitrar $k=7$
Apoi, dovatorul calculează $r_1 = g^k \bmod p = 4^7 \bmod 23 = 8$ și $r_2 = h^k \bmod p = 9^7 \bmod 23 = 4$, și le transmite. Rețineți că am făcut aceste calcule modulo $p$ - care era implicit în protocol ( astfel de operații cu modul sunt înțelese în mod obișnuit).
Acum, contestatorul alege o valoare $c$; vom alege $4$; și trimite asta.
Apoi, dovatorul calculează $s = (k - c \cdot x) \bmod q = (7 - 4 * 6) \bmod 11 = 5$ (notă: la matematică, $x \bmod q$ operația returnează întotdeauna valoarea între $0$ și $q-1$ astfel încât $x - (x \bmod q)$ este un multiplu al $q$ - multe limbaje de computer nu urmează asta - acele limbi sunt greșite) și trimite asta.
Verificatorul verifică apoi asta $r_1 = 8$ este la fel ca $g^s \cdot y_1^c \bmod p = 4^5 \cdot 2^4 \bmod 23 = 8$ și $r_2 = 4$ este la fel ca $h^s \cdot y_2^c \bmod p = 9^5 \cdot 3^4 \bmod 23 = 4$; ambele verificați, și așa trece.
Faceți la fel, doar cu valori care au o lungime de sute de cifre, nu exemplul de jucărie pe care l-am dat.
