|
Lattice Sieving
Lattice sieving is a technique for finding smooth number, smooth values of a bivariate polynomial f(a,b) over a large region. It is almost exclusively used in conjunction with the number field sieve. The original idea of the lattice sieve came from John Pollard (mathematician), John Pollard.Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag. The algorithm implicitly involves the ideal (ring theory), ideal structure of the number field of the polynomial; it takes advantage of the theorem that any prime ideal above some rational prime ''p'' can be written as p \mathbb Z[\alpha] + (u + v \alpha) \mathbb Z[\alpha]. One then picks many prime numbers ''q'' of an appropriate size, usually just above the factor base limit, and proceeds by :: For each ''q'', list the prime ideals above ''q'' by factorising the polynomial f(a,b) over GF(q) ::: For each of these prime ideals, which are called 'spe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Smooth Number
In number theory, an ''n''-smooth (or ''n''-friable) number is an integer whose prime factors are all less than or equal to ''n''. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. The 2-smooth numbers are just the powers of 2, while 5-smooth numbers are known as regular numbers. Definition A positive integer is called B-smooth if none of its prime factors are greater than B. For example, 1,620 has prime factorization 22 × 34 × 5; therefore 1,620 is 5-smooth because none of its prime factors are greater than 5. This definition includes numbers that lack some of the smaller prime factors; for example, both 10 and 12 are 5-smooth, even though they miss out the prime factors 3 and 5, resp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Number Field Sieve
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( \left(\sqrt + o(1)\right)(\ln n)^(\ln \ln n)^\right) =L_n\left .html"_;"title="frac,\sqrt[3">frac,\sqrt[3right/math> (in_L-notation.html" ;"title="">frac,\sqrt[3right.html" ;"title=".html" ;"title="frac,\sqrt[3">frac,\sqrt[3right">.html" ;"title="frac,\sqrt[3">frac,\sqrt[3right/math> (in L-notation">">frac,\sqrt[3right.html" ;"title=".html" ;"title="frac,\sqrt[3">frac,\sqrt[3right">.html" ;"title="frac,\sqrt[3">frac,\sqrt[3right/math> (in L-notation), where is the natural logarithm. It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number apart from prime powers (which are trivial to factor by taking roots). The pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
John Pollard (mathematician)
John M. Pollard (born 1941) is a British mathematician who has invented algorithms for the factorization of large numbers and for the calculation of discrete logarithms. His factorization algorithms include the rho, ''p'' − 1, and the first version of the special number field sieve, which has since been improved by others. His discrete logarithm algorithms include the rho algorithm for logarithms and the kangaroo algorithm. He received the RSA Award for Excellence in Mathematics RSA may refer to: Organizations Academia and education * Rabbinical Seminary of America, a yeshiva in New York City *Regional Science Association International (formerly the Regional Science Association), a US-based learned society *Renaissance S .... External links John Pollard's web site Living people 20th-century British mathematicians 21st-century British mathematicians Number theorists Place of birth missing (living people) 1941 births {{UK-mathematician-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ideal (ring Theory)
In ring theory, a branch of abstract algebra, an ideal of a ring is a special subset of its elements. Ideals generalize certain subsets of the integers, such as the even numbers or the multiples of 3. Addition and subtraction of even numbers preserves evenness, and multiplying an even number by any integer (even or odd) results in an even number; these closure and absorption properties are the defining properties of an ideal. An ideal can be used to construct a quotient ring in a way similar to how, in group theory, a normal subgroup can be used to construct a quotient group. Among the integers, the ideals correspond one-for-one with the non-negative integers: in this ring, every ideal is a principal ideal consisting of the multiples of a single non-negative number. However, in other rings, the ideals may not correspond directly to the ring elements, and certain properties of integers, when generalized to rings, attach more naturally to the ideals than to the elements of the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Number Field
In mathematics, an algebraic number field (or simply number field) is an extension field K of the field of rational numbers such that the field extension K / \mathbb has finite degree (and hence is an algebraic field extension). Thus K is a field that contains \mathbb and has finite dimension when considered as a vector space over The study of algebraic number fields, and, more generally, of algebraic extensions of the field of rational numbers, is the central topic of algebraic number theory. This study reveals hidden structures behind usual rational numbers, by using algebraic methods. Definition Prerequisites The notion of algebraic number field relies on the concept of a field. A field consists of a set of elements together with two operations, namely addition, and multiplication, and some distributivity assumptions. A prominent example of a field is the field of rational numbers, commonly denoted together with its usual operations of addition and multiplication. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prime Ideal
In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together with the zero ideal. Primitive ideals are prime, and prime ideals are both primary and semiprime. Prime ideals for commutative rings An ideal of a commutative ring is prime if it has the following two properties: * If and are two elements of such that their product is an element of , then is in or is in , * is not the whole ring . This generalizes the following property of prime numbers, known as Euclid's lemma: if is a prime number and if divides a product of two integers, then divides or divides . We can therefore say :A positive integer is a prime number if and only if n\Z is a prime ideal in \Z. Examples * A simple example: In the ring R=\Z, the subset of even numbers is a prime ideal. * Given an integral domain R ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Factor Base
In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer. Usage in factoring algorithms A factor base is a relatively small set of distinct prime numbers ''P'', sometimes together with -1. Say we want to factorize an integer ''n''. We generate, in some way, a large number of integer pairs (''x'', ''y'') for which x \neq \pm y, x^2 \equiv y^2 \pmod, and x^2 \pmod \texty^2 \pmod can be completely factorized over the chosen factor base—that is, all their prime factors are in ''P''. In practice, several integers ''x'' are found such that x^2 \pmod has all of its prime factors in the pre-chosen factor base. We represent each x^2 \pmod expression as a vector of a matrix with integer entries being the exponents of factors in the factor base. Linear combinations of the rows corresponds to multiplication of these expressions. A linear dependence re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lattice Reduction
In mathematics, the goal of lattice basis reduction is to find a basis with short, nearly orthogonal vectors when given an integer lattice basis as input. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice. Nearly orthogonal One measure of ''nearly orthogonal'' is the orthogonality defect. This compares the product of the lengths of the basis vectors with the volume of the parallelepiped they define. For perfectly orthogonal basis vectors, these quantities would be the same. Any particular basis of n vectors may be represented by a matrix B, whose columns are the basis vectors b_i, i = 1, \ldots, n. In the fully dimensional case where the number of basis vectors is equal to the dimension of the space they occupy, this matrix is square, and the volume of the fundamental parallelepiped is simply the absolute value of the determinant of this matrix \det(B). If the number of vectors is less than the dimension ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sieve Region
A sieve, fine mesh strainer, or sift, is a device for separating wanted elements from unwanted material or for controlling the particle size distribution of a sample, using a screen such as a woven mesh or net or perforated sheet material. The word ''sift'' derives from ''sieve''. In cooking, a sifter is used to separate and break up clumps in dry ingredients such as flour, as well as to aerate and combine them. A strainer (see Colander), meanwhile, is a form of sieve used to separate suspended solids from a liquid by filtration. Industrial strainer Some industrial strainers available are simplex basket strainers, duplex basket strainers, T-strainers and Y-strainers. Simple basket strainers are used to protect valuable or sensitive equipment in systems that are meant to be shut down temporarily. Some commonly used strainers are bell mouth strainers, foot valve strainers, basket strainers. Most processing industries (mainly pharmaceutical, coatings and liquid food indust ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
