Fermat's Little Theorem

12 Key excerpts on "Fermat's Little Theorem"

• 

  eBook - PDF

  Number Theory

  A Historical Approach

  • John J. Watkins(Author)
  • 2013(Publication Date)
  • Princeton University Press

    (Publisher)

  Note that it is the corollary, not the theorem, that is the heart of the matter. Corollary 1. If p is a prime and does not divide a, and if n is the least positive integer such that a n ≡ 1 (mod p ) , then n ( p − 1) . We often like to state Fermat’s little theorem in a slightly different form, which we get by multiplying the congruence a p − 1 ≡ 1 (mod p ) by a . Note that in this form, the congruence remains true even in the totally uninteresting case where p a . Corollary 2 ( Fermat’s little theorem—alternate form). If p is a prime, then for any integer a, a p ≡ a (mod p ) . 126 Chapter 5 In Problem 5.40, we will ask you to give a different proof of Corollary 2 using induction and following the original argument that Fermat made for the case a = 2. Primes as Sums of Two Squares With Fermat’s little theorem in hand, we are now ready to see how Fermat finished his proof of Theorem 5.1, or, as he called it, his funda-mental theorem on right-angled triangles . In the same letter to Huygens, in 1659, in which Fermat mentioned using his method of infinite descent to prove negative assertions such as Theorem 1.2, his theorem that no Pythagorean triangle has square area, he writes: For a long time I was unable to apply my method to affirmative questions . . . so much so that when it occurred to me to prove that every prime number which is one more than a multiple of 4 is a sum of two squares I found myself in a good deal of trouble. But finally a line of thought gone over many times showed me a light which did not fail, and affirmative questions surrendered to my method. We do not have the details of Fermat’s proof, only the briefest de-scription to Huygens in this letter that a version of infinite descent was used.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction to Cryptography with Open-Source Software

  • Alasdair McAndrew(Author)
  • 2016(Publication Date)
  • CRC Press

    (Publisher)

  Fermat’s and Euler’s theorems Fermat’s theorem claims that if p is a prime number, then for any integer a a p = a (mod p ) . An alternative formulation is obtained by dividing each side of this equation by a (assuming that a is not a multiple of p ); then the theorem reads a p − 1 = 1 (mod p ) . To show this, consider all the values a, 2 a, 3 a,... ( p − 1) a . Since a is not a multiple of p , all these values must have different residues when reduced mod p . For if any two were equal, then ma = na (mod p ) for some values m and n between 1 and p − 1. That is, ( m − n ) a = 0 (mod p ) . But this means that either a or m − n is divisible by p . Since a is not divisible by p , the only way for m − n to be divisible by p is to have m = n . But this is impossible since all the coefficients of a are different. This means that the residues of a, 2 a, 3 a,... ( p − 1) a (mod p ) are just the values 1 , 2 , 3 ,...,p − 1, in some order. Thus: ( a )(2 a )(3 a ) ... (( p − 1) a )) = 1 . 2 . 3 ... ( p − 1) (mod p ) . Since 1 . 2 . 3 ... ( p − 1) is not divisible by p , each side of this equation can be divided by this value to obtain a p − 1 = 1 (mod p ) . which is the required result. Fermat’s theorem can be used to simplify modular powers. For example, consider the power 10 27 (mod 13) . Since by Fermat’s theorem 10 12 = 1 (mod 13) , 42 Cryptography with Open-Source Software the original power can be expressed using multiples of 12 as 10 27 = 10 2(12)+3 = (10 12 ) 2 10 3 . Hence 10 27 (mod 13) = (10 12 ) 2 10 3 (mod 13) = 10 3 (mod 13) and this last power can be evaluated with much less trouble than the original. Note that the final power 3 is just the original power 27 modulo 12. This means that in general, if p is prime and a

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Applied Algebra

  Codes, Ciphers and Discrete Algorithms, Second Edition

  • Darel W. Hardy, Fred Richman, Carol L. Walker(Authors)
  • 2009(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  For over 350 years many professional and amateur mathematicians tried to verify Fermat’s statement, but no one succeeded in proving it. The statement became known as “Fermat’s Last Theorem” because it was the last of Fermat’s claims that people figured out how to prove. One of the remarkable achievements of the twentieth century was that Andrew Wiles (1953–) was able to prove it. I grew up in Cambridge in England, and my love of mathematics dates from those early childhood days. I loved doing problems in school. I’d take them home and make up new ones of my own. But the best problem I ever found, I found in my local public library. I was just browsing through the section of math books and I found this one book, which was all about one particular problem—Fermat’s Last Theorem. This problem had been unsolved by mathematicians for 300 years. It looked so simple, and yet all the great mathematicians in history couldn’t solve it. Here was a problem, that I, a ten year old, could understand and I knew from that moment that I would never let it go. I had to solve it. Andrew Wiles Fermat’s last theorem is also known as his great theorem . Our next result is sometimes called Fermat’s little theorem to distinguish it from his great theorem. It is also called simply Fermat’s theorem . The Chinese knew as early as 500 b.c. that 2 p − 2 is divisible by the prime p . Fermat rediscovered this fact in 1640, and stated that he had a proof that if p is any prime and x is any integer not divisible by p , then x p − 1 − 1 is divisible by p . Euler published the first proof of Fermat’s little theorem in 1736. Theorem 7.7 (Fermat’s Little Theorem) If p is a prime and a ⊥ p , then a p − 1 ≡ 1 (mod p ) Proof. Assume that p is a prime and a ⊥ p . If na ≡ ma (mod p ) then n ≡ m (mod p ), and hence it follows that no two of the numbers a , 2 a , 3 a , . . . , ( p − 1) a are congruent modulo p , and none is congruent to zero modulo p . It follows that these integers are congruent to 1, 2, 3, .

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Strange Curves, Counting Rabbits, & Other Mathematical Explorations

  • Keith Ball(Author)
  • 2011(Publication Date)
  • Princeton University Press

    (Publisher)

  prime numbers , and the only reason that 10 appeared at all is that we happen to count in base 10 (presumably because we have 10 fingers).

  Fermat discovered that if we pick any number n and any prime number p which does not divide into n , then n

  p −1

  − 1 is divisible by p . The statement is often called Fermat’s Little Theorem to distinguish it from the notorious Last Theorem of Fermat, which was perhaps the most famous unsolved problem in mathematics until a few years ago, when Andrew Wiles gave a proof.

  The Little Theorem can be proved in just the same way as the case for n = 10 was proved, by expanding the fraction 1/p as a ‘decimal’ in base n . An alternative proof is based on Problem 3.7 below. In order to explain the relevance of this problem we start by observing that the Little Theorem can be phrased slightly differently.

  If n is a whole number and p is a prime, then np − n is divisible by p.

  The point here is that

  np

  − n = n (n

  p −1

  − 1),

  so to say that

  np − n

  is divisible by p is to say that either n is divisible by p or n

  p −1

  − 1 is divisible by p . Now for the problem.

  * Problem 3.7. Show that for any two whole numbers a and b , and any prime number p , the number

  (a + b)p − ap − bp

  is divisible by p . (Hint: start by doing it for p = 2, p = 3 and p = 5.)

  The problem makes a statement about a pair of numbers, a and b , but the conclusion of the problem can immediately be ‘souped up’ from two numbers to more than two.

  Problem 3.8. Show that for any whole numbers a 1 , a 2 ,. . .,

  an

  , and any prime number p , the number

  is divisible by p .

  If we now apply this statement with all of the

  ai

  equal to 1, we conclude that

  np − n

  is divisible by p

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A Course in Mathematical Cryptography

  • Gilbert Baumslag, Benjamin Fine, Martin Kreuzer, Gerhard Rosenberger(Authors)
  • 2015(Publication Date)
  • De Gruyter

    (Publisher)

  We close this subsection with several other results in elementary number theory involving primes that appear in cryptography. The first is called Fermat’s Theorem.

  Theorem 5.4.4 (Fermat). Letp be a prime. Then

  for each a єZ, that is p\(ap - a). Hence in the ring Zp we have ap = a and if a = 0 then ap- 1 = 1.

  Proof. Here we give a purely number theoretic proof. In the next section we give a proof based on elementary group theory. If a = 0 (mod p) then

  ap

  = 0 (mod p) so

  ap

  = a (mod p).

  If a = 0 (modp) so that (a,p) = 1, let {r1 ,…,

  rp

  } be a complete residue system modulo p with

  rp

  = 0. Since (a,p) = 1 then {ar1 , ar2 ,…,

  arp

  } is also a complete residue system modulo p and

  arp

  = 0 (modp). Then we have

  However, (r1 …

  rp-1 )

  is not divisible by p so it is a unit in

  Zp

  and hence we can divide through by it to get the result;

  Theorem 5.4.5 (Wilson). Letp be aprime. Then

  Conversely if (p - 1)! = −1 (modp) thenpis aprime.

  Proof. Now (p - 1)! = (p - 1)(p - 2) ••• 1. Since

  Zp

  is a field each

  has a multiplicative inverse modulo p. Further suppose x = x- 1 in

  Zp .

  Then x2 = 1 which implies (x - 1)(x + 1) = 0 in

  Zp

  and hence either x =1or x = −1 since

  Zp

  is an integral domain. Therefore in

  Zp

  only 1, −1 are their own multiplicative inverses. Further −1 = p - 1 since p - 1 = −1 (modp).

  Hence in the product (p - 1)(p - 2) … 1 considered in the field

  Zp

  each element is paired up with its distinct multiplicative inverse except 1 and p−1. Further the product of each with its inverse is 1. Therefore in

  Zp

  we have (p - 1)(p - 2) … 1 = p −1. Written as a congruence then

  Conversely suppose (n - 1)! = −1 (mod n). If n were composite then n = mk with 1 < m < n - 1 and 1 < k < n - 1. Hence, if m = k then both m and k are included in (n −1)!. It follows that (n −1)! is divisible by n so that (n −1)! = 0 (mod n) contradicting the assertion that (n - 1)! = −1 (mod n). If m = k then n = m2 .If m = 2 then n = 4 and (n - 1)! = 2 (mod 4) contradicting the assertion (n - 1)! = −1 (mod 4).

  If m > 3 then (n - 1)! = 0 (mod m) but −1 = 0 (mod m).

  Therefore n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Number Theory

  • Richard Michael Hill(Author)
  • 2017(Publication Date)
  • WSPC (EUROPE)

    (Publisher)

  ☐ Fermat’s little theorem simplifies many calculations. Suppose, for example, that we’d like to calculate powers of 10 modulo the prime number 19. By Fermat’s Little Theorem, we have

  1018 ≡ 1    mod 19.

  This shows that the congruency class 10n mod 19 depends only on the congruency class of n modulo 18. For example, since 182 ≡ 2 mod 18, we have

  10182 ≡ 102 ≡ 5    mod 19.

  Perhaps, the example above seems a little contrived because the power 182 is very close to a multiple of 18. More realistically, suppose we’d like to calculate 10102 modulo 19. Since 102 ≡ 12 mod 18, we have

  10102 ≡ 1012     mod 19.

  The power on the right-hand side is now quite small, and so we can do the rest of the calculation by hand. The first step is to note that 1012 = 1006 ≡ 56 mod 19. Therefore,

  10102 ≡ 253 ≡ 63 ≡ 7    mod 19.

  Solving congruences with powers. We can also use Fermat’s Little Theorem to solve congruences of the form

  xa ≡ b    mod p,

  as long as p is a prime number and the power a is coprime to p − 1.

  If b ≡ 0 mod p, then since is a field, the only solution is x ≡ 0 mod p. We may therefore assume that b 0 mod p. Hence, any solution x must also be non-zero modulo p. Fermat’s Little Theorem then shows that the power xn mod p depends only on n modulo p − 1.

  To solve the congruence, we must find the inverse c of a modulo p − 1. Raising both sides of the congruence to the power c, we have

  xac ≡ bc     mod p.

  As ac ≡ 1 mod p − 1, the left-hand side simplifies to x1 , so the solution is

  x ≡ bc     mod p.

  As an example, we’ll solve the congruence

  x5 ≡ 2    mod 19.

  Note that the power 5 is coprime to 18, so the method described above is applicable. The inverse of 5 modulo 18 is 11. Therefore, the solution is x ≡ 211 mod 19. Of course, we might want to reduce 211

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Public Key Cryptography

  Applications and Attacks

  • Lynn Margaret Batten(Author)
  • 2013(Publication Date)
  • Wiley-IEEE Press

    (Publisher)

  The simplest approach to testing for “primeness” is the same as that for testing for factors: try division by each prime up to the square root of the number. Given that we need primes with more than 100 digits for our cryptosystems, this can be computationally prohibitive. (See Problem 1 in Section 7.1.2.) In general, we argue that if our resources cannot check primality in a reasonable period of time, then it is likely that the resources of an attacker cannot do so either. Thus, we are willing to give up certainty for speed, and as long as a number is not shown, in a reasonable amount of time and with a reasonable set of tests, to be not prime, we assume that it is prime or at least prime-like. The tests we present in this chapter are based on this approach.

  7.1 Fermat's Approach and Wilson's Theorem

  We saw in Section 2.3 that Fermat's theorem can be used to test if a number is prime. More precisely, if a modulus p is used with a value a in the statement of the FLT and the result is not 1, then p must be composite. The more values for a tested and returning 1, the more certain we become about the primality of p . Thus, we can associate a level of confidence with a conclusion that p is “probably prime.” However, we saw in Chapter 2 that there are composite numbers which always pass the Fermat test. These are the Carmichael numbers defined in Computer Example 3 of Section 2.3.1.

  Computer Example 2 of Section 2.3.1 defined a pseudoprime. We give a formal definition again here.

  Definition 7.1 If some specific value for a satisfies Theorem 2.3 (the FLT) modulo n where n is composite, then we say that n is a (Fermat) pseudoprime base a .

  Example 7.1 Since 2340 ≡ 1 (mod 341), the number 341 is a pseudoprime base 2. (Note that 11 divides 341.)

  The next result we consider in this section gives a definitive test for primality. It has two parts: the first part states that if p is prime, then a certain congruence modulo p must hold. The second part is the converse and states that if this same congruence holds modulo a number p , then p must be prime. However, instead of a congruence equation involving exponents, as used by Fermat and Euler, this result deals with factorials.

  Recall that n ! means n * (n − 1) * (n − 2) * ... * 2 * 1. For instance, 6 ! = 6 * 5 * 4 * 3 * 2 * 1 = 720.

  Theorem 7.1 Wilson's Theorem

  If p is a prime, then (p − 1) ! ≡ − 1 (mod p ).

  Proof. The proof is based on the fact that any number in the range 1 to p − 1 has an inverse in this range (by the EA). We pair up each number in the factorial on the left of the modulus equation with its inverse. If a number and its inverse are different, their product is 1. The only problem is when a number is its own inverse, which is the case for both 1 and p − 1, for instance. We leave as an exercise to show that these are the only cases in which a number is its own inverse. (See the problem set.) So we can pair these two numbers up, which gives a product of −1. Thus, the product of all numbers between 1 and p − 1 is −1, as claimed.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Cryptography and Network Security

  Demystifying the ideas of Network Security, Cryptographic Algorithms, Wireless Security, IP Security, System Security, and Email Security

  • Bhushan Trivedi, Savita Gandhi, Dhiren Pandit(Authors)
  • 2021(Publication Date)
  • BPB Publications

    (Publisher)

  y , he/she has no way of determining the constituents in real time. Multiplication of primes is used in RSA cryptography, whereas, discrete logarithms are used in Elgamel cryptography.

  Additional reading

  • To get a feel of distribution of prime numbers (section 4.2.3: Distribution of prime numbers ), graphs and tables of numbers of prime numbers in different ranges can be viewed at https://www.savitagandhi.com/articles/distribution-of-prime-numbers .
  • To know and understand the proof of Fermat’s little theorem (section 4.5.1: Fermat’s little theorem ) and that of Euler’s theorem (section 4.5.3:Euler’s theorem ) you can visit https://www.savitagandhi.com/articles/fermats-little-theorem and https://www.savitagandhi.com/articles/eulers-theorem , respectively.
  • The Chinese remainder theorem (section 4.5.1: Fermat’s little theorem ) is useful solving in multiple linear congruences is explained with proof and illustrations at https://www.savitagandhi.com/articles/chinese-remainder-theorem .
  • A table of values of Euler’s totient function upto 50, graph showing relationship between n and ϕ(n ) as well as proof of elementary properties of totient function (section 4.5.2:Euler’s totient function ) is presented at https://www.savitagandhi.com/articles/totient-function .
  • Proofs of the two base properties used in Miller-Rabin primality test (section 4.6.2: Miller-Rabin primality test ) is available at https://www.savitagandhi.com/articles/miller-rabin-primality-test .
  • Another common primality test, namely, Solovay-Strassen primality test is discussed, explained, and illustrated with examples at https://www.savitagandhi.com/articles/solovay-primality-test .

  Recommended reading/references

  • [Agrawal, Kayal & Saxena2004]: M. Agrawal, N. Kayal and N. Saxena, “Primes in P”

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Induction Book

  • Steven H. Weintraub(Author)
  • 2017(Publication Date)
  • Dover Publications

    (Publisher)

  Chapter 3

  Theorems

  In this chapter, we present the proofs of a small number of important theorems. These proofs all use induction or the pigeonhole principle, but they are too involved to have been posed as problems. We include them to further show the importance and utility of these methods.

  3.1 Fermat’s Theorem on Sums of Two Squares

  Our goal in this section is to prove Fermat’s famous theorem that every prime p congruent to 1 modulo 4 can be written as the sum of two integer squares, p = x2 + y2 . For example, 5 = 22 + 12 , 13 = 32 + 22 , 17 = 42 + 12 , 29 = 52 + 22 , …, 97 = 92 + 42 , 101 = 102 + 12 , …, 997 = 312 + 62 , 1009 = 282 + 152 , …, 9973 = 822 + 572 , 10009 = 1002 + 32 , …, 99989 = 2302 + 2172 , 100049 = 2322 + 2152 , …, 999961 = 7652 + 6442 .

  We call a way of writing p as a sum of two squares a representation of p as a sum of two squares.

  Furthermore, if we require x and y to be nonnegative, and do not distinguish between the order of x and y (i.e., we regard p = x 2 + y2 and p = y2 + x 2 as being the same representation), then it is also the case that the representation of p is unique.

  Fermat did not leave a record of his proof, but wrote that it was by his method of “descent.” Following this hint, Euler gave a proof by descent, and we present this proof here. As we shall see, descent is just a form of induction. (The method of mathematical induction was not formalized until the nineteenth century, long after the times of Fermat and Euler.) We shall present a second twentieth century proof, due to Thue, using the pigeonhole principle.

  Of course, every prime p is either equal to 2, and 2 = 12 + 12 , or is congruent to either 1 or 3 modulo 4. It is very easy to rule out the last case.

  Lemma 3.1.1. No integer congruent to 3 modulo 4 is the sum of two integer squares.

  Proof. Let z be any integer. If z is even, z = 2k, then z2 = 4k2 so z2 ≡ 0 (mod 4). If z is odd, z = 2k + 1, then z2 = 4k2 + 4k + 1 so z2 ≡ 1 (mod 4). Thus if n = x 2 + y2 , then, depending on whether x and y are even or odd, n ≡ 0 + 0, 0 + 1, 1 + 0, 1 + 1 (mod 4), i.e., n ≡ 0, 1, or 2 (mod 4), i.e., n

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Abstract Algebra

  A Gentle Introduction

  • Gary L. Mullen, James A. Sellers(Authors)
  • 2016(Publication Date)
  • CRC Press

    (Publisher)

  Thus ab must divide the sum, which is c . Our next theorem is often attributed to Euclid (and is referred to by many as “Euclid’s Lemma.”) It provides the foundation for the truly important role that the primes play in elementary number theory. Theorem 1.7 If p is a prime and p divides ab , then p divides a or p divides b . Proof: Since p is a prime, we know gcd( p, a ) is either 1 or p . In the latter case p divides a . If gcd( p, a ) = 1 then part (i) of Theorem 1.6 implies that p divides b . The above result says that if p is a prime and it divides the product of two integers, it must divide one or the other of the integers (or both). Note that this is not necessarily true of divisors that are not prime. For example, 4 12, | which can be written as 6 × 2. So 4 | (6 × 2), but 4 ∤ 6 and 4 ∤ 2. The next result shows that if a prime divides the product of any finite number of integers, it must divide one of them. The reader will be asked to prove this corollary in the exercises. Corollary 1.8 If p is a prime and p divides a 1 a r , then p must divide a i · · · for some i = 1 , . . . , r . We now state, and prove, one of the most fundamental results in number theory. This result states that any positive integer can be written as a product of primes, and that with a possible re-ordering of the primes, this product of primes is unique. Theorem 1.9 (Unique Factorization) (i) Each positive integer n ≥ 2 may be written as a product of primes; i.e., n may be written in the form n = p 1 p r · · · 9 Elementary Number Theory where each integer p i , i = 1 , . . . , r , is a prime. (ii) Moreover, this factorization is unique except for the order of the primes; i.e., if n = q 1 q s where each q i is a prime, then r = s and (if · · · necessary) upon re-ordering, p i = q i , i = 1 , . . . , r . Proof: For the proof of part (i), we use strong induction. This proof is given in the Appendix, Section 9.1 where strong mathematical induction is discussed.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Handbook of Mathematical Induction

  Theory and Applications

  • David S. Gunderson(Author)
  • 2014(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Then F 0 = 3, F 1 = 5, F 2 = 17, F 3 = 257, and F 4 = 65537, all prime numbers. Fermat conjectured that for every non-negative integer t , F t is prime, but Euler proved this to be false. Theorem 6.5.1 (Euler) . F 5 = 2 32 + 1 is not prime. Proof: Put a = 2 7 and b = 5. Then a − b 3 = 128 − 125 = 3 and 1 + ab − b 4 = 1 + ( a − b 3 ) b = 1 + 3 b = 16 = 2 4 . Hence 2 2 5 + 1 = 2 3 2 + 1 = (2 8 ) 4 + 1 = (2 a ) 4 + 1 = 2 4 a 4 + 1 = (1 + ab − b 4 ) a 4 + 1 = (1 + ab ) a 4 − ( a 4 b 4 − 1) = (1 + ab ) a 4 − ( a 2 b 2 − 1)( a 2 b 2 + 1) = (1 + ab ) a 4 − ( ab + 1)( ab − 1)( a 2 b 2 + 1) = (1 + ab )[ a 4 − ( ab − 1)( a 2 b 2 + 1)] , and so 1 + ab = 1 + 2 7 · 5 = 641 is a divisor of F 5 . Over a century later, Landry proved that F 6 is not prime either! Since then, it has been shown that for 5 ≤ n ≤ 21, F n is composite. For further references, see, e.g. , [456, pp. 214–215]. Fermat numbers do, however, share one property (provable by induction): Exercise 21. Prove that for every t ≥ 2 , the last digit of the Fermat number F t is 7. The next property of Fermat numbers was mentioned in Proofs from the Book [7], and although it says nothing about producing primes, it has an amazing con-nection to the number of primes being infinite. The following statement follows the convention that an empty product is 1. Exercise 22. Prove that for n = 0 , 1 , 2 ,... , F n = n − 1 productdisplay i =0 F i + 2 . (6.1) 82 Chapter 6. Empirical induction From Equation (6.1), it follows that the Fermat numbers are relatively prime (if any two had a common divisor, it would also have to divide 2, but Fermat numbers are odd). As pointed out in [7], it then follows easily that there are infinitely many primes (as there are infinitely many Fermat numbers). (Compare with Exercise 207, a variation of Euclid’s proof.) Note that a similar divisibility situation to that in Euclid’s proof (with a product and something small added) occurs in the consequence of Exercise 6.1.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction To Formal Languages And Machine Computation, An

  • Song Y Yan(Author)
  • 1998(Publication Date)
  • World Scientific

    (Publisher)

  246 Chapter 4. Number-Theoretic Computations and Applications 4.1 Primality Testing 4.1.1 Basic Algorithm Primality testing of large numbers is very important in many areas of mathe-matics, computer science and cryptography. For example, in public-key cryp-tography, if we can find two large primes p and q, each with 100 digits or more, then we can get a composite n = p • q with 200 digits or more. This composite n can be used to encrypt a message securely even when n is made public. The message cannot be decrypted without knowledge of the prime factors of n. Of course, we can try to use a modern integer factorization method, e.g., the Elliptic Curve Method (ECM) to factor n and to get its prime factors p and q, but it might take about 20 million years to complete the job even on a supercomputer. Thus, it is impossible in practice to decrypt the message. Another good example is searching for amicable numbers. In the following algebraic method for generating amicable numbers, if we can make sure that the following four integers p, q, r, s: 0 < x < n q = 2 y + (2 n+1 - 1) ■ g < where < g = 2 n ~ x + 1 r = 2 n ~ y ■ g • q - 1 0 < y < n < s = 2 n ~y+ x ■ g 2 ■ q -1 v are all primes, then the pair (m, n) = {Tqpr, 2 n qs) is an amicable pair. Thus, searching for amicable numbers is often the same as primality testing of some related integers. The search for efficient primality tests is not just an open problem, but one of the oldest unfinished projects in mathematics, with a root that possibly goes back to the ancient Greeks about 2000 years ago. It is a typical decision problem: I Input : n G N with n > 1. f Yes, if n 6 Primes, (4.1) Output: <^ V ' No, otherwise. (p = 2*-g-l 0 < x < n q = 2y + (2 n+1 - 1) ■ g < where < g = 2 n ~ x + 1 r = 2 n ~ y ■ g • q -1 0 < y < n < s = 2 n ~y+ x ■ g 2 ■ q -1 v (m, n) = {Tqpr, 2 n qs) I Input : n G N with n > 1. f Yes, if n G Primes, (4.1) Output: <^ V ' No, otherwise.

  Sign up to read

  Learn more about book