Matematica | NUMBER THEORY AND CRYPTOGRAPHY

cod. 0522200021

NUMBER THEORY AND CRYPTOGRAPHY

	0522200021
	DIPARTIMENTO DI MATEMATICA
	EQF7
	MATHEMATICS
	2022/2023

CURRICULUM APPLICATION-ORIENTED MATHEMATICS

	YEAR OF COURSE 1
	YEAR OF DIDACTIC SYSTEM 2018
	SPRING SEMESTER

TEACHING UNITS

	SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
	MAT/02	6	48	LESSONS	SUPPLEMENTARY COMPULSORY SUBJECTS

EXAMS

	Exam	Date	Session
	TEORIA DEI NUMERI E CRITTOGRAFIA	13/06/2023 - 12:00	SESSIONE ORDINARIA
	TEORIA DEI NUMERI E CRITTOGRAFIA	11/07/2023 - 12:00	SESSIONE ORDINARIA

	Objectives
	AIM OF THE COURSE IS THE STUDY OF ELEMENTARY NUMBER THEORY AND BASIC CONCEPTS IN CRYPTOGRAPHY. IN PARTICULAR WE WILL CONSIDER CONGRUENCES, THE GROUP OF UNITS, QUADRATIC RESIDUES, ARITHMETIC FUNCTIONS, PUBLIC-KEY CRYPTOGRAPHIC SYSTEMS. EXAMPLES AND APPLICATIONS WILL HELP STUDENTS TO BE ACQUAINTED TO THESE THEORIES, TO THEIR TECHNIQUES, TO THEIR MOTIVATIONS, ALSO IN VIEW OF POSSIBLE FUTURE DEVELOPMENTS.

AIM OF THE COURSE IS THE STUDY OF ELEMENTARY NUMBER THEORY AND BASIC CONCEPTS IN CRYPTOGRAPHY. IN PARTICULAR WE WILL CONSIDER CONGRUENCES, THE GROUP OF UNITS, QUADRATIC RESIDUES, ARITHMETIC FUNCTIONS, PUBLIC-KEY CRYPTOGRAPHIC SYSTEMS.
EXAMPLES AND APPLICATIONS WILL HELP STUDENTS TO BE ACQUAINTED TO THESE THEORIES, TO THEIR TECHNIQUES, TO THEIR MOTIVATIONS, ALSO IN VIEW OF POSSIBLE FUTURE DEVELOPMENTS.

	Prerequisites
	THE CONTENTS OF BASIC ALGEBRA

	Contents
	NUMBER THEORY (38 HOURS): - PRIME NUMBERS, THEIR DISTRIBUTION, THE SIEVE OF ERATOSTHENES. - FERMAT NUMBERS, FERMAT PRIMES, MERSENNE NUMBERS, MERSENNE PRIMES. - FERMATS FACTORIZATION METHOD. - LINEAR DIOPHANTINE EQUATIONS, NECESSARY AND SUFFICIENT CONDITIONS FOR EXISTING SOLUTIONS AND HOW TO CALCULATE THEM. - CONGRUENCES IN THE RING OF INTEGERS, THE RING Z_N. COMPLETE SETS OF RESIDUES. - DIVISIBILITY CRITERIA, THE PROOF BY NINE. PALINDROMIC NUMBERS, TRIANGULAR NUMBERS. - PROOFS OF FERMAT'S LITTLE THEOREM, WILSON'S THEOREM, EULER'S THEOREM. - PRIMALITY-TESTING AND FACTORISATION. POLLARD'S "P - 1" METHOD. - LINEAR CONGRUENCES, SIMULTANEOUS LINEAR CONGRUENCES. THE CHINESE REMAINDER THEOREM, ITS EXTENSION. - PSEUDOPRIMES AND CARMICHAEL NUMBERS. NUMBERS PASSING THE BASE P TEST. - LAGRANGE'S THEOREM FOR POLYNOMIALS. A PRIMALITY TEST WITH POLYNOMIALS. - ARITHMETIC FUNCTIONS, MULTIPLICATIVE FUNCTIONS. THE DIVISOR FUNCTIONS. PERFECT NUMBERS. EULER'S FUNCTION. MÖBIUS FUNCTION, MÖBIUS INVERSION FORMULA. DIRICHLET PRODUCT. - THE GROUP OF UNITS, PRIMITIVE ROOTS. THE ALGEBRAIC STRUCTURE OF THE GROUP OF UNITS. THE UNIVERSAL EXPONENT. CHARACTERIZATION OF CARMICHAEL NUMBERS. - QUADRATIC CONGRUENCES, THE GROUP OF QUADRATIC RESIDUES. THE LEGENDRE SYMBOL, EULER'S CRITERION, GAUSS' LEMMA. THE LAW OF QUADRATIC RECIPROCITY. QUADRATIC RESIDUES FOR ARBITRARY MODULI. CRIPTOGRAPHY (10 HOURS): - GENERALITIES ON CRIPTOGRAPHY. JULIUS CAESAR'S CIPHERS, AFFINE CIPHERS, HILL CIPHERS, MONOALPHABETIC AND POLYALPHABETIC CIPHERS. VIGENÈRE CIPHER. - DISCRETE LOGARITHM. BABY- STEP GIANT-STEP ALGORITHM. - PUBLIC KEY CIPHERS, DIFFIE-HELLMAN KEY EXCHANGE, DIGITAL SIGNATURES, THE TWO PADLOCKS METHOD, MASSEY-OMURA CIPHER, ELGAMAL CIPHER. - THE KNAPSACK PROBLEM, SUPERASCENDING SEQUENCES, MERKLE-HELLMAN KNAPSACK CRYPTOSYSTEM. - THE RSA SYSTEM.

