Cutolo Piano Lauree Scientifiche

$ \let\vuoto\varnothing \let\setminus\smallsetminus \let\iso\simeq \let\n\triangleleft \let\implica\Rightarrow \let\Implica\Longrightarrow \let\shiff\Leftrightarrow \let\immersione\hookrightarrow \let\epi\twoheadrightarrow \let\mono\rightarrowtail \let\ot\otimes \newcommand\set[1]{\{#1\}} \newcommand\P{{\mathscr P}} \newcommand\U{{\mathscr U}} \newcommand\I{{\mathcal I}} \newcommand\F{{\mathcal F}} % \newcommand\Pf{{\P_{\mbox{\small\textbf {fin}}}}} \newcommand\Pf{{\P_{\text{fin}}}} \newcommand\N{\mathbb N} \newcommand\Z{\mathbb Z} \newcommand\Q{\mathbb Q} \newcommand\R{\mathbb R} \newcommand\C{\mathbb C} \newcommand\S{\mathbb S} \newcommand\Pr{\mathbb P} \newcommand\ds{\mathbin{\scriptstyle\triangle}} \newcommand\xor{\mathbin{\mathsf{XOR}}} \newcommand\nor{\mathbin{\mathsf{NOR}}} \newcommand\nand{\mathbin{\mathsf{NAND}}} \newcommand\gen[1]{\langle#1\rangle} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\rest}{rest} \DeclareMathOperator{\Sym}{Sym} \DeclareMathOperator{\Div}{Div} \DeclareMathOperator{\Corr}{Corr} \DeclareMathOperator{\Rel}{Rel} \DeclareMathOperator{\Map}{Map} \DeclareMathOperator{\Eq}{Eq} \DeclareMathOperator{\Part}{Part} \DeclareMathOperator{\partz}{Partz} \DeclareMathOperator{\OS}{OS} \DeclareMathOperator{\OL}{OL} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\jac}{Jac} \DeclareMathOperator{\nrad}{NilRad} \DeclareMathOperator{\ann}{Ann} \DeclareMathOperator{\ass}{Ass} \DeclareMathOperator{\Min}{Min} \DeclareMathOperator{\minor}{Minor} \DeclareMathOperator{\maggior}{Maggior} \DeclareMathOperator{\var}{Var} \DeclareMathOperator{\spec}{Spec} \DeclareMathOperator{\car}{char} \DeclareMathOperator{\cd}{cd} \newcommand\Mod{{\mathcal{Mod}}} % \DeclareRobustCommand {\modbin}{\mathbin{\textrm {mod}}} \newcommand\modbin {\mathbin{\textrm {mod}}} \newcommand\antivec[2] {#1^{\raise #2pt\hbox{$\!\!\scriptstyle\leftarrow\!\!$}}} \newcommand\antivecf{\antivec f3} \newcommand\antivecv{v^{\raise 1.2pt\hbox{$\!\!\!\scriptstyle\leftarrow\!\!$}}} \newcommand\antivecg{g^{\raise 2pt\hbox{$\!\!\!\scriptstyle\leftarrow\!\!$}}} \newcommand\vecvuoto {\vec{\phantom{p}}} \newcommand\antivecvuoto{\,\antivec {{}}{2}} % \newcommand\antivecvuoto{{}^{\raise 2pt\hbox{$\scriptstyle\leftarrow\!\!$}}} \newcommand\maxid{\mathbin{{\n}{\cdot}}} \let\sseq\subseteq $

PLS 2018

Nei primi incontri (5 e 14 febbraio) abbiamo parlato di aritmetica modulare, con un approccio piuttosto informale, e di alcune applicazioni: criteri elementari di divisibilità e cosiddetta 'prova del 9', secondo le linee dell'articolo Una introduzione all'aritmetica modulare, scritto proprio per il Piano Lauree Scientifiche.

Ho proposto alcuni piccoli esercizi di calcolo in aritmetica modulare, in particolare calcolo di potenze:

  • Calcolare il resto del numero intero $a$ nella divisione per $b$ in ciascuno di questi casi:
    • $a=918273655555$ e $b=9$;
    • $a=918273655555$ e $b=3$;
    • $a=2^{918273655555}$ e $b=7$;
    • $a=-100000000$ e $b=9$;
    • $a=\big((6758+296753)\cdot 86543\big)^2$ e $b=9$;
    • $a=184589763$ e $b=11$;
    • $a=3501472$ e $b=7$;
    • Oggi è mercoledì; che giorno (della settimana) era $2^7+6^7+2^{472}\cdot 5^{472}$ giorni fa?
    • Descrivere le ``potenze di 2 modulo 6''. In altri termini: calcolare il resto di $2^n$ nella divisione per 6, per un arbitrario intero positivo $n$.
    • Supponiamo che siano le 15:30. Che ora sarà tra $711\cdot 56744546476^3\cdot(48^{153}+19^{1100})+ 3^{33333}5^{101}+7^{2017}$ ore?
    • Elencare i numeri primi che, scritti in base 10 (cioè come siamo abituati a fare) abbiano esattamente sei cifre e siano palindromi (cioè della forma "$abccba$" per opportune cifre $a$, $b$, $c$, con $a\ne 0$).
    • Alcune delle domande precedenti sono un po' stupide. Quali, e perché?

Gli esercizi in A sono stati risolti e discussi in aula; quelli in B sono 'compiti a casa'; ne parleremo al prossimo incontro.

Altri esercizi del genere sono nelle pagine sulle attività PLS degli scorsi anni, in particolare qui.

Abbiamo iniziato, nel secondo incontro, a parlare di crittografia (classica) e dell'inadeguatezza dei cifrari per sostituzione monoalfabetica, come quello di Cesare. Parlandone, abbiamo utilizzato la Tabula Recta per l'alfabeto inglese.

Ci si può divertire a completare la decifrazione di questo crittogramma prodotto con la crittografia di Cesare; abbiamo visto in aula come procedere.

Volendo, ci si può anche cimentare con altri brevi crittogrammi di Cesare o, per divertirsi ancora di più, con due crittogrammi cifrati per sostituzione monoalfabetica utilizzando permutazioni casuali: quello mostrato in aula ed un altro, analogo. Entrambe le pagine contengono, oltre al crittogramma, una tabella delle frequenze percentuali (approssimate e, soprattutto, solo indicative) delle lettere dell'alfabeto italiano in un testo standard ed una tabella che riporta il numero di occorrenze e la frequenza percentuale di ogni lettera che appare nel crittogramma. Tra il crittogramma e le tabelle delle frequenze si trova un form che (in modo, spero, sufficientemente intuituivo; le istruzioni per l'uso sono comunque state date in aula) permette la sostituzione rapida di lettere nel crittogramma.

Nel terzo incontro (21 febbraio), dopo aver parlato di alcuni degli esercizi che avevo proposto, abbiamo parlato in termini generali dei metodi (e delle difficoltà) della crittografia classica. Ci siamo serviti della prima parte di una presentazione sulla quale torneremo.

Abbiamo accennato, tra l'altro, ad un sistema crittografico polialfabetico, quello di Vigenère, ed a un metodo di decifrazione di messaggi cifrati con esso. Per chi avesse (tempo e) voglia da dedicarci, qui ci sono due crittogrammi da decifrare (questa potrebbe anche essere un'idea per il progetto finale).

