Mathematics
Prime Factorization
Prime factorization is the process of breaking down a number into its prime factors, which are the prime numbers that multiply together to give the original number. This is a fundamental concept in number theory and is used in various mathematical applications, such as finding the greatest common divisor or least common multiple of numbers.
Written by Perlego with AI-assistance
Related key terms
1 of 5
9 Key excerpts on "Prime Factorization"
eBook - ePub- Mary Jane Sterling(Author)
- 2016(Publication Date)
- For Dummies(Publisher)
The opposite of prime numbers, composite numbers, can be broken down into factorable, reducible pieces. In this section, you see how every composite number is the product of prime numbers, in a process known as Prime Factorization. Every number’s Prime Factorization is unique. The Prime Factorization of a number is the unique product of prime numbers that results in the given number. A prime number’s Prime Factorization consists of just that prime number, by itself. Here are some examples of Prime Factorization: 6 = 2 · 3 12 = 2 · 2 · 3 = 2 2 · 3 16 = 2 · 2 · 2 · 2 = 2 4 250 = 2 · 5 · 5 · 5 = 2 · 5 3 510,510 = 2 · 3 · 5 · 7 · 11 · 13 · 17 42,059 = 137 · 307 Okay, so that last one is a doozy. Finding that Prime Factorization without a calculator, a computer, or list of primes is difficult. The factors of some numbers aren’t always obvious, but I do have some techniques to help you write Prime Factorizations, so check out the next section. Writing Prime Factorizations Writing the Prime Factorization of a composite number is one way to be absolutely sure you’ve left no stone unturned when reducing fractions or factoring algebraic expressions. These factorizations show you the one and only way a number can be factored. Two favorite ways of creating Prime Factorizations are upside-down division and trees. Dividing while standing on your head A slick way of writing out Prime Factorizations is to do an upside-down division. You put a prime factor (a prime number that evenly divides the number you’re working on) on the outside left and the result or quotient (the number of times it divides evenly) underneath. You divide the quotient (the number underneath) by another prime number and keep doing this until the bottom number is a prime. Then you can stop. The order you do the divisions in doesn’t matter. You get the same result or list of prime factors no matter what order you use
Available until 4 Dec |Learn more- James S. Kraft, Lawrence C. Washington(Authors)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 10 Primality and Factorization Two fundamental computational problems in number theory are finding large primes and factoring composite numbers. Although these problems are related, they have intrinsic differences. It is rel-atively easy to prove that a number is composite but, once this has been done, it is much harder to find its factors. With the popularity of cryptographic algorithms that use primes, primality testing and factoring have become very important. In this chapter, we show how to decide whether a number is prime or composite. Then we discuss some factorization methods that are used in practice. 10.1 Trial Division and Fermat Factorization The easiest method for primality testing and factorization is trial division. If we want to factor an integer n > 1, we divide n by all the primes p ≤ √ n until we find a prime factor. If we don’t find a factor, n is prime. If we find a factor p 1 , then we continue to try to factor n 1 = n/p 1 . We could start at the beginning, trying to divide 2, 3, 5, · · · into n 1 . But we have already taken care of the primes less than p 1 , so we can start at p 1 and continue until either we get to √ n 1 (by Proposition 1.7) or we find another prime factor p 2 . Then we try to factor n 2 = n 1 /p 2 . This process eventually terminates and yields the factorization of n . Example. Let n = 43771. It is not divisible by 2, 3, and 5, but it 295 296 Chapter 10 Primality and Factorization is divisible by 7: 43771 = 7 × 6253 . Now we divide 7, 11, 13 into 6253 and find that 6253 = 13 × 481 . Next, we try to factor 481, starting with 13. In fact, 481 = 13 × 37 . Finally, we try to factor 37. Again, we start at 13, but now we are past √ 37 ≈ 6 . 08, so we are done. The factorization is 6253 = 7 × 13 2 × 37 . Example. Let n = 401. Dividing 401 by the primes 2, 3, 5, 7, 11, 13, 17, 19, we find that 401 has no prime factors less than or equal to √ 401 ≈ 20 .
eBook - PDFProofs and Ideas
A Prelude to Advanced Mathematics
- B. Sethuraman(Author)
- 2021(Publication Date)
- American Mathematical Society(Publisher)
10 Unique Prime Factorization in the Integers In this chapter we will revisit a result we are familiar with from our school days, and which we have used already in exercises earlier in the book (e.g. in Exericse 1.17, Chapter 1, or in Exercise 4.24, Chapter 4). This is the theorem of unique prime fac-torization of the integers, a profound theorem actually. In fact, this theorem does not hold in every number system (for instance, for numbers of the form ? + ?√ −5 , where ? and ? are arbitrary integers). The failure of this theorem to hold in other number systems in turn leads to a whole body of mathematics called algebraic number theory. We will prove this theorem carefully here, and then examine some consequences. First, recall from Example 5.38, Chapter 5, the definition of primes: they are those positive integers ( ≥ 2 ) whose only divisors are 1 and themselves. We now state the theorem: Theorem 10.1. (Unique Prime Factorization Theorem.) Every integer greater than 1 can be factored into a product of primes. The primes that appear in the factorization are uniquely determined, except for the order in which they appear in the factorization. What we mean by “uniqueness of the primes except for the order in which they appear” is the following: if we consider the factorization 108 = 2 2 ⋅ 3 3 , then no matter how someone else arrives at a factorization of 108 into a product of primes, there must be two 2 s and three 3? and no other primes in the factorization. At worst, this other person may write the factorization in a different order as, say 108 = 2 ⋅ 3 ⋅ 2 ⋅ 3 ⋅ 3 , or say 108 = 3 ⋅ 3 ⋅ 2 ⋅ 3 ⋅ 2 . As it turns out, the existence of the factorization is quite easy to prove, but the uniqueness (up to order, that is) takes a bit more work. But the reward for the work is that we will see new ideas that we would not have seen earlier, ideas that have far reaching generalizations to other numbers than just the integers.
eBook - PDF- James S. Kraft, Lawrence C. Washington(Authors)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 11 Primality and Factorization Two fundamental computational problems in number theory are finding large primes and factoring composite numbers. Although these prob-lems are related, they have intrinsic differences. It is relatively easy to prove that a number is composite but, once this has been done, it is much harder to find its factors. With the popularity of cryptographic algorithms that use primes, primality testing and factoring have be-come very important. In this chapter, we show how to decide whether a number is prime or composite. Then we discuss some factorization methods that are used in practice. 11.1 Trial Division and Fermat Factorization The easiest method for primality testing and factorization is trial di-vision. If we want to factor an integer n > 1, we divide n by all the primes p ≤ √ n (by Proposition 1.8) until we find a prime factor. If we don’t find a factor, n is prime. If we find a factor p 1 , then we continue to try to factor n 1 = n/p 1 . To factor n 1 , we could start at the beginning, dividing 2, 3, 5, · · · into n 1 . But we have already taken care of the primes less than p 1 , so we can start at p 1 and continue until either we get to √ n 1 or we find another prime factor p 2 . Then we try to factor n 2 = n 1 /p 2 . This process eventually terminates and yields the factorization of n . Example. Let n = 43771. It is not divisible by 2, 3, and 5, but it is 275 276 Chapter 11 Primality and Factorization divisible by 7: 43771 = 7 × 6253 . Now we divide 7, 11, 13 into 6253 and find that 6253 = 13 × 481 . Next, we try to factor 481, starting with 13. In fact, 481 = 13 × 37 . Finally, we try to factor 37. Again, we start at 13, but now we are past √ 37 ≈ 6 . 08, so we are done. The factorization is 6253 = 7 × 13 2 × 37 . Example. Let n = 401. Dividing 401 by the primes 2, 3, 5, 7, 11, 13, 17, 19, we find that 401 has no prime factors less than or equal to √ 401 ≈ 20 .
eBook - PDFThe Higher Arithmetic
An Introduction to the Theory of Numbers
- H. Davenport(Author)
- 2008(Publication Date)
- Cambridge University Press(Publisher)
These considerations extend easily to more than two numbers. But then it is important to note the two kinds of relative primality that are possible. Several numbers are said to be relatively prime if there is no number greater than 1 which divides all of them; they are said to be relatively prime in pairs if no two of them have a common factor greater than 1. The condition for the former is that there shall be no one prime occurring in all the numbers, and for the latter it is that there shall be no prime that occurs in any two of the numbers. There are several simple theorems on divisibility which one is inclined to think of as obvious, but which are in fact only obvious in the light of the uniqueness of factorization into primes. For example, if a number divides the product of two numbers and is relatively prime to one of them it must divide the other. If a divides bc and is relatively prime to b, the prime 16 The Higher Arithmetic factorization of a is contained in that of bc but has nothing in common with that of b, and is therefore contained in that of c. 6. Euclid’s algorithm In Prop. 2 of Book VII, Euclid gave a systematic process, or algorithm, for finding the highest common factor of two given numbers. This algorithm provides a different approach to questions of divisibility from that adopted in the last two sections, and we therefore begin again without assuming anything except the mere definition of divisibility. Let a and b be two given natural numbers, and suppose that a > b. We propose to investigate the common divisors of a and b. If a is divisible by b, then the common divisors of a and b consist simply of all divisors of b, and there is no more to be said. If a is not divisible by b, we can express a as a multiple of b together with a remainder less than b, that is a = qb + c, where c < b.
eBook - PDF- (Author)
- 2015(Publication Date)
- For Dummies(Publisher)
Think of the number you start with as being the trunk of the tree and the prime factors as being at the ends of the roots. To use the tree method, you write down your number and find two factors with a product is that number. Then you find factors for the two factors, and factors for the factors of the factors and so on. You’re finished when the lowest part of any root system is a prime number. Then you collect all those prime numbers for the factorisation. Figure 8‐1 shows an example of finding the prime factorisation of 6,350,400 using a factor tree. 172 Part II: Algebra is Part of Everything Now you collect all the prime numbers at the ends of the roots. I see the prime factors as: 7, 3, 7, 3, 3, 2, 2, 2, 2, 3, 2, 2, 5, 5. Putting them in order, I get: = ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ = ⋅ ⋅ ⋅ 6,350,400 2 2 2 2 2 2 3 3 3 3 5 5 7 7 2 3 5 7 6 4 2 2 You may not have created a tree the same way I did. Everyone sees different multiples and factors and has his or her favourites as far as dividing. I like to stick to numbers I can divide in my head. But you may be a calculator person. The great thing is that every way works and gives you the same final answer. Wrapping your head around the rules of divisibility The techniques for finding prime factorisations work just fine, as long as you have a good head start on what divides a number evenly. You probably already know the rules for dividing by 2 or 5 or 10. But many other numbers have very helpful rules or gimmicks for just looking at the number and seeing whether it’s divisible by a particular factor. In Table 8‐1, I give you many of the more commonly used rules of divisibility. Some are easier to use than others. Notice that I don’t have the numbers in order; I prefer to group the numbers by the types of rules used. Figure 8-1: Finding the prime factors using a tree.
eBook - PDF- Richard A. Mollin(Author)
- 2002(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 5 Factoring The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. C. F. Gauss 5.1 5.1 Universal Exponent Method The problem of primality testing covered in Chapter 4 is less difficult, in general, than the topic of this chapter. We have already learned that public-key cryptosystems such as RSA, base their security upon the presumed difficulty of integer factorization, a term that we now make precise. ◆ The Integer Factorization Problem (IFP) Given n ∈ N find primes p j for j = 1 , 2 , . . . , r ∈ N with p 1 < p 2 < · · · < p r such that n = r j =1 p e j j . Essentially what the conclusion of the IFP says is the content of the Funda-mental Theorem of Arithmetic (see Theorem C.6 on page 213). A subset of the IFP (which is actually the same as the IFP in the case of an RSA modulus) is the notion of splitting n ∈ N , by which we mean that we find r, s ∈ N such that 1 < r ≤ s < n and n = rs . 5.1 Carl Friederich Gauss (1777–1855) is perhaps the best-known and possibly the greatest mathematician of all time. Evidence of his genius emerged at age three when he found an error in his father’s bookkeeping. By age eight he had astonished his teacher, B¨ uttner, by rapidly calculating ∑ 100 j =1 j with the simple observation that the fifty pairs ( j + 1 , 100 − j ) for j = 0 , 1 , . . . , 49 each sum to 101 for a total of 5050. Ultimately, he entered the Collegium Carolinum with funding from the Duke of Brunswick, to whom he dedicated his magnum opus Disquisitiones Arithmeticae [95], published in 1801, from which the above quote was taken. By 1795, he entered G¨ottingen University and received his doctorate at the age of twenty. His accomplishments are too numerous to list here (see [164] for more of them), but it is safe to say that his work continues to have influence to this day.
eBook - PDF- Richard A. Mollin(Author)
- 2006(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 6 Factoring 6.1 Classical Factorization Methods Given the importance of factoring in the security of RSA and other cryp-tosystems, it is worth our having a closer look at the issue to which we devote this chapter. We first look at the following basic building block. ◆ The Integer Factoring Problem — (IFP) Given n ∈ N , find primes p j for j = 1 , 2 , . . . , r ∈ N with p 1 < p 2 < · · · < p n and e j ∈ N for j = 1 , 2 , . . . , r , such that n = r j =1 p e j j . A simpler problem than the IFP is the notion of splitting of n ∈ N , which means the finding of factors r, s ∈ N such that 1 < r ≤ s such that n = rs . Of course, with an RSA modulus, splitting and the IFP are the same thing. Yet, in order to solve the IFP for any integer, one merely splits n , then splits n/r and s if they are both composite, and so on until we have a complete factorization. Now we discuss some older methods that still have relevance for the methods of today. Trial Division The oldest method of splitting n is trial division , by which we mean dividing n by all primes up to √ n . For n < 10 8 , or within that neigh-bourhood, this is not an unreasonable method in our computer-savvy world. However, for larger integers, we need more elaborate methods. Fermat Factoring On page 201, we discussed Fermat’s method for fac-toring, which we called his difference of squares method . Although the order of magnitude (see page 67) of Fermat factoring can be shown to be O ( n 1 / 2 ), Lehman has shown how to reduce the complexity to O ( n 1 / 3 ) when combined 207 208 6. Factoring with trial division. This is all contained in [49], complete with a computer pro-gram. There is also a method, from D.H. Lehmer, for speeding up the Fermat method when all factors are of the form 2 k + 1 (see [10]). Euler’s Factoring Method This method applies only to integers of the form n = x 2 + ay 2 = z 2 + aw 2 , where x = z and y = w .
eBook - PDFPerfect, Amicable And Sociable Numbers: A Computational Approach
A Computational Approach
- Song Y Yan(Author)
- 1996(Publication Date)
- World Scientific(Publisher)
The idea of the second phase in ECM is to find a factor in the case that the first phase terminates with a group element P ^ /, such that | < P > | is reasonably small (say 0(m 2 )). (Here < P > is the cyclic group generated by P.) There are several possible implementations of the second phase. One of the simplest uses a pseudorandom walk in < P >. By the birthday paradox argument, there is a good chance that two points in the random walk will coincide after 0(J < P > |) steps, and when this occurs a nontrivial factor of N can usually be found (see [24] and [82] for more detailed information on the implementation issues of ECM. Brent's paper [25] provides also an excellent survey of methods for primality testing and integer factorization; some of the testing and factoring methods introduced in this chapter are based on [25]). 2.3.6 Progress on Factoring Fermat Numbers Fermat numbers as well as Mersenne numbers have had a profound effect on the development of factoring and primality testing techniques. This is because of their long history and their consequent use as a sort of informal bench mark for factoring techniques. In fact, Fermat numbers act as a mirror reflecting the progress of factoring large integers. In this subsection we present a brief survey of the progress on factoring Fermat numbers. Definition 2.3.1 Numbers of the form F n — 2 2 + 1, whether prime or com-posite, are called Fermat numbers. A Fermat number is called prime Fermat number if it is prime. A Fermat number is called composite Fermat number if it is composite. These special numbers obey the simple recursion: F n+l = (F n - l) 2 + 1 (2.69) or F n+1 - 2 = F n (F n -2) (2.70) which leads to the interesting product: F n+l -2 = F 0 F 1 ---F n . (2.71) 90 2. MATHEMATICAL TOOLS In other words, F n -2 is divisible by all lower Fermat numbers: F„_ f c |(F n -2), l < f c < n .
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
