Download Aritmetica, crittografia e codici by W.M. Baldoni, C. Ciliberto, G.M. Piacentini Cattaneo PDF

By W.M. Baldoni, C. Ciliberto, G.M. Piacentini Cattaneo

Il quantity potrà essere utile ai docenti che intendano svolgere un corso su questi argomenti, los angeles cui presenza sempre più viene richiesta nei corsi di laurea di matematica, fisica, informatica, ingnegneria.

Table of Contents

Cover

Aritmetica, crittografia e codici

ISBN 10 8847004551 ISBN thirteen 9788847004559

Introduzione

Indice

1 Qualche richiamo sui numeri

1.1 Principio di induzione completa
1.2 Il concetto di ricorsivit�
1.2.1 I numeri di Fibonacci
1.2.2 Altri esempi di dinamica di popolazioni
1.2.3 los angeles torre di Hanoi: un caso lineare non omogeneo
1.3 L'algoritmo di Euclide
1.3.1 los angeles divisione
1.3.2 Il massimo comun divisore
1.3.3 L'identit� di B�zout
1.3.4 Equazioni lineari diofantee
1.3.5 Anelli euclidei
1.3.6 Polinomi
1.4 Contare in basi diverse
1.4.1 l. a. rappresentazione posizionale dei numeri
1.4.2 l. a. base 2
1.4.3 Le quattro operazioni in base 2
1.4.4 Numeri interi in base qualunque
1.4.5 Rappresentazione dei numeri reali in base qualunque
1.5 Frazioni continue
1.5.1 Frazioni proceed semplici finite e numeri razionali
1.5.2 Frazioni proceed semplici endless e numeri irrazionali
1.5.3 Frazioni proceed periodiche
1.5.4 Modello geometrico delle frazioni continue
1.5.5 L'approssimazione di irrazionali mediante i convergenti
1.5.6 Frazioni proceed ed equazioni diofantee

2 Complessit� computazionale

2.1 Il concetto di complessit� computazionale
2.2 Il simbolo O
2.3 pace polinomiale, pace esponenziale
2.4 Complessit� delle operazioni elementari
2.5 Algoritmi e complessit�
2.5.1 Complessit� dell'algoritmo di Euclide
2.5.2 Dalla scrittura binaria a quella decimale: complessit�
2.5.3 Complessit� delle operazioni tra polinomi
2.5.4 Un algoritmo pi� efficiente according to los angeles moltiplicazione
2.5.5 Metodo di Ruffini-Horner

3 Dall'infinito al finito

3.1 Congruenze: top propriet�
3.2 top applicazioni delle congruenze
3.2.1 los angeles prova del nove
3.2.2 Criteri di divisibilit�
3.3 Congruenze lineari
3.3.1 Potenze modulo n
3.4 Il Teorema cinese dei resti
3.5 Esempi
3.5.1 Il calendario perpetuo
3.5.2 Girone all'italiana

4 Finito non basta: problemi di fattorizzazione

4.1 Numeri primi
4.1.1 Il Teorema Fondamentale dell'Aritmetica
4.1.2 Distribuzione dei numeri primi
4.1.3 Il crivello di Eratostene
4.2 Numeri primi e congruenze
4.2.1 Il calcolo della funzione di Eulero
4.2.2 Il Piccolo Teorema di Fermat
4.2.3 Il teorema di Wilson
4.3 Rappresentazione in base qualunque dei numeri razionali
4.4 Primi di Fermat, primi di Mersenne e numeri perfetti
4.4.1 Fattorizzazione di interi della forma bn � 1
4.4.2 Numeri primi di Fermat
4.4.3 Numeri primi di Mersenne
4.4.4 Numeri perfetti
4.5 Fattorizzazione in un dominio di integrit�
4.5.1 Elementi primi e irriducibili in un anello
4.5.2 Domini fattoriali
4.5.3 Anelli noetheriani
4.5.4 Fattorizzazione di polinomi su un campo
4.5.5 Fattorizzazione di polinomi su un anello fattoriale
4.5.6 Polinomi a coefficienti razionali o interi
4.6 L'interpolazione di Lagrange e applicazioni
4.7 Il metodo di fattorizzazione di Kronecker

5 Campi finiti e congruenze polinomiali