Abbiamo poi fatto alcune osservazioni sugli invertibili in aritmetica modulare, ed abiamo discusso della funzione di Eulero, del teorema di Fermat-Eulero, del piccolo teorema di Fermat. Per chi volesse testare la propria comprensione di questi argomenti, ecco alcuni esercizi a riguardo.

L'ultimo incontro (1 marzo) è stato, a causa della piccola emergenza climatica, riservato a pochi affezionati. Abbiamo parlato quasi esclusivamente di crittografia a chiave pubblica, seguendo la presentazione la cui prima parte avevamo già visto all'incontro precedente (ma non abbiamo discusso il protocollo ElGamal).

Progetto finale ed altro

Vi ricordo che ciascuna scuola che ha partecipato agli inconti è invitata a presentare, entro fine mese, una prima bozza di poster su argomenti collegati a quelli che abbiamo trattato; tra questi ne sarà selezionato uno che chiederemo di espandere e trasformare in una presentazione anche orale. La presentazione ed i poster (in versione definitiva, ovviamente) saranno esibiti in occasione del workshop finale PLS 2018 il prossimo 8 marzo.

Questo file offre alcuni suggerimenti su possibili argomenti. Come è ovvio, altre idee sarebbero più che benvenute.

Naturalmente resto a disposizione per chiarimenti ed ulteriori approfondimenti relativi al progetto finale, ma anche che per altre esigenze e curiosità. I miei recapiti sono (oltre che qui, a piè di pagina) nella pagina iniziale del mio sito per la didattica.