Transcription

2 Overview 1 The Problem 2 Two Simple, and Slow, Methods 3 Modern Methods 4 Algorithms Based on Factorization of Group Size 5 Algorithms Based on Fermat s Little Theorem 6 An Algorithm Outside the Two Themes Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 2 / 47

3 Outline 1 The Problem 2 Two Simple, and Slow, Methods 3 Modern Methods 4 Algorithms Based on Factorization of Group Size 5 Algorithms Based on Fermat s Little Theorem 6 An Algorithm Outside the Two Themes Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 3 / 47

4 The Problem Given a number n, decide if it is prime. Easy: try dividing by all numbers less than n. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 4 / 47

5 The Problem Given a number n, decide if it is prime. Easy: try dividing by all numbers less than n. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 4 / 47

6 The Problem Given a number n, decide if it is prime efficiently. Not so easy: several non-obvious methods have been found. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 5 / 47

7 The Problem Given a number n, decide if it is prime efficiently. Not so easy: several non-obvious methods have been found. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 5 / 47

12 Outline 1 The Problem 2 Two Simple, and Slow, Methods 3 Modern Methods 4 Algorithms Based on Factorization of Group Size 5 Algorithms Based on Fermat s Little Theorem 6 An Algorithm Outside the Two Themes Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 7 / 47

13 The Sieve of Eratosthenes Proposed by Eratosthenes (ca. 300 BCE). 1 List all numbers from 2 to n in a sequence. 2 Take the smallest uncrossed number from the sequence and cross out all its multiples. 3 If n is uncrossed when the smallest uncrossed number is greater than n then n is prime otherwise composite. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 8 / 47

14 Time Complexity If n is prime, algorithm crosses out all the first n numbers before giving the answer. So the number of steps needed is Ω( n). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 9 / 47

15 Time Complexity If n is prime, algorithm crosses out all the first n numbers before giving the answer. So the number of steps needed is Ω( n). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 9 / 47

18 Outline 1 The Problem 2 Two Simple, and Slow, Methods 3 Modern Methods 4 Algorithms Based on Factorization of Group Size 5 Algorithms Based on Fermat s Little Theorem 6 An Algorithm Outside the Two Themes Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 11 / 47

19 Fundamental Idea Nearly all the efficient algorithms for the problem use the following idea. Identify a finite group G related to number n. Design an efficienty testable property P( ) of the elements G such that P(e) has different values depending on whether n is prime. The element e is either from a small set (in deterministic algorithms) or a random element of G (in randomized algorithms). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 12 / 47

20 Fundamental Idea Nearly all the efficient algorithms for the problem use the following idea. Identify a finite group G related to number n. Design an efficienty testable property P( ) of the elements G such that P(e) has different values depending on whether n is prime. The element e is either from a small set (in deterministic algorithms) or a random element of G (in randomized algorithms). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 12 / 47

21 Fundamental Idea Nearly all the efficient algorithms for the problem use the following idea. Identify a finite group G related to number n. Design an efficienty testable property P( ) of the elements G such that P(e) has different values depending on whether n is prime. The element e is either from a small set (in deterministic algorithms) or a random element of G (in randomized algorithms). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 12 / 47

22 Fundamental Idea Nearly all the efficient algorithms for the problem use the following idea. Identify a finite group G related to number n. Design an efficienty testable property P( ) of the elements G such that P(e) has different values depending on whether n is prime. The element e is either from a small set (in deterministic algorithms) or a random element of G (in randomized algorithms). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 12 / 47

23 Groups and Properties The group G is often: A subgroup of Z n or Z n [ζ] for an extension ring Z n [ζ]. A subgroup of E(Z n ), the set of points on an elliptic curve modulo n. The properties vary, but are from two broad themes. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 13 / 47

24 Groups and Properties The group G is often: A subgroup of Z n or Z n [ζ] for an extension ring Z n [ζ]. A subgroup of E(Z n ), the set of points on an elliptic curve modulo n. The properties vary, but are from two broad themes. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 13 / 47

25 Groups and Properties The group G is often: A subgroup of Z n or Z n [ζ] for an extension ring Z n [ζ]. A subgroup of E(Z n ), the set of points on an elliptic curve modulo n. The properties vary, but are from two broad themes. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 13 / 47

26 Theme I: Factorization of Group Size Compute a complete, or partial, factorization of the size of G assuming that n is prime. Use the knowledge of this factorization to design a suitable property. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 14 / 47

