2. Professors
  3. LONGOBARDI Patrizia
  4. Teaching

NUMBER THEORY AND CRYPTOGRAPHY

Patrizia LONGOBARDI NUMBER THEORY AND CRYPTOGRAPHY

0522200021
DEPARTMENT OF MATHEMATICS
EQF7
MATHEMATICS
2024/2025

YEAR OF DIDACTIC SYSTEM 2018
SPRING SEMESTER
CFUHOURSACTIVITY
648LESSONS
PATRIZIA LONGOBARDI T Curriculum
Objectives
GENERAL PURPOSE:
THE AIM OF THE COURSE IS THE STUDY OF CLASSICAL PROPERTIES OF INTEGER NUMBERS AND THEIR APPLICATIONS TO CRYPTOGRAPHY.

KNOWLEDGE AND UNDERSTANDING:
THE PRIMARY OBJECTIVE OF THE COURSE IS TO EXPLAIN CLASSICAL PROPERTIES OF INTEGER NUMBERS, HIGHLIGHTING THEIR APPLICATIONS, PROOFS METHODOLOGIES AND RECENT DEVELOPMENTS, AND TO INTRODUCE BASIC CRYPTOGRAPHY CONCEPTS, WITH PARTICULAR ATTENTION TO PUBLIC KEY CRYPTOGRAPHY AND THE FUNDAMENTAL ROLE PLAYED IN IT FROM PROPERTIES OF INTEGER NUMBERS.
THE STUDENT, WITH THE HELP OF NUMEROUS EXAMPLES AND EXERCISES:
- WILL EXPLAIN THE PROPERTIES AND CHARACTERIZATIONS OF PRIME INTEGER NUMBERS, WITH INFORMATION ALSO ON THEIR DISTRIBUTION AND ON SIEVES;
- WILL STUDY FAMOUS CRITERIA OF PRIMALITY AND DIVISIBILITY, AND METHODS OF FACTORIZATION OF AN INTEGER;
- WILL KNOW NOTABLE CLASSES OF INTEGER NUMBERS, SUCH AS FOR EXAMPLE THOSE OF FERMAT NUMBERS, MERSENNE NUMBERS, PSEUDOPRIMES, CARMICHAEL NUMBERS, PERFECT NUMBERS;
- WILL BE INTRODUCED TO THE STUDY OF DIOPHANTIC EQUATIONS;
- WILL RESUME THE STUDY OF CONGRUENCES IN THE RING OF INTEGERS, FINDING THE FERMAT-EULER THEOREM AND WILSON'S THEOREM, AND DISCOVERING FURTHER PROOFS;
- WILL FULLY ADDRESS THE STUDY OF SYSTEMS OF CONGRUENTIAL EQUATIONS, STARTING FROM THE LINEAR ONES;
- WILL KNOW REMARKABLE ARITHMETIC FUNCTIONS, USUALLY MULTIPLICATIVE, AND WILL DEEPEN THE STUDY OF THE MÖBIUS FUNCTION WITH THE RELATIVE INVERSION FORMULA;
- WILL DETERMINE THE STRUCTURE OF THE GROUP OF THE UNITS OF EACH QUOTIENT OF THE RING OF INTEGERS AND THAT OF THE GROUP OF QUADRATIC RESIDUES;
- WILL STUDY SOME FAMOUS SYMMETRIC KEY CODES, WILL ADDRESS THE PROBLEM OF THE DISCRETE LOGARITHM, IN PARTICULAR CONSIDERING THE BABY STEP-GIANT STEP ALGORITHM;
- WILL FOCUS ON THE MAIN PUBLIC KEY CODES, IN PARTICULAR THE REMARKABLE R.S.A. AND THE MERKLE-HELLMAN CODE LINKED TO THE SUPERGROWING BACKPACK PROBLEM.

ABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING:
THE OBJECTIVE OF THE TEACHING IS TO MAKE THE STUDENT ABLE TO:
- STATE IN A CORRECT AND RIGOROUS WAY DEFINITIONS AND THEOREMS REGARDING THE CONTENTS OF THE COURSE, AND PRECISELY RECONSTRUCTE THE RELATIVE PROOFS;
- STUDY SYSTEMS OF CONGRUENTIAL EQUATIONS;
- DETERMINE THE STRUCTURE OF THE GROUP OF INVERTIBLE CLASSES OF INTEGER MODULE A POSITIVE INTEGER;
- RECOGNIZE IF AN INTEGER IS A QUADRATIC RESIDUE;
- DEAL WITH PROBLEMS RELATING TO NUMBERS WITH INDEPENDENCE, IDENTIFYING THE RIGHT FORMALIZATION AND THE MOST SUITABLE METHODOLOGY FOR THE RESOLUTION;
- SET UP AND SOLVE COMPUTATIONAL PROBLEMS, SIMPLIFYING CALCULATIONS WITH THE HELP OF STUDIED RESULTS AND METHODS;
- APPLY NUMBER THEORY TOOLS TO CRYPTOGRAPHY AND ALSO TO OTHER DISCIPLINES.

