Elementary and Algorithmic Number Theory

Subject to modification!

Subject to modification! Week [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15][16]

Week

Day

Materials to be covered

Suggested exercises/reading

1

Jan 11

Notations and Unique factorizations in P.I.D.

[I-R] Chapter I113,14,30,31

 

Jan 13

Some properties of primes and some arithmetic functions

[I-R] Chapter 2 8,9,10,11,12,13,14,15

2

.

Jan 18

Congruences

[I-R] Chapter 3

5,6,11,12,15,17,19

 

Jan 20

Primitive roots and the group structure of U(Z/nZ)

[I-R]  Chapter 4

5,7,8,10,18,22,23

3

Jan 25

$n$-th power residue

 

 

Jan 27

Public key cryptosystems and number theory, Prime distributions

RSA numbers and RSA security

4

Feb 1

Prime number theorem, some conjectures related to primes,  Mersenne primes

Homework on Mersenne primes

Reading [Kim]

 

Feb 3

Time estimate for doing arithmetic

Homework on time estimation

5

Feb 8

Some factorization algorithms I: Pollard’s rho/p-1 factorization algorithms

Reading [B-R] below

 

Feb 10

Factorization algorithms II: Fermat factorization and continued fraction  factorization

Guess and try to prove the continued fraction expansion of the irrational number e=2.71828….

Reading [Dys]

6

Feb 15

Quadratic reciprocity

[I-R] Chapter 5

4,5,6,7,8,9,10,11,18,22,25,26

 

Feb 17

Quadratic reciprocity and quadratic sieve method factorization

 

7

Feb 22

Quadratic Guass Sum

 [I-R] Chapter 6

1,2,3,4,5,8,12,13

 

Feb 24

Quadratic Guass Sum

Homework on Fourier transformation

8

Mar 1

Finite fields

 

 

Mar 3

Primes is in P

 Reading Agrawal’s presentation at ISU

[Gr]

9

Mar 8

Guass and Jacobi sums

 

 

Mar 10

Guass and Jacobi sums

[I-R]Chapter8

1,2,3,4,5,9,13,16,17,18

10

Spring break

 

 

11

Mar 22

Guass and Jacobi sums

 

 

Mar 24

Equations over finite fields

[I-R]Chapter 10

1,2,7,8,9

12

Mar 29

Equations over finite fields

 

 

Mar 31

Zeta functions

 

13

Apr 5

Riemann-Zeta function

 

 

Apr 7

Elliptic curves-Introduction I Cubic equations

 

14

Apr 12

Elliptic curves-Introduction II Weierstrass equation

 

15

Apr 19

Elliptic curves-Introduction III Elliptic curves over Q

 Homework on elliptic curve

 

Apr 21

Lenstra’s elliptic curve factorization, Elliptic curve cryptography

 

16

Apr 26

 

 

 

Apr 28

 

  

References

[I-R] Ireland, K and Rosen, M. A classical introduction to Modern Number Theory GTM 84, Springer-Verlag

[Kim] Kim, Y-C Note on the Prime Number Theorem,http://lanl.arxiv.org/abs/math.NT/0502062

 [B-P] Brent, .P and Pollard,J.M. The factorization of F_8 Math. Comp. 36 (1981), no. 154, 627—630

[Dys] Dyson, F. The sixth Fermat number and palindromic continued fractions. Enseign. Math. (2) 46 (2000), no. 3-4, 385--389.

[Cor] Corless, R. M. Continued fractions and chaos.

[Gr] Granville,A. It is easy to determine whether a given integer is prime, Bull. Amer. Math. Soc. 42 (2005), 3-38