sabato 17 aprile 2021

Crittografia e Hashing

Introduzione

Esamineremo in questa nota i concetti principali  di criptografia e hashing, a cosa servono, come vengono usati e le best practices in ambito di sicurezza dei dati.



Occorre innanzitutto distinguere due tipi di funzioni che possono essere applicate ai dati: la cifratura e l'hashing. Entrambi trasformano un testo "in chiaro" in un testo completamente diverso, ma con differenze sostanziali: la cifratura produce una serie di caratteri che può essere, mediante la decifratura, ritrasformata nel testo iniziale, mentre l'hashing non è una funzione invertibile.
La dimensione di un file criptato è in generale molto simile alla dimensione del file originale, mentre l'hashing occupa molto meno spazio (a meno che il file originale non sia di pochi caratteri).
La cifratura serve a trasmettere un file in modo che sia leggibile solo a chi sappia come decifrarlo. 
Durante la seconda guerra mondiale la decifratura di messaggi ha consentito di intercettare molte rotte di sommergibili e attacchi sia via terra che via mare. La possibilità di veicolare dati in modo che non siano accessibili da tutti è essenziale oggi in cui dati di ogni genere viaggiano e giacciono su server lontani migliaia di chilometri da chi li utilizza.
Viceversa l'hashing produce una sequenza di byte che è una "sintesi", in qualche modo, di un file in chiaro, in modo che leggendo l'hash del messaggio sia possibile stabilire se il messaggio non sia stato modificato in seguito al calcolo dell'hash.
Un altro utilizzo degli algoritmi di hashing è la memorizzazione delle password. In questo caso è memorizzato direttamente l'hash della password e non la password stessa, e poi, quando l'utente fornisce la password, ne è calcolato l'hash e confrontato con quello memorizzato per vedere se coincidono.

Prima di addentrarci nei dettagli dei vari algoritmi, consideriamo un aspetto importante sulla sicurezza:

Principio di Kerckhoffs

La conoscenza dell'algoritmo non deve causare un indebolimento della sua robustezza crittografica

In sostanza la sicurezza non deve dipendere dal nascondere l'algoritmo con cui è implementata ma solo dalla chiave crittografica utilizzata in esso.
Questo principio è diametralmente opposto a quello della "sicurezza tramite segretezza", che già dal 1851 è stato sconfessato dagli esperti di sicurezza, oggi come oggi infatti è ampiamente accettato dalla comunità scientifica che gli algoritmi open source siano molto più robusti, poiché grazie alla collaborazione delle comunità, le falle  di un algoritmo pubblico possono essere scoperte più facilmente e rapidamente corrette, rispetto a quelle di algoritmi "segreti" e manutenuti da un singolo attore.

Il NIST (National Institute of Standard and Technology) negli Stati Uniti sconsiglia espressamente questa pratica. A tal proposito vedasi "Guide to General Server Security", sezione 2.4 Open Design: System security should not depend on the secrecy of the implementations or its components.

Dunque è inutile e sbagliato, quando si tratta di sicurezza, inventarsi algoritmi propri per crittografare i dati: è meglio utilizzare algoritmi pubblici e ben collaudati, e preoccuparsi piuttosto di nascondere le chiavi in modo corretto.


Crittografia

La crittografia serve dunque a "offuscare" un messaggio, in modo che solo chi è autorizzato possa decodificarlo. Oltre al messaggio, il ricevente dovrà conoscere (per altre vie), la "chiave" necessaria a decodificarlo, senza la quale non è possibile risalire al messaggio originale. 

Possiamo dunque ragionare degli algoritmi crittografici come delle funzioni che siano in qualche modo invertibili.
Distinguiamo in tal senso due grandi famiglie di algoritmi crittografici, quelli simmetrici e asimmetrici.
 

Crittografia simmetrica

Nella crittografia simmetrica c'è una sola chiave "segreta", ed è usata sia per la cifratura che nella decifratura di un messaggio. 
Ossia considerata una coppia di funzioni di cifratura/decifratura cypher/decypher, ed un segreto (secret), il procedimento sarà del tipo
Cifratura:     
obfuscated message =  cypher(message, secret)

Decifratura:
message = decypher(obfuscated message, secret)

Ossia secret è lo stesso sia in cifratura che decifratura, e deve essere noto a priori da chi riceve il messaggio da decodificare.
Alcuni algoritmi di crittografia simmetrica sono: 
  • DES (Data Encryption Standard): a 16 stadi, si basa su una chiave a 56 bit e cifra sequenze di 64 bit, da molto tempo, con le potenze di calcolo disponibili, è possibile forzarlo in poche ore o minuti
  • 3DES: a 48 stadi, si basa sulla triplice applicazione del DES, con 3 chiavi distinte, per cui in totale la chiave è di 168 bits ed il blocco cifrato è di 64 bit. La sicurezza garantita è però solo di 112 bits, ossia il doppio del DES. E' ai fini pratici un algoritmo molto sicuro, poiché il migliore attacco conosciuto richiede circa 2^32 parole conosciute, 2^113 passi, 2^90 cifrature DES e memoria per 2^88 bytes. Di fatto se usata solo all'interno di una singola sessione non è praticamente attaccabile 
  • AES (Advanced Encryption Standard), o anche Rijndael: a 10/12/14 stadi si basa su una chiave a 128/192/256 bit, e codifica sequenze di 128 bit, sta sostituendo il 3DES in tutti gli usi, è più veloce da applicare ed è facilmente "cablabile" in circuiti fisici, richiede poca memoria e fornisce un ottimo livello di sicurezza, che varia a seconda della dimensione della chiave usata. Non esistono al momento attacchi possibili a questo codice attuabili "praticamente".
  • IDEA, CAST5, BLOWFISH, TWOFISH: sono altri algoritmi ma meno usati, poiché l'AES è stato quello scelto dal NIST nel 1997 per rimpiazzare il 3DES
Un punto debole del 3DES rispetto all'AES è che codifica blocchi di 64 bit anziché 128, e questo lo rende maggiormente vulnerabile ad un certo tipo di crittoanalisi .

Ai fini pratici, il 3DES o l'AES sono ottimi algoritmi di crittografia simmetrica, ovviamente poi bisogna effettuare delle considerazioni:
  • per quanto tempo si desidera nascondere le informazioni? se supponiamo ad esempio di nascondere un'informazione che sarà resa pubblica tre giorni dopo, e supponiamo che con la massima potenza di calcolo disponibile sia possibile decifrare il messaggio criptato in 30 anni, questo rende l'algoritmo assolutamente sicuro. Viceversa se si vuole nascondere un'informazione per periodi molto più lunghi, bisogna anche considerare che in futuro la potenza di calcolo potrebbe aumentare e rendere la cifratura meno sicura.
  • quanto è importante quell'informazione e quanto chi ha interesse a decifrarla potrebbe essere disposto a spendere per riuscirci

