Algorithms for Number Theory

Academic year

2025Year

Term

Second Semester

Course title

Algorithms for Number Theory

Class type

Lecture

Course title (ENG)

Algorithms for Number Theory

Class code・Class name・Teaching forms

Z1900025 Algorithms for Number Theory

Instructor

SAITO Seiken

Credits

2.0Credits

Day and Time

Thu.1Period

Campus

Hachioji Remote

Location

Relationship between diploma policies and this course

A) A high degree of specialized expertise　100%
B) The skills to use science and technology　0%
C) The ability to conduct research independently, knowledge pertaining to society and occupations, and sense of ethics required of engineers and researchers　0%
D) Creative skills in specific areas of specialization　0%

Goals and objectives

1.Understand the fundamentals of algorithms for continued fractions, prime factorization, and primality tests related to number theory.
2.Understand the mathematical principles of RSA cryptography, ElGamal cryptography, elliptic curve cryptography, etc.
3.Understand the mathematical foundations of number theory and related quantum algorithms and lattice-based cryptography.

Prerequisites

Preparation of congruence relations in number theory (e.g., finite fields) will facilitate understanding.
Students should also review linear algebra.

Some calculations may be performed using a computer.

Method Using AL・ICT

Not used

Class schedule

1.Extended Euclidean algorithm
2.Finite continued fractions
3.Infinite continued fractions
4.RSA (congruences, computation of RSA, etc.)
5.RSA attack with continued fractions
6. ElGamal encryption and discrete logarithm problems
7.Primality tests (Miller-Rabin's method)
8.Addition of points on elliptic curves
9.Elliptic curves on finite fields and the discrete logarithm problems
10.Elliptic curve cryptography
11.Quantum bits and quantum gates
12.Shor's algorithm
13.Quantum search (Grover's algorithm)
14.Introduction to lattice-based cryptography
15.Exercises on lattice-based cryptography

Evaluation

Students are required to submit a report on the problems presented in the lecture.

Feedback for students

I respond to your inquiries about submissions and exams via KU-LMS and email.

Textbooks

The textbook is not specified.
Handouts will be distributed.

Reference materials

Office hours and How to contact teachers for questions

Thursday 14:10〜15:10 (Laboratory Hachioji 1E-314)

Message for students

Please check KU-LMS as it may notify you of homeworks etc.

Course by professor with work experience

Not applicable

Work experience and relevance to the course content if applicable

Teaching profession course

Informatics Program

Syllabus data