27 Theme I: Factorization of Group Size Compute a complete, or partial, factorization of the size of G assuming that n is prime. Use the knowledge of this factorization to design a suitable property. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 14 / 47

28 Theme II: Fermat s Little Theorem Theorem (Fermat, 1660s) If n is prime then for every e, e n = e (mod n). Group G = Z n and property P is P(e) e n = e in G. This property of Z n is not a sufficient test for primality of n. So try to extend this property to a neccessary and sufficient condition. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 15 / 47

29 Theme II: Fermat s Little Theorem Theorem (Fermat, 1660s) If n is prime then for every e, e n = e (mod n). Group G = Z n and property P is P(e) e n = e in G. This property of Z n is not a sufficient test for primality of n. So try to extend this property to a neccessary and sufficient condition. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 15 / 47

30 Outline 1 The Problem 2 Two Simple, and Slow, Methods 3 Modern Methods 4 Algorithms Based on Factorization of Group Size 5 Algorithms Based on Fermat s Little Theorem 6 An Algorithm Outside the Two Themes Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 16 / 47

31 Lucas Theorem Theorem (E. Lucas, 1891) Let n 1 = t i=1 pd i i where p i s are distinct primes. n is prime iff there is an e Z n such that e n 1 = 1 and gcd(e n 1 p i 1, n) = 1 for every 1 i t. The theorem also holds for a random choice of e. We can choose G = Z n and P to be the property above. The test will be efficient only for numbers n such that n 1 is smooth. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 17 / 47

32 Lucas Theorem Theorem (E. Lucas, 1891) Let n 1 = t i=1 pd i i where p i s are distinct primes. n is prime iff there is an e Z n such that e n 1 = 1 and gcd(e n 1 p i 1, n) = 1 for every 1 i t. The theorem also holds for a random choice of e. We can choose G = Z n and P to be the property above. The test will be efficient only for numbers n such that n 1 is smooth. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 17 / 47

33 Lucas Theorem Theorem (E. Lucas, 1891) Let n 1 = t i=1 pd i i where p i s are distinct primes. n is prime iff there is an e Z n such that e n 1 = 1 and gcd(e n 1 p i 1, n) = 1 for every 1 i t. The theorem also holds for a random choice of e. We can choose G = Z n and P to be the property above. The test will be efficient only for numbers n such that n 1 is smooth. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 17 / 47

42 Time Complexity Depends on the difficulty of finding prime factorizations of n 1 whose product is at least n. Other operations can be carried out efficiently. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 21 / 47

43 Time Complexity Depends on the difficulty of finding prime factorizations of n 1 whose product is at least n. Other operations can be carried out efficiently. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 21 / 47

44 Elliptic Curves Based Tests Elliptic curves give rise to groups of different sizes associated with the given number. With good probability, some of these groups have sizes that can be easily factored. This motivated primality testing based on elliptic curves. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 22 / 47

45 Elliptic Curves Based Tests Elliptic curves give rise to groups of different sizes associated with the given number. With good probability, some of these groups have sizes that can be easily factored. This motivated primality testing based on elliptic curves. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 22 / 47

46 Elliptic Curves Based Tests Elliptic curves give rise to groups of different sizes associated with the given number. With good probability, some of these groups have sizes that can be easily factored. This motivated primality testing based on elliptic curves. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 22 / 47

47 Goldwasser-Kilian Test This is a randomized primality proving algorithm. Under a reasonable hypothesis, it is polynomial time on all inputs. Unconditionally, it is polynomial time on all but negligible fraction of numbers. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 23 / 47

48 Goldwasser-Kilian Test This is a randomized primality proving algorithm. Under a reasonable hypothesis, it is polynomial time on all inputs. Unconditionally, it is polynomial time on all but negligible fraction of numbers. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 23 / 47

49 Goldwasser-Kilian Test This is a randomized primality proving algorithm. Under a reasonable hypothesis, it is polynomial time on all inputs. Unconditionally, it is polynomial time on all but negligible fraction of numbers. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 23 / 47

50 Goldwasser-Kilian Test Consider a random elliptic curve over Z n. By a theorem of Lenstra (1987), the number of points of the curve is nearly uniformly distributed in the interval [n n, n n] for prime n. Assuming a conjecture about the density of primes in small intervals, it follows that there are curves with 2q points, for q prime, with reasonable probability. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 24 / 47

