{"id":35799,"date":"2026-02-04T04:51:51","date_gmt":"2026-02-04T03:51:51","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=35799"},"modified":"2026-02-05T07:44:11","modified_gmt":"2026-02-05T06:44:11","slug":"logaritmo-discreto-e-dimostrazioni-a-conoscenza-zero","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2026\/02\/04\/logaritmo-discreto-e-dimostrazioni-a-conoscenza-zero\/","title":{"rendered":"Logaritmo discreto e dimostrazioni a conoscenza zero"},"content":{"rendered":"

Avevo parlato delle dimostrazioni a conoscenza zero una decina d’anni fa<\/a>, sul Post. Magari la prossima settimana ne scrivo ancora. Per il momento vi lascio una dimostrazione pratica: una dimostrazione si dice a conoscenza zero se io riesco a convincerti che conosco un segreto senza rivelartelo. Per esempio, potrei dirti che ho una tecnica infallibile per lanciare una moneta e farla cascare su testa o croce: tu mi dai una moneta, mi dici quale faccia vuoi che esca, e io ci riesco una, dieci, cento volte di fila. A un certo punto tu ti fiderai che io sono effettivamente in grado di decidere quale faccia mostrare (e ovviamente non giocherai pi\u00f9 a testa o croce con me), anche se non hai nessuna idea di come io faccia. La parola chiave \u00e8 “fidarsi”: le dimostrazioni a conoscenza zero sono inerentemente probabilistiche, proprio perch\u00e9 non possiamo controllare la dimostrazione. Quello che conta \u00e8 che la probabilit\u00e0 che io sia stato semplicemente fortunato sia piccola a piacere: con un solo lancio capiterebbe una volta su due, con dieci lanci una volta su 1000, con cento lanci la probabilit\u00e0 di essere stato fortunato sarebbe inconcepibilmente piccola. <\/p>\n

Passiamo ora al logaritmo discreto. Probabilmente vi ricordate che se avete l’equazione $b^x = y$ allora $b$ \u00e8 la radice x<\/i>-sima di $y$, mentre $x$ \u00e8 il logaritmo di $y$ in base $b$: a differenza di addizione e moltiplicazione, l’elevazione a potenza non \u00e8 commutativa e quindi ci sono due operazioni inverse. Quello che a scuola non insegnano \u00e8 che \u00e8 possibile anche calcolare il logaritmo in un gruppo finito, se la dimensione del gruppo \u00e8 un numero primo $p$ (insomma, se stiamo usando i numeri modulo $p$). Prendiamo per esempio $p = 7$: le potenze di 3 in base 7 sono le seguenti.<\/p>\n

$$\\begin{matrix}
\nn & 1 & 2 & 3 & 4 & 5 & 6 \\\\
\n3^n & 3 & 2 & 6 & 4 & 5 & 1 \\\\
\n\\end{matrix}$$<\/p>\n

Notate che non consideriamo lo 0, perch\u00e9 ci interessa il gruppo moltiplicativo e non quello additivo; notate anche come tutti i valori da 1 a 6 sono presenti nella riga delle potenze. Da qui \u00e8 facile ricavare il logaritmo discreto: <\/p>\n

$$\\begin{matrix}
\nn & 1 & 2 & 3 & 4 & 5 & 6 \\\\
\n\\log_3 n & 6 & 2 & 1 & 4 & 5 & 3 \\\\
\n\\end{matrix}$$<\/p>\n

In questo caso la tabella \u00e8 facile da calcolare, ma se partissimo da un numero primo di centinaia di cifre sarebbe ancora facile elevare un numero a una qualche potenza, ma non lo sarebbe affatto partire da quel risultato e risalire al numero. Il logaritmo discreto \u00e8 insomma una di quelle “funzioni a senso unico”<\/a> che servono per la crittografia. Come si pu\u00f2 sfruttare il logaritmo discreto per convincere il mio interlocutore che conosco $x$, il logaritmo in base $b$ di $y$, senza rivelarglielo? Ecco un protocollo di comunicazione, come spiegato da John Cook<\/a>. <\/p>\n

(1) Io scelgo un numero (naturale) casuale $r$, calcolo $t = b^r$, e mando al mio interlocutore il numero $t$.
\n(2) Lui mi spedisce a sua volta un altro numero casuale $c$.
\n(3) Io calcolo $s = r + cx$ e glielo mando.
\n(4) Lui verifica ce effettivamente $b^s = ty^c$. In caso affermativo si fida (oppure riprova pi\u00f9 volte, se pensa che io abbia avuto fortuna).<\/p>\n

Cosa conosce il mio interlocutore, oltre alla base $b$ e a $y$? Due numeri: $t$ e $s$. Il primo, $t$, \u00e8 l’esponenziale (in base $b$ di un numero casuale, e quindi \u00e8 anch’esso casuale: non d\u00e0 dunque nessuna informazione. Il secondo, $s$, di per s\u00e9 \u00e8 basato su $x$, ma per trovarlo bisognerebbe conoscere $r$ e per riuscirci dovrebbe essere in grado di calcolare rapidamente il logaritmo discreto, cosa che al momento non \u00e8 fattibile. Infine, abbiamo che $b^s = b^{r+cx} = b^r b^{cx} = t (b^x)^c = ty^c$. Inoltre, visto che io non potevo conoscere a priori $c$, non potevo fare il calcolo in anticipo. Anche questo punto \u00e8 importante, perch\u00e9 altrimenti potrei usare dei trucchi: tornando all’esempio del lancio di monete, non \u00e8 cos\u00ec difficile fare un video in cui io per dieci volte di fila lancio una moneta dicendo ciascuna volta cosa uscir\u00e0. Comincio a filmare finch\u00e9 non mi capita la successione di dieci risultati corretti, e taglio tutta la parte precedente del video… <\/p>\n","protected":false},"excerpt":{"rendered":"

Un protocollo per dimostrare che conosco qual \u00e8 il logaritmo discreto di un numero.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"federated","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1033,214],"tags":[],"class_list":["post-35799","post","type-post","status-publish","format-standard","hentry","category-matelight-2026","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-9jp","jetpack-related-posts":[{"id":37224,"url":"https:\/\/xmau.com\/notiziole\/2026\/05\/27\/dimostrazioni-a-conoscenza-zero-e-crittografia\/","url_meta":{"origin":35799,"position":0},"title":"Dimostrazioni a conoscenza zero e crittografia","author":".mau.","date":"2026-05-27","format":false,"excerpt":"In teoria non possono esistere dimostrazioni a conoscenza zero non interattive: in pratica, grazie a G\u00f6del, possiamo trovarle.","rel":"","context":"In "mate-light 2026"","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":35855,"url":"https:\/\/xmau.com\/notiziole\/2026\/02\/11\/un-racconto-sulle-dimostrazioni-a-conoscenza-zero\/","url_meta":{"origin":35799,"position":1},"title":"Un racconto sulle dimostrazioni a conoscenza zero","author":".mau.","date":"2026-02-11","format":false,"excerpt":"Una storiella che mi permette di spiegare meglio come funzionano.","rel":"","context":"In "mate-light 2026"","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2026\/02\/0know-a.drawio.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":36001,"url":"https:\/\/xmau.com\/notiziole\/2026\/02\/18\/ancora-sulle-dimostrazioni-a-conoscenza-zero\/","url_meta":{"origin":35799,"position":2},"title":"Ancora sulle dimostrazioni a conoscenza zero","author":".mau.","date":"2026-02-18","format":false,"excerpt":"Stavolta mostro una visione pi\u00f9 filosofica del protocollo","rel":"","context":"Con 3 commenti","block_context":{"text":"Con 3 commenti","link":"https:\/\/xmau.com\/notiziole\/2026\/02\/18\/ancora-sulle-dimostrazioni-a-conoscenza-zero\/#comments"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4023,"url":"https:\/\/xmau.com\/notiziole\/2006\/03\/22\/qed_fenomenologia_della_dimostrazione\/","url_meta":{"origin":35799,"position":3},"title":"QED – Fenomenologia della dimostrazione","author":".mau.","date":"2006-03-22","format":false,"excerpt":"Troppo tecnico, purtroppo.","rel":"","context":"Articolo simile","block_context":{"text":"Articolo simile","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":29434,"url":"https:\/\/xmau.com\/notiziole\/2024\/08\/07\/che-cosa-non-e-una-dimostrazione-elegante\/","url_meta":{"origin":35799,"position":4},"title":"Che cosa NON \u00c8 una dimostrazione elegante","author":".mau.","date":"2024-08-07","format":false,"excerpt":"Cominciamo dal fondo, insomma","rel":"","context":"In "mate-light-2024"","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"\"proof\"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/08\/%E2%80%94Pngtree%E2%80%94proof-text-effect-editable_6100719-300x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":20333,"url":"https:\/\/xmau.com\/notiziole\/2020\/05\/03\/quizzino-della-domenica-testa-o-croce-2\/","url_meta":{"origin":35799,"position":5},"title":"Quizzino della domenica: testa o croce","author":".mau.","date":"2020-05-03","format":false,"excerpt":"Ciao lettore! Visto che non abbiamo molto da fare, ti propongo un gioco. Ciascuno di noi prende dieci monete e le mette in una pila scegliendo come vuole la faccia in alto di ciascuna moneta e coprendo con un cartoncino la moneta in alto in modo che non si veda\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"una pila di monete","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2020\/04\/q445a.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/35799","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=35799"}],"version-history":[{"count":6,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/35799\/revisions"}],"predecessor-version":[{"id":35860,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/35799\/revisions\/35860"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=35799"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=35799"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=35799"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}