Number Theory

Number Theory#

The Theory of Integers

Sections#

[ h ] PARI/GP

Goals

  • implement a program that factors large numbers with quadratic sieve

  • Unique Factorization

  • Euclid’s Algorithm

  • Primality

  • Congruences

  • RSA

  • Factorization Techniques

  • Pseudoprimes

  • Quadratic Reciprocity

  • Quadratic Sieve

  • Primitive Roots

  • Elliptic Curves

  • Number Field Sieve

  • the factorization of integers into primes, the testing of integers for primality

  • relative run-times and analytic number theory

Resources#

https://crypto.stanford.edu/pbc/notes/numbertheory/arith.html

Brilliant

  • [ b ] Even and Odd Numbers

  • [ b ] Strong Induction

more

YouTube#

My Lesson

  • [ y ] 07-29-2021 “Number Theory and Cryptography Complete Course | Discrete Mathematics for Computer Science”.

Richard E. Borcherds

  • [ y ] 01-13-2022 “Introduction to number theory lecture 1.”.

  • [ y ] 01-15-2022 “Introduction to number theory lecture 2: Survey.”.

  • [ y ] 01-17-2022 “Introduction to number theory lecture 3: Divisibility and Euclid’s algorithms.”.

  • [ y ] 01-18-2022 “Introduction to number theory lecture 4. More on Euclid’s algorithm”.

  • [ y ] 01-20-2022 “Introduction to number theory lecture 5. Primes.”.

Stand-up Maths

  • [ y ] 11-21-2024 “New divisibility rule! (30,000 of them)”.

  • [ y ] 10-30-2024 “How on Earth does ^.?$|^(..+?)\1+$ produce primes?”.

more

  • [ y ] 11-13-2023 Douglas Shamlin Jr. “Ultimate Large Numbers List 2024 - The Biggest Numbers Ever!!!”.

  • [ y ] 11-21-2023 Shefs of Problem Solving. “A number theory adventure - JBMO 2002 - P3”.

  • [ y ] 02-28-2019 Shannon “MATHCHICK” Myers. “Direct Proof and Counterexample V: Floor and Ceiling”.

Texts#

FAPT 1989 Bressoud, David M. Factorization and Primality Testing. Springer Undergraduate Texts in Mathematics.

PNCP 2005 Crandall, Richard & Carl Pomerance. Prime Numbers: A Computational Perspective. Springer.

SDCP 2006 Dasgupta, Sanjoy; Christos Papadimitriou; & Umesh Vazirani. Algorithms. McGraw-Hill.

DTHA 2008 Davenport, Harold. The Higher Arithmetic: An Introduction to the Theory of Numbers. Cambridge University Press.

NGAC 2008 Humphreys, J. F. & M. Y. Prest. Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.

FONT 1996 LeVeque, William J. Fundamentals of Number Theory. Dover.

KRDM 2018 Rosen, Kenneth. Discrete Mathematics and its Applications 8e. McGraw-Hill.

CENT 2023 [ h ] Vaughan, Robert. A Course of Elementary Number Theory. CMPSC/MATH 467 Factorization and Primality Testing. The Pennsylvania State University. [ book ]

TJOF 2013 Wagstaff Jr., Samuel S. The Joy of Factoring. AMS Student Mathematical Library.

Figures#

  • [ w ] 1730-1783 Bézout, Étienne

  • [ w ] 1950----- Bressoud, David

  • [ w ] 1879-1967 Carmichael, Robert

  • [ w ] 1950----- Cocks, Clifford

  • [ w ] 1947----- Cohen, Henri

  • [ w ] 1947-2012 Crandall, Richard

  • [ w ] 1805-1859 Dirichlet, Peter

  • [ w ] 1707-1783 Euler, Leonhard

  • [ w ] 1607-1665 Fermat, Pierre de

  • [ w ] 1777-1855 Gauss, Carl Friedrich

  • [ w ] 1865-1963 Hadamard, Jacques

  • [ w ] 1877-1947 Hardy, G. H.

  • [ w ] 1838-1922 Jordan, Camille

  • [ w ] --------- Lehman, R. Sherman

  • [ w ] 1842-1891 Lucas, Édouard

  • [ w ] 1944----- Pomerance, Carl

  • [ w ] 1887-1946 Poulet, Paul

  • [ w ] 1866-1962 Poussin, Charles Jean de la Vallée

  • [ w ] 1798-1861 Sarrus, Pierre Frédéric

  • [ w ] 1948----- Schroeppel, Richard

  • [ w ] 1945----- Vaughan, Robert

  • [ w ] 1945----- Wagstaff Jr., Samuel S.

