Copyright © Philip M. Parker, INSEAD. Terms of Use.

Factoring

Specialty Definition: Factoring

Top     

Specialty Definition: Factorization

(From Wikipedia, the free Encyclopedia)

In mathematics, factorization or factoring is the decomposition of an object into a list of (smaller) objects, or factors, which when multiplied together give the original. For example, the number 15 factors into primes as 3 × 5; and the polynomial x² - 4 factors as (x - 2)(x + 2).

The aim of factoring is usually to reduce something to "basic building blocks", such as numbers to prime numbers, or polynomials to irreducible polynomials. Factoring integers is covered by the fundamental theorem of arithmetic and factoring polynomials by the fundamental theorem of algebra.

Integer factorization for large integers appears to be a difficult problem. There is no known method to carry it out quickly. Its complexity is the basis of the assumed security of some public key cryptography algorithms.

A matrix can also be factorized into a product of matrices of special types, for an application in which that form is convenient. One major example of this uses an orthogonal or unitary matrix, and a triangular matrix. There are different types: QR decomposition, LQ, QL, RQ, RZ.

Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Factorization."

Top     

Integer factorization

(From Wikipedia, the free Encyclopedia)

In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. For example, given the number 45, the prime factorization would be 3²·5. The factorization is always unique, according to the fundamental theorem of arithmetic. This problem is of significance in mathematics, cryptography, complexity theory, and quantum computers.

The complete list of factors can be derived from the prime factorization by incrementing the exponents from zero until the number is reached. For example, since 45 = 3²·5, 45 is divisible by 3⁰·5⁰, 3⁰·5¹, 3¹·5⁰, 3¹·5¹, 3²·5⁰, and 3²·5¹, or 1, 5, 3, 15, 9, and 45. In contrast, the prime factorization only includes prime factors.

Given two large prime numbers, it is easy to multiply them together. However, given their product, it appears to be difficult to find the factors. This is relevant for many modern systems in cryptography. If a fast method were found for solving the integer factorization problem, then several important cryptographic systems would be broken, including the RSA public-key algorithm, and the Blum Blum Shub random number generator.

Although fast factoring is one way to break these systems, there may be other ways to break them that don't involve factoring. So it is possible that the integer factorization problem is truly hard, yet these systems can still be broken quickly. A rare exception is the Blum Blum Shub generator. It has been proved to be exactly as hard as integer factorization. There is no way to break it without also solving integer factorization quickly.

If a large, n-bit number is the product of two primes that are roughly the same size, then no algorithm is known that can factor in polynomial time. That means there is no known algorithm that can factor it in time O(n^k) for any constant k. There are algorithms, however, that are faster than &Theta(eⁿ). In other words, the best known algorithms are sub-exponential, but super-polynomial. In particular, the best known asymptotic running time is for the general number field sieve (GNFS) algorithm, which is:

For an ordinary computer, GNFS is the best known algorithm for large n. For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time! This will have significant implications for cryptography if a large quantum computer is ever built. Shor's algorithm takes only O(n³) time and O(n) space. Forms of the algorithm are known that use only about 2n qubits. In 2001, the first 7-qubit quantum computer became the first to run Shor's algorithm. It factored the number 15.

It is not known exactly which complexity classes contain the integer factorization problem. The decision-problem form of it ("does N have a factor less than M?") is known to be in both NP and co-NP. This is because both YES and NO answers can be checked if given the prime factors along with their primality proofs. It is known to be in BQP because of Shor's algorithm. It is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find polynomial-time algorithms for it and failed, therefore it is widely suspected to be outside P.

Interestingly, the decision problem "is N a composite number?" (or equivalently: "is N a prime number?") appears to be much easier than the problem of actually finding the factors of N. Specifically, the former can be solved in polynomial time (in the number n of digits of N), according to a recent preprint given in the references, below. In addition, there are a number of probabilistic algorithms that can test primality very quickly if one is willing to accept the small possibility of error. The easiness of prime testing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with.

External Resources:

• Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp.3-22. download
• Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002, http://www.cse.iitk.ac.in/news/primality.html
• The "PRIMES is in P" FAQ http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html

  Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Integer factorization."

Top     

Ring ideal

(From Wikipedia, the free Encyclopedia)

In abstract algebra, an ideal of a ring R is a subset I of R which is closed under R-linear combinations, in a sense made precise below.

Definitions

To accommodate non-commutative rings, we must distinguish three cases: left ideals, right ideals, and two-sided ideals.

A subset I of the ring R is a left ideal of R if

1: the zero element 0 of R belongs to I

2: for any a,b in I, we have a + b in I, and

3L: for any a in I and r in R, we have ra in I

A subset I of R is a right ideal of R if, in addition to properties 1 and 2 from above, it satisfies

3R: for any a in I and r in R, we have ar in I

A subset which is both a left and a right ideal (that is, it satisfies properties 1, 2, 3L, and 3R) is called a two-sided ideal of R. The term ideal alone is usually short for "two-sided ideal".

If the ring R is commutative, then all three sorts of ideals are the same. If the ring is noncommutative, however, then they may be different.

Examples