Questi algoritmi sono presenti in tutte le librerie standard, per cui non saranno forniti qui i dettagli di funzionamento, già descritti ampiamente altrove.


Crittografia asimmetrica, o anche "crittografia a chiave pubblica"

In questo caso nella cifratura e nella decifratura del messaggio sono usate chiavi diverse, una pubblica ed una privata. La forza del metodo risiede nel fatto che non è praticamente possibile ottenere la chiave privata dalla conoscenza della chiave  pubblica, e tutto questo si basa sull'impossibilità di decomporre in fattori primi numeri molto grandi. 
I fondamenti matematici affondano le radici nel piccolo teorema di Fermat e sul teorema cinese del resto, in sintesi sul fatto che 

 ove p,q sono numeri primi, e detto n=pq,  e detto T = (p-1)(q-1), ed "e" (esponente pubblico) un numero coprimo con T e più piccolo di T, e "d" (esponente privato) tale che ed=1 (modulo T)

In questo caso il procedimento è dunque:
Cifratura:     
obfuscated message =  cypher(message, chiave pubblica)

Decifratura:
message = decypher(obfuscated message, chiave privata)

ossia 
 decypher( cypher(message,chiave pubblica) , chiave privata) = message

Le due chiavi, pubblica e privata, sono in un certo senso una inversa dell'altra, poiché sono (anche) tali che, usando la chiave privata nell'algoritmo di cypher, questo possa essere decifrato con la chiave pubblica, ossia vale anche:
 decypher( cypher(message,chiave privata) , chiave pubblica) = message

Garanzia sul mittente mediante RSA

E' possibile anche garantire al ricevente che il messaggio sia autentico, ossia proveniente dal giusto mittente e non manipolato, se il mittente, prima di inviare il file, lo cifra con la  propria chiave privata.
Chiamiamo Mpubb e Mpriv chiavi pubbliche e private del mittente, e Rpubb e Rpriv  chiavi del ricevente.
Il mittente cifra prima il messaggio con la chiave pubblica del ricevente e poi con la propria chiave privata:
obfuscated message =  cypher(cypher (message, Rpubb), Mpriv)

Il ricevente decifra prima il messaggio con la chiave pubblica del mittente e poi con la propria chiave privata, e sa che il mittente è l'unico che può aver cifrato il messaggio con la chiave Mpriv
message = decypher( decypher( obfuscated message, Mpubb), Rpriv)

Per ottenere un buon livello di sicurezza è necessario utilizzare chiavi di almeno 2048 bit. Una chiave di 1024 bit può essere decomposta in circa un anno di tempo al costo di circa un milione di dollari.


Protocollo di Diffie-Hellman

Sviluppato da Diffie ed Hellman nel 1976, permette a due utenti di stabilire una chiave condivisa segreta utilizzando un canale non sicuro. Questo è di solito usato nella procedura di handshake che precede una comunicazione con uno schema di crittografia simmetrica. La chiave simmetrica è usata come chiave di sessione, temporanea, prima dell'invio dei dati con la crittografia asimmetrica.

In sostanza i due interlocutori A e B, che si sono preventivamente messi d'accordo su un gruppo ciclico G (pubblico), generano rispettivamente due numeri casuali a e b. A invia g^a a B e B invia g^b ad A.
A calcola  (g^b)^a, e B calcola (g^a)^b, che sono uguali, e che costituisce la chiave condivisa per una crittografia simmetrica.

L'algoritmo può essere reso più sicuro se l'invio di A è effettuato usando con un algoritmo RSA facendo in modo che A invii a B un dato crittografato con la chiave privata di A (e viceversa).


Digital Signature Algorithm (DSA)

E' uno standard per la firma digitale, che si basa sul calcolo dello SHA (che vedremo tra poco) del messaggio e alla firma mediante una chiave privata di esso, in modo tale che per chi riceve il messaggio sia possibile, con un calcolo inverso, verificare che la firma presente contenga effettivamente lo SHA del messaggio cifrato con la chiave privata del firmatario.
I principi alla base del DSA sono sostanzialmente quelli dell'algoritmo RSA.


Hashing

Una funzione di Hashing mappa una stringa di lunghezza qualsiasi in una stringa di dimensione predefinita.
La caratteristica principale di una funzione di hashing è che non deve essere computazionalmente trattabile il problema di cercare una stringa avente l'hash dato. La differenza tra i vari algoritmi di hashing sta in quanto sia probabile avere delle collisioni. Le principali funzioni di hash sono  l'MD5, lo SHA, il RIPEMD.

SHA

Lo SHA è una famiglia di vari algoritmi, SHA1, SHA-224, SHA-256, SHA-384, SHA-512, ognuno dei quali produce un hash di tanti bit quanti indicati dal nome, tranne lo SHA-1 che produce un digest di 160 bit.
Lo SHA-1 è stato "craccato" da algoritmi di critto analisi, quindi sono da preferirsi i fratelli maggiori. Opera con blocchi di 10 bytes e produce un hash di altrettanti bytes.
 Lo SHA-256 o 512 sono quelli attualmente ritenuti sicuri, e operano e restituiscono blocchi rispettivamente di 16/32 bytes.
Lo SHA-1 è tuttavia usato in molti protocolli e applicazioni, tra cui TLS, SSL, PGP. S/MIME e IPSec.


MD5

L'MD5, message-digest algorithm, lavora su blocchi di 32 bytes e produce un hash di 16 bytes. Nel 2012 è stato craccato e la sua debolezza usata dal malware Flame , pertanto non dvrebbe più essere usato. In particolare è stato trovato un algoritmo in grado di trovare in pochi secondi dei messaggi aventi un determinato hash. Questo rende l'algoritmo inutilizzabile, poiché sarebbe potrebbe essere facile per un utente maligno lasciare intatta la firma (vedasi DSA) e cambiare il messaggio con un altro avente lo stesso hash per far credere al ricevente che sia un messaggio genuino.


RIPEMD

Ne esistono varie versioni operanti con  varie lunghezze di blocchi: 160,256,320. Sviluppati per risolvere i problemi dell'MD5 sono però sono meno sicuri degli SHA, per cui si raccomanda l'uso degli SHA.

Crittografia Ellittica o ECC

E' un tipo di crittografia a chiave pubblica basata sulle curve ellittiche definite su campi finiti.