Contents

NUMBER THEORY (38 HOURS):
- PRIME NUMBERS, THEIR DISTRIBUTION, THE SIEVE OF ERATOSTHENES. - FERMAT NUMBERS, FERMAT PRIMES, MERSENNE NUMBERS, MERSENNE PRIMES.
- FERMATS FACTORIZATION METHOD.
- LINEAR DIOPHANTINE EQUATIONS, NECESSARY AND SUFFICIENT CONDITIONS FOR EXISTING SOLUTIONS AND HOW TO CALCULATE THEM.
- CONGRUENCES IN THE RING OF INTEGERS, THE RING Z_N. COMPLETE SETS OF RESIDUES.
- DIVISIBILITY CRITERIA, THE PROOF BY NINE. PALINDROMIC NUMBERS, TRIANGULAR NUMBERS.
- PROOFS OF FERMAT'S LITTLE THEOREM, WILSON'S THEOREM, EULER'S THEOREM.
- PRIMALITY-TESTING AND FACTORISATION. POLLARD'S "P - 1" METHOD.
- LINEAR CONGRUENCES, SIMULTANEOUS LINEAR CONGRUENCES. THE CHINESE REMAINDER THEOREM, ITS EXTENSION.
- PSEUDOPRIMES AND CARMICHAEL NUMBERS. NUMBERS PASSING THE BASE P TEST.
- LAGRANGE'S THEOREM FOR POLYNOMIALS. A PRIMALITY TEST WITH POLYNOMIALS.
- ARITHMETIC FUNCTIONS, MULTIPLICATIVE FUNCTIONS. THE DIVISOR FUNCTIONS. PERFECT NUMBERS. EULER'S FUNCTION. MÖBIUS FUNCTION, MÖBIUS INVERSION FORMULA. DIRICHLET PRODUCT.
- THE GROUP OF UNITS, PRIMITIVE ROOTS. THE ALGEBRAIC STRUCTURE OF THE GROUP OF UNITS. THE UNIVERSAL EXPONENT. CHARACTERIZATION OF CARMICHAEL NUMBERS.
- QUADRATIC CONGRUENCES, THE GROUP OF QUADRATIC RESIDUES. THE LEGENDRE SYMBOL, EULER'S CRITERION, GAUSS' LEMMA. THE LAW OF QUADRATIC RECIPROCITY. QUADRATIC RESIDUES FOR ARBITRARY MODULI.

CRIPTOGRAPHY (10 HOURS):
- GENERALITIES ON CRIPTOGRAPHY. JULIUS CAESAR'S CIPHERS, AFFINE CIPHERS, HILL CIPHERS, MONOALPHABETIC AND POLYALPHABETIC CIPHERS. VIGENÈRE CIPHER.
- DISCRETE LOGARITHM. BABY- STEP GIANT-STEP ALGORITHM.
- PUBLIC KEY CIPHERS, DIFFIE-HELLMAN KEY EXCHANGE, DIGITAL SIGNATURES, THE TWO PADLOCKS METHOD, MASSEY-OMURA CIPHER, ELGAMAL CIPHER.
- THE KNAPSACK PROBLEM, SUPERASCENDING SEQUENCES, MERKLE-HELLMAN KNAPSACK CRYPTOSYSTEM.
- THE RSA SYSTEM.

	Teaching Methods
	LECTURES. ATTENDANCE TO CLASS LESSONS IS STRONGLY RECOMMENDED.

	Verification of learning
	THE AIM OF THE EXAMINATION IS TO EVALUATE THE FAMILIARITY OF THE STUDENT WITH THE THEORY OF NUMBERS AND CRYPTOGRAPHY. THE EXAMINATION IS ORAL. THE STUDENT HAS TO TALK ABOUT EXAMPLES AND THE PRINCIPAL PROPERTIES OF THE ELEMENTARY NUMBER THEORY WITH SOME TOPICS IN CRIPTOGRAPHY. HE HAS TO SOLVE SOME EXERCISES.

	Texts
	G. A. JONES, J. M. JONES - ELEMENTARY NUMBER THEORY, SPRINGER, 1998 (RIST. 2003). M. W. BALDONI, C. CILIBERTO, G. M. PIACENTINI CATTANEO - ARITMETICA, CRITTOGRAFIA E CODICI , SPRINGER, 2006. S. LEONESI, C. TOFFALORI - NUMERI E CRITTOGRAFIA, SPRINGER, 2006.