• The even integers form an ideal in the ring Z of all integers; it is usually denoted by 2Z.
• The set of all polynomials with real coefficients which are divisible by the polynomial x² + 1 is an ideal in the ring of all polynomials.
• The set of all n-by-n matrices whose last column is zero forms a left ideal in the ring of all n-by-n matrices. It is not a right ideal. The set of all n-by-n matrices whose last row is zero forms a right ideal but not a left ideal.
• The ring C(R) of all continuous functions f from R to R contains the ideal of all continuous functions f such that f(1) = 0. Another ideal in C(R) is given by those functions which vanish for large enough arguments, i.e. those continuous functions f for which there exists a number L > 0 such that f(x) = 0 whenever |x| > L.
• {0} and R are ideals in every ring R. If R is commutative, then R is a field iff it has precisely two ideals, {0} and R.

Further properties of ideals

Because zero belongs to it, any ideal is nonempty. In fact, property 1 in the definition can be replaced with simply the requirement that I be nonempty.

Any left, right or two-sided ideal is a subgroup of the additive group (R,+).

The ring R can be considered as a left module over itself, and the left ideals of R are then seen as the submodules of this module. Similarly, the right ideals are submodules of R as a right module over itself, and the two-sided ideals are submodules of R as a bimodule over itself. If R is commutative, then all three sorts of module are the same, just as all three sorts of ideal are the same.

Types of ideals

The first two examples above are principal ideals; the principal (left) ideal generated by an element a in R is Ra := {ra : r in R}. The principal right ideal aR is defined similarly; and these two principal ideals generated by a are identical (and hence a two-sided ideal) if the ring is commutative. In that case, it's common to denote the principal ideal by <a> or (a).

An ideal I is called proper if I is not equal to R. An ideal is proper if and only if it doesn't contain 1. A proper ideal is called maximal if the only proper ideal it is contained in is itself. Every ideal is contained in a maximal ideal, a consequence of Zorn's lemma. A proper ideal I is called prime if, whenever ab belongs to I, then so does a or b (or both). Every maximal ideal is prime.

Factor rings (quotient rings) and kernels

Ideals are important because they appear as the kernels of ring homomorphisms and allow one to define factor rings, as will be described next.

Recall that a function f from R to S is a ring homomorphism iff f(a + b) = f(a) + f(b) and f(ab) = f(a) f(b) for all a, b in R and f(1) = 1. Then the kernel of f is defined as

ker(f) := {a in R : f(a) = 0}.

The kernel is always a two-sided ideal of R.

Conversely, if we start with a two-sided ideal I of R, then we may define a congruence relation ~ on R as follows: a ~ b if and only if b - a is in I. In case a ~ b, we say that a and b are congruent modulo I. The equivalence class of the element a in R is given by

[a] = a + I := {a + r : r in I}.

The set of all such equivalence classes is denoted by R/I; it becomes a ring, the factor ring or quotient ring of R modulo I, if one defines

• (a + I) + (b + I) = (a + b) + I;
• (a + I) * (b + I) = (ab) + I.

(But note that these quotient rings are unrelated to the quotient field, or field of fractions, of an integral domain, and also unrelated to the rings of quotients resulting from localization of rings.)

The map p from R to R/I defined by p(a) = a + I is a surjective ring homomorphism (or regular epimorphism) whose kernel is the original ideal I. In summary, we see that ideals are precisely the kernels of ring homomorphisms.

If R is commutative and I is a maximal ideal, then the factor ring R/I is a field; if I is only a prime ideal, then R/I is only an integral domain.

The most extreme examples of factor rings are provided by modding out by the most extreme ideals, {0} and R itself. R/{0} is naturally isomorphic to R, and R/R is the trivial ring {0}.

Ideal operations

The sum and the intersection of ideals is again an ideal; with these two operations as join and meet, the set of all ideals of a given ring forms a lattice.

If A is any subset of the ring R, then we can define the ideal generated by A to be the smallest ideal of R containing A; it is denoted by <A> or (A) and contains all finite sums of the form

r₁a₁s₁ + ··· + r_na_ns_n

with each r_i and s_i in R and each a_i in A. The principal ideals mentioned above are the special case when A is just the singleton {a}.

The product of two ideals I and J is defined to be the ideal IJ generated by all products of the form ab with a in I and b in J. It is contained in the intersection of I and J.

Important properties of these ideal operations are recorded in the Noether isomorphism theorems.

Ideals as "ideal numbers"

The term "ideal" comes from "ideal number": ideals were seen as a generalization of the concept of number. In the ring Z of integers, every ideal can be generated by a single number (so Z is a principal ideal domain), and the ideal determines the number up to its sign. The concepts of "ideal" and "number" are therefore almost identical in Z (and in any principal ideal domain). In other rings, it turned out that the concept of "ideal" allows one to generalize several properties of numbers. For instance, in general rings one studies prime ideals instead of prime numbers, one defines coprime ideals as a generalization of coprime numbers, and one can prove a generalized Chinese remainder theorem about ideals. In a certain class of rings important in number theory, the Dedekind domains, one can even recover a version of the fundamental theorem of arithmetic: in these rings, every nonzero ideal can be uniquely written as a product of prime ideals.

See also:

• Modular arithmetic
• Chinese remainder theorem
• Noether isomorphism theorem

  Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Ring ideal."

Top     

Top     

Top     

Commercial Usage: Factoring

Top     

Non-Fiction Usage: Factoring

Top     

Usage Frequency: Factoring

Source: compiled by the editor from several corpora; see credits.

Top     

Usage in Company Names: Factoring

Source: compiled by the editor from Icon Group International, Inc.

Top     

Expression: Factoring

Top     

Frequency of Internet Keywords: Factoring

Top     

Modern Translation: Factoring

Top     

Misspellings: Factoring

Top     

Rhyming with "Factoring"

Top     

Anagrams: Factoring

Top