A differenza degli algoritmi RSA, che si basano sulla difficoltà di decomporre in fattori primi grossi numeri. questi algoritmi si basano sulla difficoltà di risolvere l'equazione a^x=b quando questa si presenta in un campo finito. In altre parole sulla difficoltà di calcolare il logaritmo discreto di un numero. Al momento gode di una buona reputazione ed è stata inserita tra gli algoritmi consigliati dalla NSA.

Memorizzazione delle password

Un problema ricorrente per chi scrive software è memorizzare le password degli utenti, per poter in seguito verificare se quella che inseriscono è corretta.
Senz'altro non vanno memorizzate in chiaro, e bisogna fare in modo tale che chi dovesse venire in possesso del file o del database ove sono memorizzate le password "criptate", non possa ottenere le password in chiaro e possibilmente nemmeno collegarle agli utenti.
Per oscurare la password, il metodo principe utilizzato è senz'altro l'hash, nella fattispecie è stato a lungo usato l'MD5 ma oggi è preferito lo SHA256 o 512.

Attacchi dizionario e sicurezza delle password

E' una tecnica di attacco ad una password confrontandone l'hash con gli hash contenuti in uno o più dizionari di password già calcolate. Per le proprietà della funzione di hash, non è possibile in maniera diretta risalire ad un testo (password) avente lo stesso hash, ma se la password è semplice o già usata da altri, è facile che questa sia presente in un "dizionario" di hash.
I dizionari sono spesso calcolati da dizionari veri e propri di lingua, e poi ottenute a partire dalle parole in esse contenute delle varianti inserendo uno o più numeri o altri caratteri. 
Tuttavia tante più caratteri si considerano e tanto più un attacco a dizionario non ha alcun modo di riuscire. 
Ad esempio se consideriamo una password di 16 caratteri, con caratteri scelti a caso tra lettere maiuscole, minuscole, caratteri speciali e cifre, per semplicità supponiamo da un set di 80 caratteri, le combinazioni possibili sono di 80^16 = 2.8 * 10^30
Uno dei più grandi database esistenti di password contiene circa 1.5 * 10^10 hash di password, ossia 15 miliardi.
Da un rapido calcolo si può facilmente evincere che la probabilità che la password così generata sia contenuta in un siffatto database è di circa 1 / (1.8 * 10^20 ) ossia  una possibilità ogni duecento  miliardi di miliardi.
Ora, se tutti usassimo password così sicure e usassimo le stesse una volta sola per ogni sito o programma a cui ci iscriviamo, e magari  periodicamente, mettiamo ogni 6 mesi, le cambiassimo, nessun attacco a dizionario avrebbe mai successo. In sostanza 15 miliardi di password in un dizionario possono sembrare tante, ma rispetto alle possibilità combinatorie con 16 caratteri sono meno di un granello di sabbia nel deserto.

E' inoltre da notare che si volesse tentare di violare una siffatta password, anche con tutta la potenza di calcolo dei più potenti processori, anche potendo testare 1 miliardo di hash al secondo (quelli più potenti attuali non superano qualche centinaio di migliaia al secondo), ci vorrebbero circa 2.8 * 10^20 secondi, siamo intorno ai 10^13 anni. Si consideri che si prevede che il sole si spegnerà tra soli 5-7 miliardi di anni.

Tuttavia molti utenti scelgono password ben più semplici  e/o le utilizzano in più occasioni, pertanto tali password diventano tanto sicure quanto il meno sicuro dei siti in cui le usano.
E ci sono siti che addirittura le memorizzano in chiaro, perché non gestiti da professionisti.



Hashing ripetuto e Salt 

Per proteggere le password degli utenti, soprattutto quelli che malauguratamente abbiano usato una password "semplice" o l'abbiano usata su più database si usano tecniche di key stretching e di salt.
Il key stretching consiste nel rafforzare la password inserita dall'utente applicando l'algoritmo di hash ripetutamente anziché una volta sola. In questo modo il confronto tra le hash dovrà prevedere che nel dizionario di ricerca dovrà essere presente la stessa password a cui è stato applicato l'algoritmo di hash lo stesso numero di volte. Questo comporta che quanto meno il database dovrà essere una quantità di dati tanto maggiore (linearmente) quante sono le volte in cui è stato applicato l'algoritmo.
Se si pensa che un algoritmo si può applicare facilmente 100 volte, questo può significare che l'attaccante dovrà avere un database 100 volte più grande e tempi 100 volte più lunghi.
Ovviamente sarà poi necessario ricordarsi quante volte bisogna applicare l'algoritmo di hashing, o in alternativa provarlo iterativamente sino ad un numero massimo di volte prefissato, quando si va a verificare la corrispondenza in fase di autenticazione dell'utente.
 
Un'altra tecnica che si utilizza, sempre per prevenire attacchi a dizionario, è di aggiungere, magari sparpagliati o in coda alla password dell'utente, dei caratteri random, il cosiddetto salt. 
Il salt è diverso da utente ad utente  e viene generato in maniera casuale ogni volta che è salvata una nuova password.
Tali caratteri sono aggiunti prima di applicare l'algoritmo di hashing, con il risultato da rendere non confrontabili le hash memorizzate sui database-dizionario. Se si pensa che l'aggiunta di un solo bit raddoppia le combinazioni, aggiungendo soli due caratteri si ottiene che le combinazioni possibili per ogni password (volendo provare tutti i salt collegati) sono 65 mila volte maggiori, e 4 miliardi di volte se aggiungiamo 4 byte di salt.
Se il database fosse quello a cui facevo riferimento prima, di 15 miliardi di hash, calcolare per ogni hash 4 miliardi di varianti sarebbe fisicamente impossibile.
Dunque è buona prassi, per rendere inefficaci gli attacchi dizionario, aggiungere dei byte di salt e memorizzare questi separatamente dalle password (stessa cosa nel numero di ripetizioni visto nel key stretching).
In questo modo, anche se il file delle password dovesse finire in mano ad un hacker, sarà impossibile per lui risalire alle password in chiaro se non munito anche del file dei salt e del numero di ripetizioni.


Idea: Pin come Salt

Il salt ed il numero di iterazioni andrebbero memorizzati, come detto, in un luogo diverso rispetto al database delle password.
Un'idea è di non memorizzarli affatto, e di utilizzare, in alternativa, un "pin" come quello richiesto nell'accesso da alcune banche. Ad esempio considerato un pin di 6 cifre, queste possono essere considerate il salt. In fase di login saranno chieste solo 3 cifre in posizioni random del pin, e sarà effettuato, per le restanti tre, un mini attacco brute force, di massimo 1000 tentativi, quindi abbastanza veloce da attuare. In questo modo si ottiene il vantaggio che un dizionario per includere quelle 6 cifre aggiuntive dovrebbe essere 1 milione di volte più grande, ad esempio il dizionario visto prima dovrebbe contenere invece di 15 miliardi 15 milioni di miliardi di hash e relative password,  cosa molto più costosa e fisicamente inattuabile (anche la dimensione, da qualche giga bytes, diverrebbe di petabytes ossia migliaia di terabytes).