51 Goldwasser-Kilian Test Consider a random elliptic curve over Z n. By a theorem of Lenstra (1987), the number of points of the curve is nearly uniformly distributed in the interval [n n, n n] for prime n. Assuming a conjecture about the density of primes in small intervals, it follows that there are curves with 2q points, for q prime, with reasonable probability. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 24 / 47

52 Goldwasser-Kilian Test Consider a random elliptic curve over Z n. By a theorem of Lenstra (1987), the number of points of the curve is nearly uniformly distributed in the interval [n n, n n] for prime n. Assuming a conjecture about the density of primes in small intervals, it follows that there are curves with 2q points, for q prime, with reasonable probability. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 24 / 47

53 Goldwasser-Kilian Test Theorem (Goldwasser-Kilian) Suppose E(Z n ) is an elliptic curve with 2q points. If q is prime and there exists A E(Z n ) O such that q A = O then either n is provably prime or provably composite. Proof. Let p be a prime factor of n with p n. We have q A = O in E(Z p ) as well. If A = O in E(Z p ) then n can be factored. Otherwise, since q is prime, E(Z p ) q. If 2q < n n then n must be composite. Otherwise, p p > n 2 n which is not possible. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 25 / 47

54 Goldwasser-Kilian Test Theorem (Goldwasser-Kilian) Suppose E(Z n ) is an elliptic curve with 2q points. If q is prime and there exists A E(Z n ) O such that q A = O then either n is provably prime or provably composite. Proof. Let p be a prime factor of n with p n. We have q A = O in E(Z p ) as well. If A = O in E(Z p ) then n can be factored. Otherwise, since q is prime, E(Z p ) q. If 2q < n n then n must be composite. Otherwise, p p > n 2 n which is not possible. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 25 / 47

55 Goldwasser-Kilian Test Theorem (Goldwasser-Kilian) Suppose E(Z n ) is an elliptic curve with 2q points. If q is prime and there exists A E(Z n ) O such that q A = O then either n is provably prime or provably composite. Proof. Let p be a prime factor of n with p n. We have q A = O in E(Z p ) as well. If A = O in E(Z p ) then n can be factored. Otherwise, since q is prime, E(Z p ) q. If 2q < n n then n must be composite. Otherwise, p p > n 2 n which is not possible. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 25 / 47

56 Goldwasser-Kilian Test Theorem (Goldwasser-Kilian) Suppose E(Z n ) is an elliptic curve with 2q points. If q is prime and there exists A E(Z n ) O such that q A = O then either n is provably prime or provably composite. Proof. Let p be a prime factor of n with p n. We have q A = O in E(Z p ) as well. If A = O in E(Z p ) then n can be factored. Otherwise, since q is prime, E(Z p ) q. If 2q < n n then n must be composite. Otherwise, p p > n 2 n which is not possible. Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 25 / 47

61 Analysis The algorithm never incorrectly classifies a composite number. With high probability it correctly classifies prime numbers. The running time is O(log 11 n). Improvements by Atkin and others result in a conjectured running time of O (log 4 n). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 27 / 47

62 Analysis The algorithm never incorrectly classifies a composite number. With high probability it correctly classifies prime numbers. The running time is O(log 11 n). Improvements by Atkin and others result in a conjectured running time of O (log 4 n). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 27 / 47

63 Analysis The algorithm never incorrectly classifies a composite number. With high probability it correctly classifies prime numbers. The running time is O(log 11 n). Improvements by Atkin and others result in a conjectured running time of O (log 4 n). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 27 / 47

64 Analysis The algorithm never incorrectly classifies a composite number. With high probability it correctly classifies prime numbers. The running time is O(log 11 n). Improvements by Atkin and others result in a conjectured running time of O (log 4 n). Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 27 / 47

65 Adleman-Huang Test The previous test is not unconditionally polynomial time on a small fraction of numbers. Adleman-Huang (1992) removed this drawback. They first used hyperelliptic curves to reduce the problem of testing for n to that of a nearly random integer of similar size. Then the previous test works with high probability. The time complexity becomes O(log c n) for c > 30! Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 28 / 47

66 Adleman-Huang Test The previous test is not unconditionally polynomial time on a small fraction of numbers. Adleman-Huang (1992) removed this drawback. They first used hyperelliptic curves to reduce the problem of testing for n to that of a nearly random integer of similar size. Then the previous test works with high probability. The time complexity becomes O(log c n) for c > 30! Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 28 / 47