5.1 Un po' di teoria dei campi
5.1.1 Estensioni di campi
5.1.2 Estensioni algebriche
5.1.3 Campo di riducibilit� completa di un polinomio
5.1.4 Radici dell'unit�
5.1.5 Chiusura algebrica
5.1.6 Campi finiti e loro sottocampi
5.1.7 Automorfism dei campi finiti
5.1.8 Polinomi irriducibili su Zp
5.1.9 Campo F4 di ordine quattro
5.1.10 Campo F8 di ordine otto
5.1.11 Campo F16 di ordine sedici
5.1.12 Campo F9 di ordine nove
5.1.13 Sui generatori di un campo finito
5.1.14 Complessit� del calcolo in un campo finito
5.2 Congruenze polinomiali non lineari
5.2.1 Equazioni di secondo grado
5.2.2 Residui quadratici
5.2.3 Il simbolo di Legendre e sue propriet�
5.2.4 l. a. legge di reciprocit� quadratica
5.2.5 Il simbolo di Jacobi
5.2.6 Un algoritmo in line with il calcolo delle radici quadrate

6 try di primalit� e di fattorizzazione

6.1 Numeri pseudoprimi e try out probabilistici
6.1.1 Numeri pseudoprimi
6.1.2 try probabilistici e try deterministici
6.1.3 Un primo try out di primalit� probabilistico
6.1.4 Numeri di Carmichael
6.1.5 Pseudoprimi di Eulero
6.1.6 Il try probabilistico di primalit� di Solovay-Strassen
6.1.7 Pseudoprimi forti
6.1.8 try out probabilistico di primalit� di Miller-Rabin
6.2 Radici primitive
6.2.1 Radici primitive e indice
6.2.2 Ancora sul try out di Miller-Rabin
6.3 Un try di primalit� deterministico polinomiale
6.4 Metodi di fattorizzazione
6.4.1 Il metodo di fattorizzazione di Fermat
6.4.2 Generalizzazione del metodo fattorizzazione di Fermat
6.4.3 Il metodo delle basi di fattorizzazione
6.4.4 Fattorizzazione e frazioni continue
6.4.5 L'algoritmo del crivello quadratico
6.4.6 Il metodo
6.4.7 Variazione del metodo

7 Segreti... e bugie

7.1 I cifrari classici
7.1.1 Le top scritture segrete nella storia
7.2 L'analisi del testo cifrato
7.2.1 Macchinari according to cifrare
7.3 Impostazione matematica di un crittosistema
7.4 Alcuni cifrari classici basati sull'aritmetica modulare
7.4.1 Cifrari affini
7.4.2 Cifrari con matrici o di Hill
7.5 L'idea di base della crittografi a chiave pubblica
7.5.1 Un algoritmo in keeping with il calcolo dei logaritmi discreti
7.6 Problema dello zaino e applicazioni alla crittografi
7.6.1 Cifrario a chiave pubblica basato sul problema dello zaino o di Merkle-Hellman
7.7 Il sistema RSA
7.7.1 Accesso al sistema RSA
7.7.2 Invio di un messaggio cifrato con il sistema RSA
7.7.3 Decifratura di un messaggio cifrato con il sistema RSA
7.7.4 Perch� ha funzionato?
7.7.5 Autenticazione delle enterprise con il sistema RSA
7.7.6 Un commento sulla sicurezza del sistema RSA
7.8 Varianti del sistema RSA e oltre
7.8.1 Scambio di chiavi private
7.8.2 Il crittosistema di Elgamal
7.8.3 Zero-knowledge evidence: ovvero convincere che si conosce un risultato senza svelarne il contenuto o l. a. dimostrazione
7.8.4 Nota storica
7.9 Crittografi e curve ellittiche
7.9.1 Crittografi in un gruppo
7.9.2 Curve algebriche in un piano affine numerico
7.9.3 Rette e curve razionali
7.9.4 Curve iperellittiche
7.9.5 Curve ellittiche
7.9.6 Legge di gruppo sulle curve ellittiche
7.9.7 Curve ellittiche su R, C e Q
7.9.8 Curve ellittiche su campi finiti
7.9.9 Curve ellittiche e crittografi
7.9.10 Il metodo di fattorizzazione p 1 di Pollard

8 Trasmettere senza. . . paura di sbagliare

8.1 Auguri di buon compleanno!
8.2 Fotografando nello spazio o lanciando monete, arriviamo ai codici
8.3 Codici che correggono gli errori
8.4 Limitazioni sugli invarianti
8.5 Codici lineari
8.6 Codici ciclici
8.7 Codici di Goppa

9 Il futuro � gi� presente: l. a. crittografia quantistica