Conclusioni

Abbiamo esaminato diverse tecniche di crittografia ed hashing, elencato i livelli di sicurezza di ognuno e annotato quelli ormai da non usare perché "craccati" o non più abbastanza sicuri. Abbiamo esaminato alcuni tipi di attacco e  le best practices di come memorizzare le password, oltre a proporre un modo di salvare il salt in modo sicuro (ossia non salvandolo affatto).
Si conclude ricordando che quando si usano delle password, non bisogna mai riusarle in più siti o applicazioni, e devono sempre essere di più di 10 caratteri, presi a caso tra maiuscoli, minuscoli, numeri, caratteri speciali, in modo da ampliare il set di caratteri che dovrà essere usato per un eventuale attacco brute force. Ad esempio la differenza tra 26^10 = 1.41 10^14  e 80^10 = 10^19 è già dell'ordine di 10^5.


- Nessun commento:
Etichette: , , , , , , , , , , ,

lunedì 5 aprile 2021

Refactoring: improving abstraction

 Astrazione

L'astrazione consente di semplificare le entità attraverso la riduzione dei dettagli non rilevanti e la generalizzazione, operata individuandone le caratteristiche principali.
L'astrazione è cruciale nel problem solving per poter decomporre un sistema reale in componenti e stabilire le loro connessioni in modo da poterlo gestire più efficacemente.


I principi che dovrebbero guidare la progettazione e l'individuazione delle varie entità per comporre un modello di un sistema sono:
  • Identificare  e definire il contorno di un "oggetto"
  • Gli oggetti del dominio applicativo dovrebbero avere corrispondenza nel suo modello logico o concettuale. E' molto più facile parlare di oggetti che  hanno una corrispondenza nel mondo reale che di oggetti completamente astratti, pensiamo al caso in cui si voglia validare il modello con il cliente, o anche solo parlarne con un collega.
  • Ogni componente  del modello dovrebbe essere un oggetto "completo" di tutte le funzioni necessarie per operarvi. "Chiuso" potrebbe essere un altro aggettivo applicabile.
  • Ogni componente del modello dovrebbe avere un unico scopo e che abbia sufficiente complessità da garantirgli il diritto ad esistere
  • Non creare entità simili, ma gestire correttamente l'astrazione e la generalizzazione. Ad esempio non avrebbe senso sviluppare da zero una classe "lista di ordini" e "lista di fatture", ma può avere senso una classe "lista" generica su cui operare a prescindere dal contenuto, e poi in qualche modo ottenere le due classi specifiche a partire da quella

Vediamo allora dei possibili problemi che possiamo riscontrare in un sistema e come porvi rimedio.


Astrazione mancante

Un sintomo è la presenza di pezzi di codice simili in varie parti del programma al fine di ottenere gli stessi obiettivi. 
Le cause possono essere una progettazione incompleta, o manutenzioni di tipo quick-fix, o si è pensato di cercare di migliorare la velocità di esecuzione a scapito della modularità.

La soluzione consiste di solito nell'introdurre nuove classi, e sostituirle ai tipi semplici usati nel codice esistente, o in alternativa raggruppare strutture dati in classi e gestirle con i metodi della classe.
Questo refactoring favorirà la manutenibilità, l'estendibilità, la riusabilità e la testabilità, tuttavia bisogna stare attenti a non eccedere e creare classi per funzioni davvero troppo semplici (over-engineering)

Astrazione imperativa