67 Adleman-Huang Test The previous test is not unconditionally polynomial time on a small fraction of numbers. Adleman-Huang (1992) removed this drawback. They first used hyperelliptic curves to reduce the problem of testing for n to that of a nearly random integer of similar size. Then the previous test works with high probability. The time complexity becomes O(log c n) for c > 30! Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 28 / 47

68 Outline 1 The Problem 2 Two Simple, and Slow, Methods 3 Modern Methods 4 Algorithms Based on Factorization of Group Size 5 Algorithms Based on Fermat s Little Theorem 6 An Algorithm Outside the Two Themes Manindra Agrawal (IIT Kanpur) Is n a Prime Number? March 27, 2006, Delft 29 / 47

Primality - Factorization Christophe Ritzenthaler November 9, 2009 1 Prime and factorization Definition 1.1. An integer p > 1 is called a prime number (nombre premier) if it has only 1 and p as divisors.

David Harvey (joint work with Edgar Costa, NYU) University of New South Wales 25th October 2011 The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers

An Overview of Integer Factoring Algorithms Manindra Agrawal IITK / NUS The Problem Given an integer n, find all its prime divisors as efficiently as possible. 1 A Difficult Problem No efficient algorithm

Factoring & Primality Lecturer: Dimitris Papadopoulos In this lecture we will discuss the problem of integer factorization and primality testing, two problems that have been the focus of a great amount

3. Computational Complexity. (A) Introduction. As we will see, most cryptographic systems derive their supposed security from the presumed inability of any adversary to crack certain (number theoretic)

Today s Topics Primes & Greatest Common Divisors Prime representations Important theorems about primality Greatest Common Divisors Least Common Multiples Euclid s algorithm Once and for all, what are prime

Primality Testing and Factorization Methods Eli Howey May 27, 2014 Abstract Since the days of Euclid and Eratosthenes, mathematicians have taken a keen interest in finding the nontrivial factors of integers,

Computational Number Theory C. Pomerance 1 Introduction Historically, computation has been a driving force in the development of mathematics. To help measure the sizes of their fields, the Egyptians invented

On the largest prime factor of x 2 1 Florian Luca and Filip Najman Abstract In this paper, we find all integers x such that x 2 1 has only prime factors smaller than 100. This gives some interesting numerical

15 Prime and Composite Numbers Divides, Divisors, Factors, Multiples In section 13, we considered the division algorithm: If a and b are whole numbers with b 0 then there exist unique numbers q and r such

HYPERELLIPTIC CURVE METHOD FOR FACTORING INTEGERS WENHAN WANG 1. Thoery and Algorithm The idea of the method using hyperelliptic curves to factor integers is similar to the elliptic curve factoring method.

8 Primes and Modular Arithmetic 8.1 Primes and Factors Over two millennia ago already, people all over the world were considering the properties of numbers. One of the simplest concepts is prime numbers.

FACTORING The claim that factorization is harder than primality testing (or primality certification) is not currently substantiated rigorously. As some sort of backward evidence that factoring is hard,

Factorization Methods: Very Quick Overview Yuval Filmus October 17, 2012 1 Introduction In this lecture we introduce modern factorization methods. We will assume several facts from analytic number theory.

CHAPTER 5 Number Theory 1. Integers and Division 1.1. Divisibility. Definition 1.1.1. Given two integers a and b we say a divides b if there is an integer c such that b = ac. If a divides b, we write a