Terms#

  • [ w ] Base Case

  • [ w ] Binet Formula

  • [ w ] Binomial

  • [ w ] Binomial Coefficient

  • [ w ] Binomial Theorem

  • [ w ] Cassini’s Identity

  • [ w ] Complete Induction

  • [ w ] Course of Values Induction

  • [ w ] Fibonacci Sequence

  • [ w ] Index Set

  • [ w ] Indexed Family

  • [ w ] Induction

  • [ w ] Induction Hypothesis

  • [ w ] Induction Step

  • [ w ] Iteration

  • [ w ] Iterative Method

  • [ w ] Linear Difference Equation

  • [ w ] Linear Recurrence Relation

  • [ w ] Linear Recurrence with Constant Coefficients

  • [ w ] Mathematical Induction

  • [ w ] Memoization

  • [ w ] Pascal’s Triangle

  • [ w ] Recurrence Relation - A recurrence relation is an equation that expresses each term of a sequence as a function of the preceding ones.

  • [ w ] Recursion

  • [ w ] Strong Induction

  • [ w ] Addition [ proofs ]

  • [ w ] Additive Function

  • [ w ] Aliquot Sum

  • [ w ] Arbitrary-Precision Arithmetic

  • [ w ] Arithmetic Function

  • [ w ] Arithmetic Precision

  • [ w ] Artin’s Conjecture on Primitive Roots

  • [ w ] Bézout’s Identity

  • [ w ] Binary GCD Algorithm

  • [ w ] Carmichael Number

  • [ w ] Chinese Hypothesis

  • [ w ] Chinese Remainder Theorem

  • [ w ] Chunking

  • [ w ] Collatz Conjecture

  • [ w ] Computational Number Theory

  • [ w ] Congruence of Squares

  • [ w ] Congruence Relation

  • [ w ] Coprime

  • [ w ] Cyclic Number

  • [ w ] Difference of Squares

  • [ w ] Diffie-Hellman Key Exchange

  • [ w ] Diophantine Approximation

  • [ w ] Diophantine Equation

  • [ w ] Dirichlet’s Approximation Theorem

  • [ w ] Dirichlet’s Theorem

  • [ w ] Divisibility rules

  • [ w ] Division Algorithm

  • [ w ] Divisor

  • [ w ] divisors, table

  • [ w ] Dixon’s Factorization Method

  • [ w ] Euclid’s Lemma

  • [ w ] Euclid’s Theorem

  • [ w ] Euclidean Algorithm

  • [ w ] Euclidean Division

  • [ w ] Euler’s Criterion

  • [ w ] Euler’s Totient Function

  • [ w ] Exponentiation by Squaring

  • [ w ] Extended Euclidean Algorithm

  • [ w ] Factor Base

  • [ w ] Fast Inverse Square Root

  • [ w ] Fast Library for Number Theory (FLINT)

  • [ w ] Fermat Factorization

  • [ w ] Fermat Number

  • [ w ] Fermat Pseudoprime

  • [ w ] Fermat’s Little Theorem [ proof ]

  • [ w ] Fermat’s Factorization Method

  • [ w ] Full Reptend Prime

  • [ w ] Fundamental Theorem of Algebra

  • [ w ] Fundamental Theorem of Arithmetic

  • [ w ] Galley Division

  • [ w ] Gauss’ Lemma

  • [ w ] General Number Field Sieve

  • [ w ] Golden Ratio Base

  • [ w ] Greatest Common Divisior (GCD)

  • [ w ] Greatest Element

  • [ w ] GNU Multiple Precision Arithmetic Library (GMP)

  • [ w ] Integer Factorization

  • [ w ] Integer Square Root

  • [ w ] Jacobi Symbol

  • [ w ] Jordan’s Totient Function

  • [ w ] L-Notation

  • [ w ] Lagrange’s Theorem

  • [ w ] Law of Quadratic Reciprocity

  • [ w ] Law of Quadratic Reciprocity, proofs

  • [ w ] Least Element

  • [ w ] Legendre Symbol

  • [ w ] Lehmer’s GCD Algorithm

  • [ w ] Linnik’s Theorem

  • [ w ] Long Division

  • [ w ] Lucas’ Theorem

  • [ w ] Machin-Like Formula

  • [ w ] Miller-Rabin Primality Test

  • [ w ] Modular Arithmetic

  • [ w ] Modular Exponentiation

  • [ w ] Modular Multiplicative Inverse

  • [ w ] Montgomery Multiplication

  • [ w ] Multiplication Algorithm

  • [ w ] Multiplicative Order

  • [ w ] Number Theory Library

  • [ w ] Ostrowski Numeration

  • [ w ] PARI/GP

  • [ w ] Pollard’s Kangaroo Algorithm

  • [ w ] Pollard’s Rho Algorithm

  • [ w ] Primality Test

  • [ w ] Prime Gap

  • [ w ] Prime Number Theorem

  • [ w ] Prime Omega Function

  • [ w ] Prime Power

  • [ w ] Prime Signature

  • [ w ] Prime, lists

  • [ w ] Prime-Counting Function

  • [ w ] Primitive Root Modulo n

  • [ w ] Primorial

  • [ w ] Probable Prime

  • [ w ] Pseudoprime

  • [ w ] Public-Key Cryptography

  • [ w ] Quadratic Residue

  • [ w ] Quadratic Sieve

  • [ w ] Quotient

  • [ w ] Rational Sieve

  • [ w ] Reduced Residue System

  • [ w ] Remainder

  • [ w ] Residue Number System

  • [ w ] Root of Unity Modulo \(n\)

  • [ w ] Rounding

  • [ w ] RSA (Rivest–Shamir–Adleman)

  • [ w ] Short Division

  • [ w ] Sieve Theory

  • [ w ] Solovay-Strassen Primality Test

  • [ w ] Special Number Field Sieve

  • [ w ] Square Number

  • [ w ] Square Root, of 2

  • [ w ] Square Root, methods of computing

  • [ w ] Strong Pseudoprime

  • [ w ] Totative

  • [ w ] Trial Division

  • [ w ] Well-Ordering Principle

  • [ w ] Wheel Factorization

  • [ w ] Wilson’s Theorem

  • [ w ] Witness

  • [ w ] Zeckendorf’s Theorem