{"id":6737,"date":"2009-01-22T08:00:00","date_gmt":"2009-01-22T08:00:00","guid":{"rendered":"http:\/\/xmau.com\/wp\/notiziole\/2009\/01\/22\/aritmetica_modu_1\/"},"modified":"2009-01-22T08:00:00","modified_gmt":"2009-01-22T08:00:00","slug":"aritmetica_modu_1","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2009\/01\/22\/aritmetica_modu_1\/","title":{"rendered":"Aritmetica modulare \/ 2"},"content":{"rendered":"

(la prima parte si trova qua<\/a>)
\nMoltiplicazione, ma soprattutto divisione!<\/u>
\nUna tabellina per la somma \u00e8 una cosa strana, ma nessuno si scandalizza nel caso della moltiplicazione: in fin dei conti, la buona vecchia tavola pitagorica la conosciamo tutti. La tabella 2 mostra appunto la moltiplicazione, stavolta modulo 10 per semplicit\u00e0 pratica: \u00e8 come se guardassimo l’ultima cifra della tavola pitagorica standard. Alcune sue caratteristiche sono quelle a cui noi siamo abituati. La tabellina dello zero \u00e8 sempre monotona: zero per un qualsiasi numero fa zero. Anche la tabellina dell’uno non \u00e8 che sia poi cos\u00ec eccitante: uno per n<\/i> fa n<\/i> per ogni numero n<\/i>. Negli altri casi, le cose cambiano eccome.
\n\"[prodotto
\nTabella 2:<\/b> prodotto modulo 10
\nA volte succede che due numeri diversi da zero, moltiplicati tra di loro, diano zero: lo vediamo nelle tabelline dei numeri pari e in quella del 5. Altre volte succede che nella tabellina tutti i numeri diversi sono presenti; lo vediamo, oltre che nella tabellina dell’uno, anche in quella di 3, 7 e 9. I due casi sono complementari: non \u00e8 difficile dimostrare che o capita uno o l’altro, per\u00f2 sono buono e non lo faccio, visto che non \u00e8 cos\u00ec importante nella nostra discussione. Qui ci basta vedere che 4*2 e 4*7 valgono entrambi 8, il che significa che nell’aritmetica modulare la divisione pu\u00f2 avere pi\u00f9 di un risultato, oppure non averne nessuno. Nel primo caso, 8\/4 vale 2 oppure 7; nel secondo caso, 9\/4 \u00e8 impossibile, e non ce la facciamo nemmeno a pensare di estendere i numeri modulo 10 per avere un risultato fuori dall’insieme di partenza. Non abbiamo insomma l’equivalente dei numeri frazionari modulari, almeno cos\u00ec ad occhio.
\n\"[prodotto
\nTabella 3:<\/b> prodotto modulo 11
\nLa situazione per\u00f2 cambia di colpo se stiamo usando l’aritmetica modulare con un modulo che \u00e8 un numero primo. La tabella 3 mostra la tavola pitagorica per l’aritmetica modulo 11. In questo caso, a parte per lo zero, l’insieme dei multipli di ciascun numero \u00e8 composto da tutti i numeri! Quindi ogni numero diverso da zero ha un suo inverso, che moltiplicato per il numero dato ci fa ottenere 1. Per i numeri modulo 11, l’inverso di 1 \u00e8 1, quello di 2 \u00e8 6, quello di 3 \u00e8 4, quello di 5 \u00e8 9, quello di 7 \u00e8 8, quello di 10 \u00e8 10. Come per la differenza, in questo caso possiamo permetterci il lusso di non imparare le divisioni; basta avere la tabellina per gli inversi, e cos\u00ec 5\/8 (modulo 11) \u00e8 uguale a 5*7 che vale 35 cio\u00e8 2.
\n\"[opposti
\nListato 2:<\/b> inversi modulo 11
\nPotenze e logaritmi<\/u>
\nAccenno solamente a quello che succede nel caso dell’elevazione a potenza e del logaritmo, limitandomi al caso in cui il modulo sia un numero primo dove le propriet\u00e0 sono pi\u00f9 interessanti: per fissare le idee, immaginiamo di usare i numeri modulo 11.
\n\"[potenze
\nTabella 4:<\/b> potenze modulo 11
\nScrivere a<\/i>b<\/i><\/sup> significa moltiplicare a<\/i>*a<\/i>*a<\/i>… per b<\/i> volte, sempre eliminando tutti i multipli di 11 nelle operazioni. Come nel caso dei numeri interi, definiamo a<\/i>0<\/sup> = 1 e a<\/i>1<\/sup> = a<\/i>. La tabella 4 \u00e8 una “tavola potenziagorica”: visto che l’elevazione a potenza non \u00e8 commutativa e cio\u00e8 a<\/i>b<\/i><\/sup> non \u00e8 necessariamente uguale a b<\/i>a<\/i><\/sup>, preciso che la base si legge nella colonna a sinistra e l’esponente nella riga in alto. Notate nulla di strano? Dovrebbero esserci almeno due cose che saltano all’occhio. La prima \u00e8 che la colonna della potenza 10 \u00e8 composta da tutti 1; la seconda (in po’ pi\u00f9 difficile) \u00e8 che alcune colonne (in lilla) e alcune righe (in azzurro) contengono tutti i numeri da 1 a 10. La prima di queste propriet\u00e0 vale per l’aritmetica modulare quando il modulo \u00e8 un numero primo p<\/i>, ed \u00e8 nota come Piccolo teorema di Fermat<\/em> (no, non c’entra nulla con l’Ultimo teorema di Fermat se non che sono stati enunciati entrambi dal matematico e giudice francese). La seconda invece \u00e8 vera per le colonne quando stiamo lavorando con l’aritmetica modulo p<\/i> (primo) e prendiamo una potenza n<\/i> tale che n<\/i> e p-1<\/i> non abbiano fattori primi in comune; tecnicamente si dice che “n<\/i> \u00e8 primo con p-1<\/i>“. Per le righe, invece, i valori per cui vale la propriet\u00e0 si chiamano generatori<\/b> nella base p<\/i>.
\nPer quanto riguarda le colonne lilla, possiamo dire che in quei casi \u00e8 sempre possibile fare la radice n-sima di un numero, che ha sempre un solo valore (a meno di multipli del modulo). Non ditemi che \u00e8 lo stesso con le radici cubiche “normali”: anche lasciando perdere i valori complessi, ditemi voi qual \u00e8 la radice cubica di 9! Per quanto ne so, comunque, questa propriet\u00e0 non \u00e8 poi cos\u00ec importante in pratica, a differenza di quella sui generatori. Se si sceglie una base che \u00e8 un numero primo e un valore che \u00e8 un generatore per questa base, infatti, \u00e8 sempre possibile calcolarne il logaritmo discreto<\/a>, che poi non \u00e8 altro che il logaritmo in versione modulare. Se 26<\/sup> \u00e8 congruo a 9 (modulo 11) questo significa che il logaritmo discreto di 9 in base 2 e modulo 11 vale 6. (Vale anche 16, 26, 36 e cos\u00ec via… ma anche in questo caso si prende convenzionalmente il pi\u00f9 piccolo valore). La cosa interessante del logaritmo discreto \u00e8 che non ci sono modi “facili” per calcolarlo, se non andando avanti a elevare a potenza la base finch\u00e9 non si trova il valore di cui ci serve il logaritmo. L’unico problema \u00e8 che fare tutti questi conti costa, e il costo cresce esponenzialmente con la dimensione del modulo p<\/i>. Questo significa che per un modulo abbastanza grande (il generatore pu\u00f2 anche essere piccolo) abbiamo una “funzione trappola”, che \u00e8 facile da calcolare in un verso ma difficile da craccare nell’altro verso: situazione ideale per gli algoritmi a chiave pubblica, e infatti il protocollo Diffie-Hellman<\/a> sfrutta i logaritmi discreti come base di un algoritmo di crittografia… algoritmo che non vi spiego in questa sede perch\u00e9 questa \u00e8 matematica light.
\nQuesto \u00e8 tutto: come sempre domande e suggerimenti sono i benvenuti!<\/p>\n","protected":false},"excerpt":{"rendered":"

Finisce la breve rassegna sull’aritmetica modulare<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","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":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[214],"tags":[],"class_list":["post-6737","post","type-post","status-publish","format-standard","hentry","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-1KF","jetpack-related-posts":[{"id":7881,"url":"https:\/\/xmau.com\/notiziole\/2010\/05\/14\/tabelline\/","url_meta":{"origin":6737,"position":0},"title":"Tabelline","author":".mau.","date":"2010-05-14","format":false,"excerpt":"anche se in effetti le tabelline vanno solo fino al 10...","rel":"","context":"In "povera_matematica"","block_context":{"text":"povera_matematica","link":"https:\/\/xmau.com\/notiziole\/category\/povera_matematica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":19716,"url":"https:\/\/xmau.com\/notiziole\/2019\/12\/25\/i-biscotti-misura-e-le-tabelline\/","url_meta":{"origin":6737,"position":1},"title":"I biscotti Misura e le tabelline","author":".mau.","date":"2019-12-25","format":false,"excerpt":"Le moltiplicazioni, queste sconosciute","rel":"","context":"In "povera_matematica"","block_context":{"text":"povera_matematica","link":"https:\/\/xmau.com\/notiziole\/category\/povera_matematica\/"},"img":{"alt_text":"quanto fa 8 per 9?","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2019\/12\/misura-300x149.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":16769,"url":"https:\/\/xmau.com\/notiziole\/2018\/05\/27\/quizzino-della-domenica-tabellina-enigmatica\/","url_meta":{"origin":6737,"position":2},"title":"Quizzino della domenica: Tabellina… enigmatica","author":".mau.","date":"2018-05-27","format":false,"excerpt":"Nella tabellina qui sotto nessuna delle cifre presenti \u00e8 giusta, ma ogni cifra \u00e8 sempre stata sostituita con la stessa altra cifra: per esempio a 1 potrebbe corrispondere 7 mentre a 2 corrisponde 5. Sapete scrivere la tabellina corretta? (un aiutino lo trovate sul mio sito, alla pagina http:\/\/xmau.com\/quizzini\/p319.html; la\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"tabellina","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2018\/05\/q319a.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":30016,"url":"https:\/\/xmau.com\/notiziole\/2024\/11\/13\/il-13-e-proprio-una-brutta-bestia\/","url_meta":{"origin":6737,"position":3},"title":"Il 13 \u00e8 proprio una brutta bestia","author":".mau.","date":"2024-11-13","format":false,"excerpt":"La tabellina del 13 sia davvero perfida, almeno per fare uscire come iniziali tutte le cifre da 1 a 9.","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":"gif animata che mostra il comportamento di k(n), da https:\/\/aperiodical.com\/2018\/03\/exactly-how-bad-is-the-13-times-table\/","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/11\/a249067animated.gif?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/11\/a249067animated.gif?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/11\/a249067animated.gif?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/11\/a249067animated.gif?resize=700%2C400&ssl=1 2x"},"classes":[]},{"id":17862,"url":"https:\/\/xmau.com\/notiziole\/2018\/12\/24\/moltiplicazioni-complicate\/","url_meta":{"origin":6737,"position":4},"title":"Moltiplicazioni complicate","author":".mau.","date":"2018-12-24","format":false,"excerpt":"Sono conti davvero cos\u00ec difficili?","rel":"","context":"In "povera_matematica"","block_context":{"text":"povera_matematica","link":"https:\/\/xmau.com\/notiziole\/category\/povera_matematica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":6736,"url":"https:\/\/xmau.com\/notiziole\/2009\/01\/19\/aritmetica_modu\/","url_meta":{"origin":6737,"position":5},"title":"Aritmetica modulare \/ 1","author":".mau.","date":"2009-01-19","format":false,"excerpt":"Alcune nozioni sull'aritmetica modulare","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/6737","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=6737"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/6737\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=6737"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=6737"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=6737"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}