INDEPENDENT JUDGMENTS:
THE STUDENT WILL BE GUIDED TO LEARN IN A CRITICAL AND RESPONSIBLE MANNER EVERYTHING THAT IS ILLUSTRATED IN THE CLASSROOM AND TO IMPROVE THEIR JUDGMENT SKILLS ALSO THROUGH THE STUDY OF THE INDICATED EDUCATIONAL MATERIALS.
THE STUDENT WILL BE ABLE TO ASSESS THE CORRECTNESS OF PROPOSITIONS, IDENTIFYING APPROPRIATE EXAMPLES AND PROVING THEM WITH RIGOROUS ARGUMENTATION, OR REFUTING THEM WITH THE PRESENTATION OF COUNTEREXAMPLES. HE WILL BE ABLE TO ASSESS THE DIFFICULTY OF SOLVING A PROBLEM, EVEN HAVING AN ELEMENTARY FORMULATION.

COMMUNICATION SKILLS:
THE COURSE WILL TEND TO IMPROVE THE STUDENT'S ABILITY TO EXPRESS THE ACQUIRED KNOWLEDGE IN A CLEAR AND RIGOROUS WAY, HIGHLIGHTING WHICH ARE THE MOST SUITABLE METHODS TO USE AND THE MOST COMPLEX ASPECTS OF THE PROBLEM ADDRESSED.

LEARNING ABILITY:
THE STUDENT WILL BE ABLE TO:
- UNDERSTAND AND USE FORMAL MATHEMATICAL LANGUAGE;
- BUILD EXAMPLES AND/OR COUNTEREXAMPLES;
- SOLVE PROBLEMS RELATING TO THE TOPICS COVERED;
- UNDERSTAND, ANALYZE AND RECONSTRUCTE THE STRUCTURE OF MATHEMATICAL PROOFS;
- USE THE FUNDAMENTAL IDEAS OF SOME PROOFS EVEN IN CONTEXTS DIFFERENT FROM THOSE PROPOSED DURING THE COURSE.
THE ULTIMATE AIM OF THE COURSE IS TO DEVELOP A FLEXIBLE MENTALITY IN THE STUDENTS THAT ALLOWS THEM TO EASILY DEAL WITH NEW AND DIFFERENT PROBLEMS.
Prerequisites
THE CONTENTS OF THE ALGEBRA I/II AND ALGEBRA III COURSES.
Contents
NUMBER THEORY (38 HOURS):
- PRIME NUMBERS, OBSERVATIONS ON THEIR DISTRIBUTION, SIEVE OF ERATOSTHENE.
- FERMAT NUMBERS, FERMAT PRIMES. MERSENNE NUMBERS, MERSENNE PRIMES.
- FERMAT METHOD FOR FINDING DIVISORS OF A NATURAL NUMBER.
- LINEAR DIOPHANTINE EQUATIONS, NECESSARY AND SUFFICIENT CONDITIONS FOR SOLUTIONS TO EXIST AND THEIR DETERMINATION.
- REFERENCES ON CONGRUENCES IN THE RING OF INTEGERS. THE RING Z_N. COMPLETE SET OF RESIDUES MODULE AN INTEGER.
- DIVISIBILITY CRITERIA, 9 TEST. PALINDROME NUMBERS, TRIANGULAR NUMBERS.
- PROOF OF FERMAT'S "LITTLE THEOREM", WILSON'S THEOREM, EULER'S THEOREM.
- PRIMALITY CRITERIA. FACTORIZATION CRITERIA. POLLARD'S "P - 1" METHOD FOR FINDING DIVISORS OF AN INTEGER.
- LINEAR CONGRUENTIAL EQUATIONS, NECESSARY AND SUFFICIENT CONDITIONS FOR THE EXISTENCE OF SOLUTIONS AND METHODS TO DETERMINE THEM. CHINESE REMAINDER THEOREM, ITS GENERALIZATION.
- PSEUDOPRIMES AND CARMICHAEL NUMBERS. NUMBERS THAT "PASS THE TEST" FOR AN INTEGER.
- LINKS BETWEEN POLYNOMIALS WITH INTEGER COEFFICIENTS AND POLYNOMIALS WITH COEFFICIENTS IN Z_N. THE LAGRANGE THEOREM. A PRIMALITY CRITERION WITH POLYNOMIALS.
- ARITHMETIC FUNCTIONS, MULTIPLICATIVE FUNCTIONS. THE "NUMBER OF DIVIDERS" FUNCTION AND THE "SUM OF DIVIDERS" FUNCTION. PERFECT NUMBERS. THE EULER FUNCTION. THE MÖBIUS FUNCTION, THE MÖBIUS INVERSION FORMULA. THE DIRICHLET PRODUCT.
- THE GROUP OF Z_N UNITS. PRIMITIVE ROOTS. THE STRUCTURE OF THE GROUP OF Z_N UNITS. THE UNIVERSAL EXPONENT. CHARACTERIZATION OF CARMICHAEL NUMBERS.
- QUADRATIC CONGRUENCES, THE GROUP OF QUADRATIC RESIDUALS, LEGENDRE’S SYMBOL, THE EULER CRITERION, THE GAUSS LEMMA. THE LAW OF QUADRATIC RECIPROCITY. QUADRATIC RESIDUALS FOR ARBITRARY MODULES.
- INTRODUCTION ON THE SUMS OF SQUARES AND THE WARING PROBLEM, NECESSARY CONDITIONS FOR A NATURAL NUMBER TO BE THE SUM OF TWO OR THREE SQUARES.
- FERMAT'S "INFINITE DESCENT" METHOD, INTRODUCTION ON PYTHAGOREAN TRIPLES AND FERMAT'S LAST THEOREM.

