|
Algebraic-group Factorisation Algorithms
{{unreferenced, date=January 2015 Algebraic-group factorisation algorithms are algorithms for factoring an integer ''N'' by working in an algebraic group defined modulo ''N'' whose group structure is the direct sum of the 'reduced groups' obtained by performing the equations defining the group arithmetic modulo the unknown prime factors ''p''1, ''p''2, ... By the Chinese remainder theorem, arithmetic modulo ''N'' corresponds to arithmetic in all the reduced groups simultaneously. The aim is to find an element which is not the identity of the group modulo ''N'', but is the identity modulo one of the factors, so a method for recognising such ''one-sided identities'' is required. In general, one finds them by performing operations that move elements around and leave the identities in the reduced groups unchanged. Once the algorithm finds a one-sided identity all future terms will also be one-sided identities, so checking periodically suffices. Computation proceeds by picking an arbit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer Factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public-key encryption and the RSA digital signature. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing. In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number ( RSA-240) utilizing approximately 900 core-years of computing power. The researchers estimated that a 1024-bit R ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algebraic Group
In mathematics, an algebraic group is an algebraic variety endowed with a group structure which is compatible with its structure as an algebraic variety. Thus the study of algebraic groups belongs both to algebraic geometry and group theory. Many groups of geometric transformations are algebraic groups; for example, orthogonal groups, general linear groups, projective groups, Euclidean groups, etc. Many matrix groups are also algebraic. Other algebraic groups occur naturally in algebraic geometry, such as elliptic curves and Jacobian varieties. An important class of algebraic groups is given by the affine algebraic groups, those whose underlying algebraic variety is an affine variety; they are exactly the algebraic subgroups of the general linear group, and are therefore also called ''linear algebraic groups''. Another class is formed by the abelian varieties, which are the algebraic groups whose underlying variety is a projective variety. Chevalley's structure theorem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modular Arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book '' Disquisitiones Arithmeticae'', published in 1801. A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Simple addition would result in , but clocks "wrap around" every 12 hours. Because the hour number starts over at zero when it reaches 12, this is arithmetic ''modulo'' 12. In terms of the definition below, 15 is ''congruent'' to 3 modulo 12, so "15:00" on a 24-hour clock is displayed "3:00" on a 12-hour clock. Congruence Given an integer , called a modulus, two integers and are said to be congruent modulo , if is a divisor of their difference (that is, if there is an integer such that ). Congruence modu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chinese Remainder Theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of these integers, under the condition that the divisors are pairwise coprime (no two divisors share a common factor other than 1). For example, if we know that the remainder of ''n'' divided by 3 is 2, the remainder of ''n'' divided by 5 is 3, and the remainder of ''n'' divided by 7 is 2, then without knowing the value of ''n'', we can determine that the remainder of ''n'' divided by 105 (the product of 3, 5, and 7) is 23. Importantly, this tells us that if ''n'' is a natural number less than 105, then 23 is the only possible value of ''n''. The earliest known statement of the theorem is by the Chinese mathematician Sun-tzu in the '' Sun-tzu Suan-ching'' in the 3rd century CE. The Chinese remainder theorem is widely used for computing with l ... [...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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multiplicative Group
In mathematics and group theory, the term multiplicative group refers to one of the following concepts: *the group under multiplication of the invertible elements of a field, ring, or other structure for which one of its operations is referred to as multiplication. In the case of a field ''F'', the group is , where 0 refers to the zero element of ''F'' and the binary operation • is the field multiplication, *the algebraic torus GL(1).. Examples *The multiplicative group of integers modulo ''n'' is the group under multiplication of the invertible elements of \mathbb/n\mathbb. When ''n'' is not prime, there are elements other than zero that are not invertible. * The multiplicative group of positive real numbers \mathbb^+ is an abelian group with 1 its identity element. The logarithm is a group isomorphism of this group to the additive group of real numbers, \mathbb. * The multiplicative group of a field F is the set of all nonzero elements: F^\times = F -\, under the mu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Greatest Common Divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is denoted \gcd (x,y). For example, the GCD of 8 and 12 is 4, that is, \gcd (8, 12) = 4. In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include highest common factor (hcf), etc. Historically, other names for the same concept have included greatest common measure. This notion can be extended to polynomials (see Polynomial greatest common divisor) and other commutative rings (see below). Overview Definition The ''greatest common divisor'' (GCD) of two nonzero integers and is the greatest positive integer such that is a divisor of both and ; that is, there are integers and such that and , and is the larges ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Williams' P + 1 Algorithm
In computational number theory, Williams's ''p'' + 1 algorithm is an integer factorization algorithm, one of the family of algebraic-group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number ''N'' to be factored contains one or more prime factors ''p'' such that ''p'' + 1 is smooth, i.e. ''p'' + 1 contains only small factors. It uses Lucas sequences to perform exponentiation in a quadratic field. It is analogous to Pollard's ''p'' − 1 algorithm. Algorithm Choose some integer ''A'' greater than 2 which characterizes the Lucas sequence: :V_0=2, V_1=A, V_j=AV_-V_ where all operations are performed modulo ''N''. Then any odd prime ''p'' divides \gcd(N,V_M-2) whenever ''M'' is a multiple of p-(D/p), where D=A^2-4 and (D/p) is the Jacobi symbol. We require that (D/p)=-1, that is, ''D'' should be a quadratic non-residue modulo ''p''. But as we don't know ''p'' beforehand, more than one value of ''A'' may ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quadratic Residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic nonresidue modulo ''n''. Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers. History, conventions, and elementary facts Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries established theorems and formed conjectures about quadratic residues, but the first systematic treatment is § IV of Gauss's '' Disquisitiones Arithmeticae'' (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that if the context makes it clear, the adjective "quadratic" may be dropped ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Elliptic Curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If the field's characteristic is different from 2 and 3, then the curve can be described as a plane algebraic curve which consists of solutions for: :y^2 = x^3 + ax + b for some coefficients and in . The curve is required to be non-singular, which means that the curve has no cusps or self-intersections. (This is equivalent to the condition , that is, being square-free in .) It is always understood that the curve is really sitting in the projective plane, with the point being the unique point at infinity. Many sources define an elliptic curve to be simply a curve given by an equation of this form. (When the coefficient field has characteristic 2 or 3, the above equation is not quite general enough to include all non-singular ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inverse Function
In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon X\to Y, its inverse f^\colon Y\to X admits an explicit description: it sends each element y\in Y to the unique element x\in X such that . As an example, consider the real-valued function of a real variable given by . One can think of as the function which multiplies its input by 5 then subtracts 7 from the result. To undo this, one adds 7 to the input, then divides the result by 5. Therefore, the inverse of is the function f^\colon \R\to\R defined by f^(y) = \frac . Definitions Let be a function whose domain is the set , and whose codomain is the set . Then is ''invertible'' if there exists a function from to such that g(f(x))=x for all x\in X and f(g(y))=y for all y\in Y. If is invertible, then there is exactly one function ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
