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

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, l. a. 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 los angeles 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 in step with los angeles moltiplicazione
2.5.5 Metodo di Ruffini-Horner

3 Dall'infinito al finito

3.1 Congruenze: top propriet�
3.2 leading applicazioni delle congruenze
3.2.1 l. a. 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 keeping with il calcolo delle radici quadrate

6 try out di primalit� e di fattorizzazione

6.1 Numeri pseudoprimi e try out probabilistici
6.1.1 Numeri pseudoprimi
6.1.2 try out probabilistici e attempt 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 attempt probabilistico di primalit� di Solovay-Strassen
6.1.7 Pseudoprimi forti
6.1.8 attempt 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 major scritture segrete nella storia
7.2 L'analisi del testo cifrato
7.2.1 Macchinari in step with 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 according to 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: los angeles 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

Combinatorial Algorithms for Computers and Calculators (Computer science and applied mathematics)

During this publication Nijenhuis and Wilf speak about a number of combinatorial algorithms.
Their enumeration algorithms comprise a chromatic polynomial set of rules and
a everlasting review set of rules. Their lifestyles algorithms comprise a vertex
coloring set of rules that is in keeping with a normal go into reverse set of rules. This
backtrack set of rules is additionally utilized by algorithms which checklist the colorations of a
graph, record the Eulerian circuits of a graph, record the Hamiltonian circuits of a
graph and checklist the spanning bushes of a graph. Their optimization algorithms
include a community move set of rules and a minimum size tree set of rules. They
give eight algorithms which generate at random an association. those eight algo-
rithms can be utilized in Monte Carlo reviews of the houses of random
arrangements. for instance the set of rules that generates random timber will be prepared

Traffic Flow on Networks (Applied Mathematics)

This e-book is dedicated to macroscopic types for site visitors on a community, with attainable functions to motor vehicle site visitors, telecommunications and supply-chains. The speedily expanding variety of circulating vehicles in smooth towns renders the matter of site visitors regulate of paramount value, affecting productiveness, toxins, way of life and so on.

Introduction to combinatorial mathematics

Seminal paintings within the box of combinatorial arithmetic

Extra info for Aritmetica, crittografia e codici

Sample text

Ad esempio A = (1) e 0 = (0) sono ideali principali. Si noti che (x) = (y) se e solo se x e y sono associati (cfr. 46). Un anello commutativo si dice a ideali principali se ogni suo ideale `e principale. 13. Se A `e un dominio di integrit` a a ideali principali, allora per ogni coppia (a, b) di elementi non nulli di A esiste il M CD(a, b) e tale `e ogni generatore dell’ideale (a, b). Dimostrazione. Sia d un generatore dell’ideale (a, b). Poich´e a, b ∈ (a, b), `e chiaro che d divide sia a che b.

Cm+h cm+1 . . cm+h . . cm+1 . . cm+h . . che pi` u brevemente si scrive a − [a] = 0, c1 . . cm cm+1 . . cm+h . Le cifre cm+1 . . cm+h si dicono costituire il periodo di a = ak ak−1 . . a1 a0 , c1 c2 c3 . , le cifre c1 . . cm si dicono costituire l’antiperiodo. Se m = 0, ossia se non vi `e antiperiodo, a si dice periodico semplice, altrimenti si dice periodico misto. Ora torniamo al problema di capire come `e fatta la rappresentazione in base β dei numeri razionali. A tale scopo ci possiamo ovviamente ridurre a considerare numeri nell’intervallo (0, 1).

Ad esempio: 1 = 3 · 7 + (−4) · 5 = (−2) · 7 + 3 · 5. 10. Analizziamo ora un esempio per capire come funziona l’algoritmo euclideo per trovare una relazione di B´ezout. Nel far ci` o introdurremo una notazione particolarmente efficace sia nel caso in cui si voglia programmare l’algoritmo su un calcolatore, sia nel caso in cui si facciano i conti a mano. Vogliamo determinare una identit` a di B´ezout per il M CD(1245, 56). Seguendo l’algoritmo di Euclide si fanno i seguenti passaggi: 1245 = 56 · 22 + 13, 56 = 13 · 4 + 4, 13 = 4 · 3 + 1 , 4 = 1 · 4 + 0.

Download PDF sample

Rated 4.03 of 5 – based on 20 votes