CRYPTOGRAPHY (10 HOURS):
- GENERAL INFORMATION ON CRYPTOGRAPHY. CAESAR CIPHERES, AFFINI CIPHERES, MATRIX (OR HILL) CIPHERES, MONOALPHABETICAL AND POLYLPHABETIC CIPHRIES, THE VIGENÈRE CIPHER.
- THE DISCRETE LOGARITHM, THE BABY-STEP GIANT-STEP ALGORITHM.
- PUBLIC KEY CODES, THE DIFFIE-HELLMAN CRYPTO SYSTEM, THE DIGITAL SIGNATURE, THE DOUBLE PADLOCK METHOD, THE MASSEY-OMURA CRYPTO SYSTEM, THE ELGAMAL CRYPTO SYSTEM.
- THE BACKPACK PROBLEM, THE SUPERGROWING BACKPACK PROBLEM, THE MERKLE-HELLMAN PUBLIC KEY CIPHER.
- THE RSA SYSTEM.
Teaching Methods
FRONTAL LESSONS. ATTENDING THE COURSE, ALTHOUGH NOT MANDATORY, IS STRONGLY RECOMMENDED.
Verification of learning
THE EXAM IS AIMED AT ASSESSING AS A WHOLE THE KNOWLEDGE AND ABILITY TO UNDERSTAND THE CONCEPTS PRESENTED IN LESSONS, AS WELL AS THE ABILITY TO APPLY SUCH KNOWLEDGE IN THE STUDY OF NUMBER THEORY WITH ELEMENTS OF CRYPTOGRAPHY.
THE EXAM CONSISTS OF AN ORAL INTERVIEW. THE STUDENT WILL HAVE TO SHOW FAMILIARITY WITH THE CONCEPTS AND FUNDAMENTAL PROPERTIES OF ELEMENTARY NUMBER THEORY AND WITH SOME TOPICS OF CRYPTOGRAPHY, IN PARTICULAR PUBLIC KEY CRYPTOGRAPHY. THEY MUST ALSO BE ABLE TO SOLVE EXERCISES.
THE FINAL ASSESSMENT WILL BE EXPRESSED IN THIRTIETHS. LAUDE MAY BE AWARDED TO STUDENTS WHO DEMONSTRATE THEY ARE ABLE TO INDEPENDENTLY APPLY KNOWLEDGE AND SKILLS ACQUIRED EVEN IN CONTEXTS DIFFERENT THAN THOSE PROPOSED IN LESSONS.

Texts
G. A. JONES, J. M. JONES - ELEMENTARY NUMBER THEORY, SPRINGER, 1998 (REPRINT 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.
More Information
TEACHERS' EMAIL ADDRESS:
PLONGOBARDI@UNISA.IT
WEBSITE:
HTTPS://DOCENTI.UNISA.IT/00479
Lessons Timetable

  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2025-03-05]