Related Research Articles
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
In number theory, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.
A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior using specialized hardware. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer. In particular, a large-scale quantum computer could break widely used encryption schemes and aid physicists in performing physical simulations; however, the current state of the art is largely experimental and impractical, with several obstacles to useful applications.
Magma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma. It runs on Unix-like operating systems, as well as Windows.
In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indra (mod m) (read "the index of a to the base r modulo m") for r x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.
Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.
In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm; that is, whether the problem lies in the complexity class P.
Hendrik Willem Lenstra Jr. is a Dutch mathematician.
The following tables list the computational complexity of various algorithms for common mathematical operations.
In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where the variables are interpreted as having real number values, and where is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula , make it become true.
Jennifer Shyamala Sayaka Balakrishnan is an American mathematician known for leading a team that solved the problem of the "cursed curve", a Diophantine equation that was known for being "famously difficult". More generally, Balakrishnan specializes in algorithmic number theory and arithmetic geometry. She is a Clare Boothe Luce Professor at Boston University.
In mathematics, the supersingular isogeny graphs are a class of expander graphs that arise in computational number theory and have been applied in elliptic-curve cryptography. Their vertices represent supersingular elliptic curves over finite fields and their edges represent isogenies between curves.
Andrew Victor Sutherland is an American mathematician and Principal Research Scientist at the Massachusetts Institute of Technology. His research focuses on computational aspects of number theory and arithmetic geometry. He is known for his contributions to several projects involving large scale computations, including the Polymath project on bounded gaps between primes, the L-functions and Modular Forms Database, the sums of three cubes project, and the computation and classification of Sato-Tate distributions.
In mathematics, a sparse polynomial is a polynomial that has far fewer terms than its degree and number of variables would suggest. For example, x10 + 3x3 − 1 is a sparse polynomial as it is a trinomial with a degree of 10.
Shmuel Onn is a mathematician, Professor of Operations Research and Dresner Chair at the Technion - Israel Institute of Technology. He is known for his contributions to integer programming and nonlinear combinatorial optimization.
References
- ↑ "Algorithmic Number Theory Symposium" . Retrieved 14 March 2020.
- ↑ Warner Bley; Robert Boltie (2006). "Computation of Locally Free Class Groups". Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 4076. pp. 72–86. doi:10.1007/11792086_6. ISBN 978-3-540-36075-9.
- ↑ Juliana Belding; Reinier Bröker; Andreas Enge; Kristin Lauter (2008). "Computing Hilbert Class Polynomials". Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 5011. pp. 282–295. arXiv: 0802.0979 . doi:10.1007/978-3-540-79456-1_19. ISBN 978-3-540-79455-4. S2CID 11047044.
- ↑ John Voight (2010). "Computing Automorphic Forms on Shimura Curves over Fields with Arbitrary Class Number". Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 6197. pp. 357–37'. arXiv: 1004.5340 . doi:10.1007/978-3-642-14518-6_28. ISBN 978-3-642-14517-9. S2CID 15424318.
- ↑ Andrew Sutherland (2012). "On the evaluation of modular polynomials". The Open Book Series. 1: 531–555. arXiv: 1202.3985 . Bibcode:2012arXiv1202.3985S. doi:10.2140/obs.2013.1.531. S2CID 1367368.
- ↑ Tom Fisher, Fisher, Tom (2014). "Minimal models of 6-coverings of elliptic curves". LMS Journal of Computation and Mathematics. 17: 112–127. doi: 10.1112/S1461157014000217 .
- ↑ Jan Steffen Müller; Michael Stoll (2016). "Computing Canonical Heights on Elliptic Curves in Quasi-Linear Time". LMS Journal of Computation and Mathematics. 19: 391–405. arXiv: 1509.08748 . doi:10.1112/S1461157016000139. S2CID 50736998.
- ↑ Michael Musty; Sam Schiavone; Jeroen Sijsling; John Voight (2019). "A database of Belyi maps". The Open Book Series. 2: 375–392. arXiv: 1805.07751 . doi:10.2140/obs.2019.2.375. S2CID 119152099.
- ↑ Jonathan Love; Dan Boneh (2020). "Supersingular curves with small non-integer endomorphisms". The Open Book Series. 4: 7–22. arXiv: 1910.03180 . doi:10.2140/obs.2020.4.7. S2CID 203905885.
- ↑ Harald Helfgott; Lola Thompson (2023). "Summing mu(n): a faster elementary algorithm". Research in Number Theory. 9 (6). arXiv: 2101.08773 . doi:10.1007/s40993-022-00408-8.
- ↑ Erik Mulder (2024). "Fast square-free decomposition of integers using class groups" (PDF). to appear in Research in Number Theory. arXiv: 2308.06130 .
- ↑ "Call for Papers". ANTS XV. University of Bristol . Retrieved 10 August 2022.
- ↑ "Call for Papers". ANTS XVI. Massachusetts Institute of Technology . Retrieved 19 July 2024.