9.1 Una prima incursione nel mondo quantistico: l'esperimento di Young
9.2 Il computing device quantistico
9.3 Il cifrario di Vernam
9.4 Un breve glossario di meccanica quantistica
9.5 Crittografi quantistica

10 Soluzione di alcuni esercizi

10.1 Esercizi del Capitolo 1
10.2 Esercizi del Capitolo 2
10.3 Esercizi del Capitolo 3
10.4 Esercizi del Capitolo 4
10.5 Esercizi del Capitolo 5
10.6 Esercizi del Capitolo 6
10.7 Esercizi del Capitolo 7
10.8 Esercizi del Capitolo 8
10.9 Esercizi del Capitolo 9

Riferimenti bibliografici

Indice analitico

Show description

Read or Download Aritmetica, crittografia e codici PDF

Similar combinatorics books

Coxeter Matroids

Matroids look in various components of arithmetic, from combinatorics to algebraic topology and geometry. This principally self-contained textual content presents an intuitive and interdisciplinary remedy of Coxeter matroids, a brand new and gorgeous generalization of matroids that is in accordance with a finite Coxeter workforce. Key subject matters and features:* Systematic, sincerely written exposition with plentiful references to present learn* Matroids are tested by way of symmetric and finite mirrored image teams* Finite mirrored image teams and Coxeter teams are constructed from scratch* The Gelfand-Serganova theorem is gifted, making an allowance for a geometrical interpretation of matroids and Coxeter matroids as convex polytopes with sure symmetry homes* Matroid representations in constructions and combinatorial flag types are studied within the ultimate bankruptcy* Many routines all through* very good bibliography and indexAccessible to graduate scholars and study mathematicians alike, "Coxeter Matroids" can be utilized as an introductory survey, a graduate path textual content, or a reference quantity.

Algorithmics of Matching Under Preferences

Matching issues of personal tastes are throughout us: they come up while brokers search to be allotted to each other at the foundation of ranked personal tastes over strength results. effective algorithms are wanted for generating matchings that optimise the pride of the brokers in line with their choice lists.

Difference Sets: Connecting Algebra, Combinatorics, and Geometry

Distinction units belong either to staff idea and to combinatorics. learning them calls for instruments from geometry, quantity conception, and illustration conception. This ebook lays a origin for those subject matters, together with a primer on representations and characters of finite teams. It makes the examine literature on distinction units obtainable to scholars who've studied linear algebra and summary algebra, and it prepares them to do their very own examine.

Extra info for Aritmetica, crittografia e codici

Example text

Osserviamo che 0 ≤ r < b per costruzione e q `e unico perch´e `e il minimo intero il cui prodotto per b non supera a. Di conseguenza anche r `e unico. Se b `e negativo, per quanto gi` a dimostrato, si ha, in modo unico, a = q ′ (−b) + r, con 0 ≤ r < −b = |b|. Basta allora porre q = −q ′ per trovare i due numeri q ed r richiesti, la cui unicit` a segue da quella gi` a provata nel caso b > 0. 1) permette dunque di determinare gli interi q ed r a partire da a e b, e prende anche il nome di divisione di a per b.

Infine 1 + 2 = 1 0. In definitiva, si ha 40 1 Qualche richiamo sui numeri 11 221+ 12 1010 Analogamente nel caso della moltiplicazione. Ad esempio il Lettore potr` a verificare che (221)3 · (12)3 = (11122)3 . 5 Rappresentazione dei numeri reali in base qualunque Non solo i numeri interi ma pi` u in generale i numeri reali si possono rappresentare in una fissata base β. 4. Sia a un numero reale tale che 0 ≤ a < 1 e sia β > 1 un intero. 31) dove i coefficienti sono interi ci tali che 0 ≤ ci ≤ β − 1.

Al polinomio nullo, ossia al polinomio che ha tutti i coefficienti uguali a zero, non si attribuisce alcun grado. 20) con la successione di elementi di A { a0 , a1 , . . , an , 0, 0, . . }, che assume, a partire da un certo punto in poi il valore 0. Si usa porre ai = 0 per i ogni i > n e si pu` o anche scrivere p(x) = ∞ i=0 ai x , tenendo presente che comunque la somma `e finita. In generale quindi, usando il simbolo di uguaglianza per indicare la identificazione sopra descritta, si ha a = {a, 0, 0, 0, .

Download PDF sample

Rated 4.12 of 5 – based on 33 votes