Questo problema si evidenzia quando ci sono funzioni che sono state erroneamente trasformate in classi. Un sintomo è il nome della classe, di solito costituito da un verbo, come "leggiOrdini" o "stampaFatture". 
L'errore consiste nel fatto che la classe non rappresenta un entità del sistema, ma un'azione che si può compiere su essa. Può derivare da una cattiva traduzione da un programma di tipo procedurale ad uno ad oggetti, o una cattiva applicazione dell'OOP.
La soluzione può consistere nella creazione di un metodo ad una classe esistente, o la creazione di una nuova classe avente come oggetto i dati su cui operava la precedente classe, e magari altri metodi inerenti gli stessi dati.
Anche in questo caso il refactoring migliorerà la riusabilità (è molto meglio avere una classe che gestisce un'informazione "in toto" che non avere n classi per ogni operazione che si vuole svolgere su essa. Anche la leggibilità e la testabilità ne avranno beneficio, potendo collegare tali funzioni ai dati della classe e non a dati generici non strutturati o addirittura dislocati altrove.

Astrazione incompleta

Accade quando una classe non fornisce tutti i metodi necessari per operare sull'oggetto da essa gestito.
Il risultato è che per eseguire tali operazioni ci sono metodi esterni o codice duplicato sparso nel programma.
La causa potrebbe essere una progettazione incompleta che non ha previsto la realizzazione di una certa funzione, seguita da manutenzioni quick-fix operate su classi diverse.
Un indizio a cui prestare attenzione è la presenza di alcune funzioni, che di solito vanno in coppia, senza la presenza del proprio "simmetrico", come ad esempio la presenza di un min senza un max, o similmente per first/last, push/pop, left/right, open/close, insert/delete, start/stop e via dicendo.
La soluzione è certamente creare i metodi mancanti con attenzione ai parametri per poterli usare nel codice sostituendo lo spaghetti-code presente al momento.
Inutile dire che la manutenibilità ne avrà gran giovamento, così come la leggibilità e la testabilità.

Astrazione sovraccarica

Accade quando ad una classe sono addossate troppe responsabilità. E' un problema simile a quello che abbiamo già trovato quando abbiamo parlato di modularità (insufficiente in questo caso).
In questo caso abbiamo una ridotta manutenibilità e maggiore impatto delle modifiche della classe nei confronti del resto del sistema.
A volte si presenta quando si vuole gestire con la stessa classe dei  dati eterogenei, con metodi tuttavia simili. E' spesso complicato correggere tale situazione, perché per la sua natura è usata in molti punti. Il risultato è la mancanza di coesione e tutto quel che ne consegue.
Spesso la  soluzione è estrarre tante classi quante sono le diverse responsabilità che sono state in essa sovrapposte, ed usare questa nella classe stessa o direttamente nei client esistenti.

Astrazione inutilizzata

Si ha quando una classe è del tutto inutilizzata, ossia addirittura suo codice risulta irraggiungibile.
Può succedere se è stata progettata ma poi abbandonata in favore di altre classi, o era una classe astratta poi non seguita da alcuna implementazione concreta.
La progettazione non dovrebbe dare luogo a questo genere di classi, bensì dovrebbero essere sviluppate solo le classi che realmente sono necessarie. Cercare di prevedere futuri bisogni in maniera speculativa ed iperprudenziale tende a creare queste classi. In alternativa può capitare che in manutenzioni quick-fix siano state create nuove classi in sostituzione di quelle inutilizzate invece di manutenerle, per timore di creare malfunzionamenti sul codice esistente.
Tutto questo causa maggior lavoro di manutenzione (quando si analizza l'impatto di nuove modifiche) su codice che in realtà non è nemmeno utilizzato.
Di solito la soluzione è molto semplice: rimuovere del tutto queste classi, o iniziare ad usarle se per caso in qualche punto avrebbero dovuto essere usate ma ci si è dimenticati della loro esistenza e aggirato l'ostacolo con del codice collocato a macchia di leopardo in altre classi.


Astrazione non necessaria

Accade quando è introdotta una classe che non sarebbe stata necessaria, perché svolge un compito troppo semplice o quasi del tutto assente.
Può capitare se il codice deriva da traduzioni da altri linguaggi procedurali, e sono state introdotte classi che sostituiscono strutture dati, prive (o quasi) di metodi, oppure per sopperire a limitazioni del linguaggio, oppure come causa di over-engineering, una progettazione iperprotettiva.
In questi casi si può, a seconda, sopprimere la classe, spostarne i metodi in altre classi, o trovare i metodi per sopperire alle carenze di un linguaggio con altri costrutti del linguaggio ospitante.


Astrazione duplicata

Accade quando ci sono classi con lo stesso nome o con la stessa funzione. La duplicazione andrebbe evitata in ogni caso, perché crea problemi sia in fase di comprensione che di manutenzione e viola il principio DRY (Don't repeat yourself)
Possono essere generati da programmazione copia-incolla, da più rami di progetto sviluppati da team che non comunicavano tra loro, o necessità di derivare classi che però erano non derivabili.
La soluzione può essere rimuovere le copie e lasciare in vita solo una delle classi, ove possibile, oppure ove presenti piccole differenze, effettuare un subclassing da una classe base comune. In alternativa modificare i client per usare solo una delle classi esistenti e rimuovere le altre.
Se si trattava di non poter derivare una classe "chiusa" alle derivazioni, valutare se utilizzare una classe bridge




bibliografia
Refactoring for Software design smells,  Girish Suryanarayana, Ganesh Samarthyam, Tushar Sharma

- Nessun commento:
Etichette: , , , , , ,

sabato 3 aprile 2021

Numeri primi e funzione Z di Riemann

Introduzione

In questa nota raccoglierò alcune formule e teoremi inerenti i numeri primi e la funzione Z, al solo fine di avere un punto di raccolta online sul tema, per coloro (presumo pochi) che fossero, come me, appassionati dell'argomento.
Non esporrò tutte le dimostrazioni, ma eventualmente darò i riferimenti su dove trovarle ove si fosse interessati ad esse.
In fondo all'articolo c'è una bibliografia con tutto il materiale per approfondire.
La presente nota sarà integrata nel tempo ossia non è (e forse non lo sarà mai) "finita".
Le formule sono ottenute con codecogs e math.typeit


Nomenclatura

π(n) = quanti numeri primi ci sono tra 1 e n

Teorema dei numeri primi

Questo teorema è talmente importante che ha una sua sigla propria, ossia TNP.
Afferma che 
  [1]



ossia che tra 1 ed n ci sono circa n/log(n) numeri primi. Statisticamente la probabilità che un numero compreso tra 1 ed n sia primo è 1/log(n). 
Alternativamente, l'n-no numero primo vale circa n log(n)
Questo risultato, inizialmente intuito da Gauss fu provato poi da Hadamard e Lavallée Poussin nel 1896. Gauss congetturò la stima data da
\pi(x) \sim Li(x)


ove Li(x) è il logaritmo integrale di x, definito come

Li(x) = \int_2^x \frac{1}{log(y)}dy   [2]


Il logaritmo integrale Li(x) è calcolato da 2 per non includere la singolarità nel punto 1, e rispetto alla versione  
li(x) = \int_0^x \frac{1}{log(y)}dy

Si ha che Li(x) = li(x)-log(2). li(x) ha un solo zero, circa in x=1.4513569... costante nota come di Ramanujan-Soldner.


Si osserva che π(x) < Li(x) per numeri non troppo grandi e che il primo cambiamento di segno della loro differenza π(x) - Li(x) è intorno a 10^371. Il primo a congetturare un limite superiore per il primo cambio di segno fu Skew, che dimostro che tale numero era inferiore a 
poi detto numero di Skew.
Littlewood ha dimostrato che tale differenza cambia di segno infinite volte.


Somma degli inversi dei numeri primi minori di N

Già Eulero dimostrò che

\sum_{p<x} 1/p \sim log(log(x))  [3]

ossia che la somma dei numeri primi minori di x tende a log(log(x)), nel senso che il loro rapporto tende a uno.
Tal somma tende all'infinito, molto lentamente, tanto che John Selfridge, un teorico dei numeri, usava dire "Si sa che log(log(n)) cresce all’infinito, ma nessuno l’ha mai visto arrivarci."

In particolare Mertens ha dimostrato che

 [4]


Identità di Eulero o prodotto di Eulero

Per s∈ℝ, Re(s)>1
\sum_{n} \frac{1}{n^s} = \prod_{p} \frac{1}{1-p^{-s}}   [5]


questa identità è molto interessante in quanto mette in relazione un prodotto in cui ci sono tutti i numeri primi con una somma  in cui figurano potenze di tutti i numeri naturali. Eulero studiò questa identità sul campo ℝ, poi Riemann la studiò su ℂ, per Re(s)>1 e poi estendendola a tutto ℂ mediante la funzione ζ.

Funzione fattoriale complesso

Eulero estese la funzione fattoriale n! = n(n-1)*.. *3*2*1 dai numeri naturali a qualsiasi numero reale maggiore di -1 osservando che per n intero
n! = \int_{0}^\infty e^{-x}x^{n}dx      [6]  

e definendo quindi Π(s) la funzione di variabile complessa:

\Pi(s) = \int_{0}^\infty e^{-s}x^{s}dx  [7]

ove si osserva facilmente che Π(n) = n! per n intero

Tale funzione è strettamente collegata alla funzione Γ di Eulero che vedremo tra poco. in alcune scritture tuttavia risulta più comodo usare la funzione Π così definita che la funzione  Γ.

Si può provare che si può estendere tale funzione a tutto il piano complesso osservando che:
\Pi(s) = \lim_{n \to \infty} \frac{n! (n+1)^s}{(s+1)(s+2)\cdot \cdot \cdot (s+n)}    [8]


Si dimostra che valgono le seguenti proprietà per la funzione fattoriale complesso:

\Pi (s) = \prod_{n=1}^{\infty} \frac{n^{1-s}(n+1)^s}{s+n} = \prod_{n=1}^{\infty} (1+\frac{s}{n})^{-1}(1+\frac{1}{n})^s    [9]


    [10]


   
\Pi(s)\Pi(-s) = \frac{\pi s}{sin (\pi s)}  [11]



\pi(s) = 2^{s} \pi(\frac{s}{2}) \pi(\frac{s-1}{2})\pi^{-1/2}   [12]



Funzione Gamma Γ di Eulero

Correlata alla funzione fattoriale complesso è la funzione 
 


molto usata in statistica (si veda la distribuzione gamma)
Facilmente si osserva che 

 [13]

ossia

[14]



quindi per la funzione gamma valgono relazioni simili a quelle riportate (8,9,10,11) cambiando s in s-1
in particolare
 
  [15]


\Gamma(z) = \lim_{n \to \infty}\frac{n!n^z}{z (z+1)...(z+n)}  [16]

e l'analoga della [11] è 

\Gamma(s)\Gamma(-s) = \frac{\pi}{sin (\pi s)} [11a]

(si noti che nel numeratore manca la s) da cui si ricava facilmente  Γ(1/2) = √π

Una particolarità delle funzioni Π e Γ è che, per via della [11] e [11a], conoscendone il valore in a+ib, con a e b reali e 0<a<1 è possibile ricavarne il valore di un generico x+ib con x>0 applicando ricorsivamente la formula ossia calcolando, ad esempio,
Γ( x + ib) = (x+ib) Γ( (x-1) + i b)  = (x+ib)(x-1+ib) Γ( (x-2) + i b) = ..
sino ad arrivare alla parte intera n di x per cu si avrà
Γ( x + ib) =  (x+ib)(x-1+ib)...(x-n+ib)  Γ( (x-n) + i b)
dove x-n è compreso tra 0 e 1.
In sostanza si ha

\Gamma(s)= \frac{\Gamma(s+n)}{s (s+1) .. (s+n-1)} [17]

da cui possiamo anche osservare che Γ ha dei poli semplici in 0, -1, -2,... e non ha zeri.
Per Re(s) >0 si ha che Γ(s)>0 mentre per Re(s)<0 è positiva o negativa a seconda della parte intera di s, ossia negativa tra -1<Re(s)<0, positiva tra -2<Re(s)<1 etc.



Funzione ζ di Riemann  

Questa è la sezione che descrive la funzione di maggiore interesse dell'articolo, quindi sarà trattata con maggiore cura.
Riemann estende la funzione definita per Re(s)>1
  [18]

con una  funzione meromorfa  ζ valida su tutto ℂ e che sodisfa la seguente equazione funzionale:
\zeta(s)= \Pi(-s) (2\pi)^{(s-1)}2sin(\frac{s\pi}{2})\zeta(1-s) [19]

che si dimostra essere equivalente a 

\Gamma(\frac{s}{2})\pi^{-s/2}\zeta(s) = \Gamma(\frac{1-s}{2})\pi^{-(1-s)/2}\zeta(1-s) [19b]


come mostreremo ora, a grandi linee.
E' chiaro quindi che la funzione ζ è strettamente collegata alla funzione Γ.



Alla sinistra del semipiano Re(s)>1 sostituendo nt a t nel prodotto di Eulero e calcolando per x-1 [7]
ossia (riprendendo la formula già vista) in

\Pi(s) = \int_{0}^\infty e^{-t}t^{s}dt [7]

consideriamo nx = t e quindi ndx = dt  quindi otteniamo

     [20]


e calcolando per s-1 otteniamo dopo pochi passaggi


\int_{0}^\infty e^{-nx} x^{s-1} dx = \frac{\Pi(s-1)}{n^s}  [21]



a questo punto Riemann somma i due membri per n che varia da 1 a ∞:

\sum_{n=1}^{\infty}\int_0^\infty e^{-nx}x^{s-1} = \sum_{n=1}^{\infty}\frac{\Pi(s-1)}{n^s}



e osservato che 
\sum_{n=1}^\infty r^{-n} = \frac{1}{1-r^{-1}}-1 = \frac{r}{r-1}-1 = \frac{1}{r-1}

ove in questo caso r = e^(-x) che non dipende da s quindi si può eseguire a parte, ottiene 
 
\int_{0}^\infty \frac{x^{s-1}}{e^x-1}dx = \Pi(s-1)\sum_{n=1}^\infty \frac{1}{n^s} = \Pi(s-1) \zeta(s)  [22]


E' possibile dimostrare un lemma, che qui non dimostriamo, che stabilisce che

\int_{-\infty}^\infty \frac{(-x)^s}{e^x-1}\frac{dx}{x} = (e^{i \pi s}-e^{-i \pi s})\int_{0}^{\infty}\frac{x^{s-1}dx}{e^x-1}    [23]

Dove con integrale da +infinito a +infinito si intende un integrale curvilineo che parte da +infinito e si muove in senso anti orario sotto l'asse delle ascisse, gira intorno all'origine e torna a + infinito sopra l'asse delle ascisse.


e che  ricordando la definizione di seno complesso

si ha in questo caso z= πs
dà

\int_{-\infty}^\infty \frac{(-x)^s}{e^x-1}\frac{dx}{x} = 2 i sin(\pi s)\int_{0}^{\infty}\frac{x^{s-1}dx}{e^x-1}  [24]

quindi per la [22] si ha:

  [25]



applicando la [10]   sulla parte destra 
e moltiplicando ambo i membri per Π(-s)  / 2πi


dà

\frac{\Pi(-s)}{2 \pi i} \int_{+\infty}^{+\infty} \frac{(-x)^s}{e^x-1}\frac{dx}{x} = \frac {sin(\pi s)\Pi(-s) \Pi(s)} {\pi s} \zeta(s)  [26]


e tenuto conto della proprietà [11]                             

            
si ottiene finalmente
\zeta(s) = \frac{\Pi(-s)}{2 \pi i} \int_{+\infty}^{+\infty} \frac{(-x)^s}{e^x-1}\frac{dx}{x}     [27]


quando Re(s)>1 questa converge a 

\frac{1}{\Gamma(s)}\int_0^\infty \frac{x^{s-1}}{e^x-1}dx [27b]



Valori di ζ(s), zeri banali

Considerando la funzione x/(e^x-1)  possiamo notare che è la funzione generatrice per i numeri di Bernoulli Bn con B0=1, B1= -1/2
Ossia 
\frac{x}{e^x-1} = \sum_{n=0}^\infty \frac {B_{n}x^n}{n!}  [28]

Da cui ricorsivamente si calcolano, e si può dimostrare che tutti i Bn con n dispari maggiore di uno sono pari a zero.
La  [28] può essere usata per calcolare i valori di  ζ(-n) con n=0, 1,2.. ottenendo infatti che (vedasi rif.[1], pag.12):

\zeta(-n)= (-1)^n \frac{B_{n+1}}{n+1} [29]

da cui discendono tutti gli zeri cosiddetti "banali" della funzione z, ossia essendo Bn pari a zero per tutti gli n dispari maggiori di uno si ha che ζ(-2n) = 0 per ogni n<0
Inoltre si ha che 
\zeta(2n)= \frac {(2 \pi)^{2n} (-1)^{n+1}B_{2n}} {2 \cdot (2n)!}  [30]


Ipotesi di Riemann

Tutti gli zeri non banali di  ζ(s) hanno parte reale pari a 1/2


Per provare questa ipotesi si è cercato di esprimere ζ(s) in vari modi per evidenziarne alcune proprietà

Equazione funzionale

Prende il nome di equazione funzionale di ζ la seguente uguaglianza, che lega  ζ(s) e  ζ(1-s)

  [31]


con una serie di passaggi è possibile dimostrare che quest'ultima è equivalente alla seguente:

\Pi(\frac{s}{2}-1)\pi^{-s/2}\zeta(s) = \Pi(\frac{1-s}{2}-1)\pi^{-(1-s)/2}\zeta(1-s) [32]

Questa è la "forma simmetrica dell'equazione funzionale"
da cui si evince chiaramente che la funzione a sinistra dell'uguaglianza non cambia sostituendo s con 1-s.
La stessa si può anche esprimere in funzione di Γ(s) ricordando che Γ(s) = ∏(s-1):

\Gamma(\frac{s}{2})\pi^{-s/2}\zeta(s) = \Gamma(\frac{1-s}{2})\pi^{-(1-s)/2}\zeta(1-s)  [33]

Che è quella che abbiamo anticipato nella [17a]. 
Da questa uguaglianza si evince chiaramente che gli zeri di ζ sono simmetrici rispetto all'asse x= 1/2. 


Definendo la funzione teta
\psi(x)= \sum_{n=1}^{\infty} exp(-n^2\pi x) [34]

si può dimostrare che tale funzione converge molto rapidamente e che per s qualsiasi

\Pi(\frac{s}{2}-1) \pi^{-s/2}\zeta(s) = \int_{1}^{\infty}\psi(x)[x^{s/2}+x^{(1-s)/2)}] \frac{dx}{x} - \frac{1}{s(1-s)} [35]


Che è un altro modo di evidenziare come la funzione è invariante alla sostituzione di s con 1-s.
Dalla [35] si può anche dedurre che la funzione nella parte sinistra dell'uguaglianza ha poli in 0 e in 1.


Funzione ξ(s)

Riemann moltiplica la funzione alla sinistra della [32]  per s(s-1)/2, ottenendo:

\Pi(\frac{s}{2}-1)\pi^{-s/2}\zeta(s) \frac{s(s-1)}{2}


 e, ricordando che Π(s) = s Π(s-1), ossia che  (s/2) Π(s/2-1) = Π(s/2) definisce:

\xi(s) = \Pi(\frac{s}{2}) (s-1) \pi^{-s/2}\zeta(s)  [36]

L'equazione funzionale di ζ(s) equivale a ξ(s) = ξ(1-s)

Si noti che esistono versioni equivalenti delle equazioni funzionali, che usano la funzione Γ invece di Π. Basterà ricordare che Γ(s+1) = Π(s) ed ottenere quindi, dalla [31], sostituendo Π(-s) con Γ(1-s) :

\zeta(s) = \Gamma(1-s)(2 \pi)^{s-1} 2 \sin( \frac{s \pi}{2}) \zeta(1-s)  [37]


e dalla  [36]  essendo Π(s/2) = Γ(s/2+1) = (s/2) Γ(s/2), si ha

 [38]


La funzione ξ(s) ha gli stessi zeri della funzione ζ(s), ad eccezione di quelli banali ed è per questo che in questa sede ci interessiamo alla sua valutazione

Si dimostra che anche per ξ vale la formula ξ(s)  = ξ(1-s)

 

Funzione ξ(s) come serie di potenze

Si dimostra che è possibile esprimere ξ(s) come serie di potenze:
\xi(s) = \sum_{n=0}^\infty a_{2n}(s-\frac{1}{2})^{2n} [39]

ove 
a_{2n} = 4 \int_1^\infty \frac{d[x^{3/2}\psi'(x)]}{dx}x^{-1(4)}\frac{(\frac{1}{2}logx)^{2n}}{(2n)!}dx  [40]


e dove  Ψ(x) è quella introdotta al punto [29] 


Prodotto di Hadamard

Si dimostra che  è possibile esprimere  ξ(s)  come prodotto infinito:
\xi(s) = \frac{1}{2} \prod_\rho (1 - \frac{s}{\rho})  [41]



ove ρ spazia tra le radici di  ξ, a patto di prenderle a coppie, ossia raggruppando le radici di tipo  ρ e 1- ρ




Relazioni tra ζ(s) e numeri primi

Usando il prodotto di Eulero [5] e usando la definizione di  [17], per Re(s)>1 si ha


\gamma(s) = \prod_{p} \frac{1}{1-p^{-s}} [42]

dove p varia tra i numeri primi.
da cui, effettuando il logaritmo di ambo i membri e sviluppando in serie  si ottiene, per Re(s)>1


log \zeta(s) = \sum_{p}\sum_{n}(1/n)p^{-ns} [43]

A questo punto dobbiamo introdurre una nuova fondamentale funzione, J(x) che inizia da 0 per x=0 e aumenta di uno dopo ogni numero p primo, di 1/2 dopo ogni quadrato di numero primo e di 1/n per ogni potenza n-ma di un numero primo. Nel punto esatto di ogni salto la funzione J(x) è definita come la media tra i due valori prima e dopo il salto.
In sostanza J(x) = 0 per 0<=x<2, J(2)=1/2, J(x)= 2 per 2<x<3, J(3)=1.5, J(x)= 2 per 3<x<5 etc.
Fatta questa premessa, possiamo riscrivere la [38] come:

log \zeta(s) = \int_0^\infty x^{-s}dJ(x) [44]

Dove l'integrale in questione è un integrale di Stieltjes, a proposito si ricorda che l'integrale di Riemann-Stieltjes  di f rispetto a g è definito come

\int_a^b f(x)dg(x) = \lim_{\delta(P)\to 0 } \sum_{c_i\epsilon P} f(c_i)(g(x_{i+1})-g(x_i)) [45]


Ove P={x0=a<x1<x2< ..< xn=b} è una partizione di [a,b] e c1..cn ognuno preso da [xi..xi+1], e δ(P) è il "calibro" della partizione ed è pari al max | xi-xi+1 |, se esiste indipendentemente dalla scelta dei punti  ci
Si dimostra che ove f sia integrabile secondo Riemann si ha che

\int_a^b f(x)dg(x) = \int_a^b f(x)g'(x)dx [46]

Alternativamente, senza ricorrere all'integrale di Stieltjes, la [39] si può scrivere, per Re(s)>1, come:

log \zeta(s) = s \int_0^\infty J(x) x^{-(s+1)}  [47]

in sostanza il logaritmo della funzione  ζ è pari all'integrale di x-s rispetto alla funzione J, che è una funzione che "conta" i numeri primi e le loro potenze, dando come conteggio l'esponente con cui trova il numero primo. 

Inversione di Fourier

Dalla [47] dividendo ambo i termini per s si ottiene, per Re(s)>1

\frac {log \zeta(s)}{s} = \int_0^\infty J(x) x^{-(s+1)} [48]

ed effettuando alcuni passaggi, che includono l'applicazione del teorema di inversione di Fourier, si ottiene, per a>1

J(x) = \frac{1}{2\pi i} \int_{a-i\infty}^{a+i\infty} log(\zeta(s))x^s\frac{ds}{s} [49]


Tenendo presente la definizione di ξ(s) [39]

\xi(s) = \Pi(\frac{s}{2}) (s-1) \pi^{-s/2}\zeta(s) [39]  

possiamo ottenere un'espressione alternativa per log ζ(s):

log \ \zeta(s) = log \ \xi(s) - log \ \Pi(\frac{s}{2})+ \frac{s}{2} log\pi - log (s-1) [50]

e poi  usando la \xi(s) = \frac{1}{2} \prod_\rho (1 - \frac{s}{\rho}) [41]

abbiamo che

log \ \zeta(s) = \frac {1}{2} + \sum_p{log(1-\frac{s}{p})}- log \ \Pi(\frac{s}{2})+ \frac{s}{2} log\pi - log (s-1) [51]

e si dimostra che in questa espressione, il termine predominante è l'ultimo, ossia -log(s-1), quando s tende all'infinito.


Se consideriamo nuovamente la [48] e deriviamo ambo i membri, otteniamo

 [52]


Funzione Ψ(x), o funzione di Chebyshev

La misura (log x) dJ(x) è una misura punto a punto che assegna log(p^n)/n alle potenze dei numeri primi p^n e 0 a tutti gli altri punti, quindi [48] può essere espresso come un integrale di Stieltjes sulla funzione Ψ(x) che inizia assegnando 0 a x=0 e poi ha un salto di log(p^n)/n= log p ad ogni potenza p^n di un numero primo. Ossia:

 
\psi(x) = \sum_{p<x} log(p) [53]

A questo punto possiamo riscrivere la [52] come:


\frac{\zeta'(s)}{\zeta(s)} = \int_0^\infty x^{-s} d\psi(x) [54]


Funzione di von Mangoldt

Consideriamo la funzione, detta di von Mangoldt,
 [55]

questa funzione assegna ad n il peso attribuito dalla funzione Ψ. 
Si può osservare che 
    [56]


e tramite la funzione di Mangoldt si può esprimere la [50] in termini di sommatoria:

-\frac{\zeta'(s)}{\zeta(s)}= \sum_{n=2}^\infty \Lambda(n) n^{-s} [57]

Si può dimostrare che

\Psi(x) = x - \sum_p \frac{x^p}{p}+ \sum_n \frac{x^{-2n}}{2n} - \frac{\zeta'(0)}{\zeta(0)} [58]


e considerato che 

log(\frac{1}{1-x}) = x + \frac{x^2}{2} + \frac{x^3}{3} + \frac{x^4}{4}...



e sostituendo l'ultimo termine col suo valore si ottiene:

\Psi(x) = x - \sum_p \frac{x^p}{p}+ \frac{1}{2} log \frac{x^2}{x^2-1} - log 2 \pi [59]


Formula principale di Riemann

 Nel suo lavoro, Riemann dimostrò (e successivamente, in maniera più rigorosa, von Mangoldt) che, per x>1:
J(x)= Li(x) - \sum_\rho Li(x^\rho) - log\ 2 + \int_{x}^\infty \frac{dt}{t(t^2-1)log(t)}  [60]

In questa formula ρ varia tra le soluzioni non banali di  ζ.
Osservando i due membri, a sinistra abbiamo J(x) che come abbiamo visto è la funzione che inizia da 0 per x=0 e aumenta di uno dopo ogni numero p primo, di 1/2 dopo ogni quadrato di numero primo e di 1/n per ogni potenza n-ma di un numero primo. Analiticamente si ha che

J(x) = \sum_n \frac{\pi(x^{1/n})}{n} [61]


Li(x) è il logaritmo integrale di x, ed il risultato della funzione è sempre reale anche se i vari ρ sono numeri complessi, poiché le parti immaginarie degli zeri sono simmetriche rispetto all'origine.



Valori noti di ζ(s)

Tra i valori noti di ζ(s) si segnalano
ζ(0) = -1/2
ζ(-1) =  -1/12



Bibliografia, in ordine di rilevanza

[1] Riemann's Z function di H.M. Edwards
[3] RiemannPaper di Bernhard Riemann, tradotto da David R. Wilkins
[4] L'ossessione dei numeri primi di John Derbyshire
[5] L'enigma dei numeri primi di Marcus du Satoy
[6] Breve storia dei numeri primi di Alessandro Zaccagnini
[7Mer] Il teorema dei numeri primi di Flavio Cimolin
[9] Il teorema dei numeri primi  di Mauro Davide Ferrario

   

- Nessun commento:
Iscriviti a: Post (Atom)

Refactoring: improving modularization

  Modularità In generale, per modularità si intende la misura in cui un sistema può essere decomposto e ricombinato. La modularizzazione è a...