The Prime Numbers Before starting our study of primes, we record the following important lemma. Recall that integers a, b are said to be relatively prime if gcd(a, b) = 1. Lemma (Euclid s Lemma). If gcd(a,

Runtime and Implementation of Factoring Algorithms: A Comparison Justin Moore CSC290 Cryptology December 20, 2003 Abstract Factoring composite numbers is not an easy task. It is classified as a hard algorithm,

EMBEDDING DEGREE OF HYPERELLIPTIC CURVES WITH COMPLEX MULTIPLICATION CHRISTIAN ROBENHAGEN RAVNSHØJ Abstract. Consider the Jacobian of a genus two curve defined over a finite field and with complex multiplication.

Breaking The Code Ryan Lowe Ryan Lowe is currently a Ball State senior with a double major in Computer Science and Mathematics and a minor in Applied Physics. As a sophomore, he took an independent study

MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2016 47 4. Diophantine Equations A Diophantine Equation is simply an equation in one or more variables for which integer (or sometimes rational) solutions

The General Approach Notes on Factoring MA 26 Kurt Bryan Suppose I hand you n, a 2 digit integer and tell you that n is composite, with smallest prime factor around 5 digits. Finding a nontrivial factor

Number Fields Introduction A number field is a field of finite degree over Q. By the Primitive Element Theorem, any number field K = Q(α) for some α K. The minimal polynomial Let K be a number field and

ELEMENTARY THOUGHTS ON DISCRETE LOGARITHMS Carl Pomerance Given a cyclic group G with generator g, and given an element t in G, the discrete logarithm problem is that of computing an integer l with g l

The van Hoeij Algorithm for Factoring Polynomials Jürgen Klüners Abstract In this survey we report about a new algorithm for factoring polynomials due to Mark van Hoeij. The main idea is that the combinatorial

11 Ideals The presentation here is somewhat different than the text. In particular, the sections do not match up. We have seen issues with the failure of unique factorization already, e.g., Z[ 5] = O Q(

Computing square roots mod p We now have very effective ways to determine whether the quadratic congruence x a (mod p), p an odd prime, is solvable. What we need to complete this discussion is an effective

Chapter 23 Squares Modulo p Revised Version of Chapter 23 We learned long ago how to solve linear congruences ax c (mod m) (see Chapter 8). It s now time to take the plunge and move on to quadratic equations.

CONSTRUCTION OF THE FINITE FIELDS Z p S. R. DOTY Elementary Number Theory We begin with a bit of elementary number theory, which is concerned solely with questions about the set of integers Z = {0, ±1,

A Comparison Of Integer Factoring Algorithms Keyur Anilkumar Kanabar Batchelor of Science in Computer Science with Honours The University of Bath May 2007 This dissertation may be made available for consultation

The Prime Facts: From Euclid to AKS c 2003 Scott Aaronson 1 Introduction My idea for this talk was to tell you only the simplest, most basic things about prime numbers the things you need to know to call

MATH 168: FINAL PROJECT Troels Eriksen 1 Introduction In the later years cryptosystems using elliptic curves have shown up and are claimed to be just as secure as a system like RSA with much smaller key

STUDY ON ELLIPTIC AND HYPERELLIPTIC CURVE METHODS FOR INTEGER FACTORIZATION by Takayuki Yato A Senior Thesis Submitted to Department of Information Science Faculty of Science The University of Tokyo on

Minimal Polynomials Definition Let α be an element in GF(p e ). We call the monic polynomial of smallest degree which has coefficients in GF(p) and α as a root, the minimal polyonomial of α. Example: We

SOLUTIONS FOR PROBLEM SET 2 A: There exist primes p such that p+6k is also prime for k = 1,2 and 3. One such prime is p = 11. Another such prime is p = 41. Prove that there exists exactly one prime p such

MATH31: Number Theory Homework until Test # Philipp BRAUN Section 3.1 page 43, 1. It has been conjectured that there are infinitely many primes of the form n. Exhibit five such primes. Solution. Five such

Elementary Number Theory A revision by Jim Hefferon, St Michael s College, 2003-Dec of notes by W. Edwin Clark, University of South Florida, 2002-Dec L A TEX source compiled on January 5, 2004 by Jim Hefferon,

DIVISORS IN A DEDEKIND DOMAIN Javier Cilleruelo and Jorge Jiménez-Urroz 1 Introduction Let A be a Dedekind domain in which we can define a notion of distance. We are interested in the number of divisors

The application of prime numbers to RSA encryption Prime number definition: Let us begin with the definition of a prime number p The number p, which is a member of the set of natural numbers N, is considered

CMSC 858T: Randomized Algorithms Spring 2003 Handout 8: The Local Lemma Please Note: The references at the end are given for extra reading if you are interested in exploring these ideas further. You are

Instructions. Answer each of the questions on your own paper, and be sure to show your work so that partial credit can be adequately assessed. Credit will not be given for answers (even correct ones) without

An Introductory Course in Elementary Number Theory Wissam Raji 2 Preface These notes serve as course notes for an undergraduate course in number theory. Most if not all universities worldwide offer introductory

Carmichael numbers and pseudoprimes Notes by G.J.O. Jameson Introduction Recall that Fermat s little theorem says that if p is prime and a is not a multiple of p, then a p 1 1 mod p. This theorem gives

3. APPLICATIONS OF NUMBER THEORY 163 3. Applications of Number Theory 3.1. Representation of Integers. Theorem 3.1.1. Given an integer b > 1, every positive integer n can be expresses uniquely as n = a