Faster access than browser!
86 relations: Addison-Wesley, Adleman–Pomerance–Rumely primality test, Advanced Micro Devices, AKS primality test, Algebraic number theory, Algebraic-group factorisation algorithm, Algorithm, Big O notation, Binary search algorithm, Bit, BQP, Carl Pomerance, Co-NP, Co-NP-complete, Complexity class, Composite number, Computational complexity theory, Computer science, Congruence of squares, Continued fraction factorization, Cryptography, David Bressoud, Decision problem, Discriminant, Dixon's factorization method, Donald Knuth, Elliptic curve, Empty product, Euler's factorization method, Factorization, Fermat's factorization method, FNP (complexity), FP (complexity), Function problem, Fundamental theorem of arithmetic, General number field sieve, Generalized Riemann hypothesis, Generating set of a group, Greatest common divisor, Group (mathematics), Hacker's Delight, Ideal class group, International Association for Cryptologic Research, Kronecker symbol, L-notation, Lenstra elliptic-curve factorization, Manindra Agrawal, Mathematics, Maurice Kraitchik, Multiplicative partition, ..., Nature (journal), NP (complexity), NP-completeness, NP-intermediate, Number theory, Opteron, Partition (number theory), Pearson Education, Peter Shor, Pollard's p − 1 algorithm, Pollard's rho algorithm, Primality test, Prime number, Public-key cryptography, Quadratic form, Quadratic sieve, Quantum computing, Randomized algorithm, Rational sieve, Richard Crandall, RSA (cryptosystem), RSA numbers, RSA problem, Semiprime, Shanks's square forms factorization, Shor's algorithm, Smooth number, Special number field sieve, Stan Wagon, Sylow theorems, The Art of Computer Programming, Time complexity, Trial division, UP (complexity), Wheel factorization, Williams's p + 1 algorithm. Expand index (36 more) »
Addison-Wesley
Addison-Wesley is a publisher of textbooks and computer literature.
New!!: Integer factorization and Addison-Wesley · See more »
Adleman–Pomerance–Rumely primality test
In computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime.
New!!: Integer factorization and Adleman–Pomerance–Rumely primality test · See more »
Advanced Micro Devices
Advanced Micro Devices, Inc. (AMD) is an American multinational semiconductor company based in Santa Clara, California, that develops computer processors and related technologies for business and consumer markets.
New!!: Integer factorization and Advanced Micro Devices · See more »
AKS primality test
The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled "PRIMES is in P".
New!!: Integer factorization and AKS primality test · See more »
Algebraic number theory
Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations.
New!!: Integer factorization and Algebraic number theory · See more »
Algebraic-group factorisation algorithm
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 p1, p2,...
New!!: Integer factorization and Algebraic-group factorisation algorithm · See more »
Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
New!!: Integer factorization and Algorithm · See more »
Big O notation
Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
New!!: Integer factorization and Big O notation · See more »
Binary search algorithm
In computer science, binary search, also known as half-interval search,logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
New!!: Integer factorization and Binary search algorithm · See more »
Bit
The bit (a portmanteau of binary digit) is a basic unit of information used in computing and digital communications.
New!!: Integer factorization and Bit · See more »
BQP
In computational complexity theory, BQP (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.
New!!: Integer factorization and BQP · See more »
Carl Pomerance
Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist.
New!!: Integer factorization and Carl Pomerance · See more »
Co-NP
In computational complexity theory, co-NP is a complexity class.
New!!: Integer factorization and Co-NP · See more »
Co-NP-complete
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead.
New!!: Integer factorization and Co-NP-complete · See more »
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
New!!: Integer factorization and Complexity class · See more »
Composite number
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers.
New!!: Integer factorization and Composite number · See more »
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
New!!: Integer factorization and Computational complexity theory · See more »
Computer science
Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
New!!: Integer factorization and Computer science · See more »
Congruence of squares
In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.
New!!: Integer factorization and Congruence of squares · See more »
Continued fraction factorization
In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm.
New!!: Integer factorization and Continued fraction factorization · See more »
Cryptography
Cryptography or cryptology (from κρυπτός|translit.
New!!: Integer factorization and Cryptography · See more »
David Bressoud
David Marius Bressoud (born March 27, 1950 in Bethlehem, Pennsylvania) is an American mathematician who works in number theory, combinatorics, and special functions.
New!!: Integer factorization and David Bressoud · See more »
Decision problem
In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.
New!!: Integer factorization and Decision problem · See more »
Discriminant
In algebra, the discriminant of a polynomial is a polynomial function of its coefficients, which allows deducing some properties of the roots without computing them.
New!!: Integer factorization and Discriminant · See more »
Dixon's factorization method
In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method.
New!!: Integer factorization and Dixon's factorization method · See more »
Donald Knuth
Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.
New!!: Integer factorization and Donald Knuth · See more »
Elliptic curve
In mathematics, an elliptic curve is a plane algebraic curve defined by an equation of the form which is non-singular; that is, the curve has no cusps or self-intersections.
New!!: Integer factorization and Elliptic curve · See more »
Empty product
In mathematics, an empty product, or nullary product, is the result of multiplying no factors.
New!!: Integer factorization and Empty product · See more »
Euler's factorization method
Euler's factorization method is a technique for factoring a number by writing it as a sum of two squares in two different ways.
New!!: Integer factorization and Euler's factorization method · See more »
Factorization
In mathematics, factorization (also factorisation in some forms of British English) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind.
New!!: Integer factorization and Factorization · See more »
Fermat's factorization method
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: That difference is algebraically factorable as (a+b)(a-b); if neither factor equals one, it is a proper factorization of N. Each odd number has such a representation.
New!!: Integer factorization and Fermat's factorization method · See more »
FNP (complexity)
In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP.
New!!: Integer factorization and FNP (complexity) · See more »
FP (complexity)
In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.
New!!: Integer factorization and FP (complexity) · See more »
Function problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem.
New!!: Integer factorization and Function problem · See more »
Fundamental theorem of arithmetic
In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors.
New!!: Integer factorization and Fundamental theorem of arithmetic · See more »
General number field sieve
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than.
New!!: Integer factorization and General number field sieve · See more »
Generalized Riemann hypothesis
The Riemann hypothesis is one of the most important conjectures in mathematics.
New!!: Integer factorization and Generalized Riemann hypothesis · See more »
Generating set of a group
In abstract algebra, a generating set of a group is a subset such that every element of the group can be expressed as the combination (under the group operation) of finitely many elements of the subset and their inverses.
New!!: Integer factorization and Generating set of a group · See more »
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.
New!!: Integer factorization and Greatest common divisor · See more »
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set of elements equipped with an operation that combines any two elements to form a third element and that satisfies four conditions called the group axioms, namely closure, associativity, identity and invertibility.
New!!: Integer factorization and Group (mathematics) · See more »
Hacker's Delight
Hacker's Delight is a software algorithm book by Henry S. Warren, Jr.
New!!: Integer factorization and Hacker's Delight · See more »
Ideal class group
In number theory, the ideal class group (or class group) of an algebraic number field is the quotient group where is the group of fractional ideals of the ring of integers of, and is its subgroup of principal ideals.
New!!: Integer factorization and Ideal class group · See more »
International Association for Cryptologic Research
The International Association for Cryptologic Research (IACR) is a non-profit scientific organization whose purpose is to further research in cryptology and related fields.
New!!: Integer factorization and International Association for Cryptologic Research · See more »
Kronecker symbol
In number theory, the Kronecker symbol, written as \left(\frac an\right) or (a|n), is a generalization of the Jacobi symbol to all integers n. It was introduced by.
New!!: Integer factorization and Kronecker symbol · See more »
L-notation
L-notation is an asymptotic notation analogous to big-O notation, denoted as L_n for a bound variable n tending to infinity.
New!!: Integer factorization and L-notation · See more »
Lenstra elliptic-curve factorization
The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves.
New!!: Integer factorization and Lenstra elliptic-curve factorization · See more »
Manindra Agrawal
Manindra Agrawal (born 20 May 1966) is a professor at the Department of Computer Science and Engineering and the Deputy Director at the Indian Institute of Technology, Kanpur.
New!!: Integer factorization and Manindra Agrawal · See more »
Mathematics
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
New!!: Integer factorization and Mathematics · See more »
Maurice Kraitchik
Maurice Kraitchik (April 21, 1882 – August 19, 1957) was a Belgian mathematician and populariser.
New!!: Integer factorization and Maurice Kraitchik · See more »
Multiplicative partition
In number theory, a multiplicative partition or unordered factorization of an integer n that is greater than 1 is a way of writing n as a product of integers greater than 1, treating two products as equivalent if they differ only in the ordering of the factors.
New!!: Integer factorization and Multiplicative partition · See more »
Nature (journal)
Nature is a British multidisciplinary scientific journal, first published on 4 November 1869.
New!!: Integer factorization and Nature (journal) · See more »
NP (complexity)
In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.
New!!: Integer factorization and NP (complexity) · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: Integer factorization and NP-completeness · See more »
NP-intermediate
In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI.
New!!: Integer factorization and NP-intermediate · See more »
Number theory
Number theory, or in older usage arithmetic, is a branch of pure mathematics devoted primarily to the study of the integers.
New!!: Integer factorization and Number theory · See more »
Opteron
Opteron is AMD's x86 former server and workstation processor line, and was the first processor which supported the AMD64 instruction set architecture (known generically as x86-64).
New!!: Integer factorization and Opteron · See more »
Partition (number theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers.
New!!: Integer factorization and Partition (number theory) · See more »
Pearson Education
Pearson Education (see also Pearson PLC) is a British-owned education publishing and assessment service to schools and corporations, as well as directly to students.
New!!: Integer factorization and Pearson Education · See more »
Peter Shor
Peter Williston Shor (born August 14, 1959) is an American professor of applied mathematics at MIT.
New!!: Integer factorization and Peter Shor · See more »
Pollard's p − 1 algorithm
Pollard's p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974.
New!!: Integer factorization and Pollard's p − 1 algorithm · See more »
Pollard's rho algorithm
Pollard's rho algorithm is an algorithm for integer factorization.
New!!: Integer factorization and Pollard's rho algorithm · See more »
Primality test
A primality test is an algorithm for determining whether an input number is prime.
New!!: Integer factorization and Primality test · See more »
Prime number
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
New!!: Integer factorization and Prime number · See more »
Public-key cryptography
Public-key cryptography, or asymmetric cryptography, is any cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner.
New!!: Integer factorization and Public-key cryptography · See more »
Quadratic form
In mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables.
New!!: Integer factorization and Quadratic form · See more »
Quadratic sieve
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve).
New!!: Integer factorization and Quadratic sieve · See more »
Quantum computing
Quantum computing is computing using quantum-mechanical phenomena, such as superposition and entanglement.
New!!: Integer factorization and Quantum computing · See more »
Randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.
New!!: Integer factorization and Randomized algorithm · See more »
Rational sieve
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors.
New!!: Integer factorization and Rational sieve · See more »
Richard Crandall
Richard E. Crandall (December 29, 1947 – December 20, 2012) was an American physicist and computer scientist who made contributions to computational number theory.
New!!: Integer factorization and Richard Crandall · See more »
RSA (cryptosystem)
RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission.
New!!: Integer factorization and RSA (cryptosystem) · See more »
RSA numbers
In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that are part of the RSA Factoring Challenge.
New!!: Integer factorization and RSA numbers · See more »
RSA problem
In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key.
New!!: Integer factorization and RSA problem · See more »
Semiprime
In mathematics, a semiprime is a natural number that is the product of two prime numbers.
New!!: Integer factorization and Semiprime · See more »
Shanks's square forms factorization
Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method.
New!!: Integer factorization and Shanks's square forms factorization · See more »
Shor's algorithm
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994.
New!!: Integer factorization and Shor's algorithm · See more »
Smooth number
In number theory, a smooth (or friable) number is an integer which factors completely into small prime numbers.
New!!: Integer factorization and Smooth number · See more »
Special number field sieve
In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm.
New!!: Integer factorization and Special number field sieve · See more »
Stan Wagon
Stanley Wagon is a Canadian-American mathematician, a professor of mathematics at Macalester College in Minnesota.
New!!: Integer factorization and Stan Wagon · See more »
Sylow theorems
In mathematics, specifically in the field of finite group theory, the Sylow theorems are a collection of theorems named after the Norwegian mathematician Ludwig Sylow (1872) that give detailed information about the number of subgroups of fixed order that a given finite group contains.
New!!: Integer factorization and Sylow theorems · See more »
The Art of Computer Programming
The Art of Computer Programming (sometimes known by its initials TAOCP) is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis.
New!!: Integer factorization and The Art of Computer Programming · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: Integer factorization and Time complexity · See more »
Trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms.
New!!: Integer factorization and Trial division · See more »
UP (complexity)
In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input.
New!!: Integer factorization and UP (complexity) · See more »
Wheel factorization
Wheel factorization is a method for generating lists of mostly prime numbers from a simple mathematical formula and a much smaller list of the first prime numbers.
New!!: Integer factorization and Wheel factorization · See more »
Williams's 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.
New!!: Integer factorization and Williams's p + 1 algorithm · See more »
Redirects here:
Algorithms for factoring integers, Factor table, Factor tree, Factoring integers, Factoring problem, Factoring tree, Integer Factorization, Integer factoring, Integer factorisation, Integer factorization algorithms, Integer factorization problem, Integer factors, Prime Factorization, Prime decomposition, Prime factorisation, Prime factorization, Prime factorization algorithm, Prime factorization algorithms.
References
[1] https://en.wikipedia.org/wiki/Integer_factorization
