Related Research Articles
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography to provide equivalent security.
A quantum computer is a computer that exploits quantum mechanical phenomena. At small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior, specifically quantum superposition and entanglement, using specialized hardware that supports the preparation and manipulation of quantum states. 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.
Hypercomputation or super-Turing computation is a set of models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that can correctly evaluate every statement in Peano arithmetic.
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.
In quantum computing, a quantum algorithm is an algorithm which 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 usually used for those algorithms which 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 graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
John K. S. McKay was a British-Canadian mathematician and academic who worked at Concordia University, known for his discovery of monstrous moonshine, his joint construction of some sporadic simple groups, for the McKay conjecture in representation theory, and for the McKay correspondence relating certain finite groups to Lie groups.
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.
The following tables list the computational complexity of various algorithms for common mathematical operations.
In algebraic geometry, a supersingular K3 surface is a K3 surface over a field k of characteristic p > 0 such that the slopes of Frobenius on the crystalline cohomology H2(X,W(k)) are all equal to 1. These have also been called Artin supersingular K3 surfaces. Supersingular K3 surfaces can be considered the most special and interesting of all K3 surfaces.
In cryptography, post-quantum cryptography (PQC) refers to cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.
Harald Andrés Helfgott is a Peruvian mathematician working in number theory. Helfgott is a researcher at the CNRS at the Institut Mathématique de Jussieu, Paris.
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
Supersingular isogeny Diffie–Hellman key exchange is an insecure proposal for a post-quantum cryptographic algorithm to establish a secret key between two parties over an untrusted communications channel. It is analogous to the Diffie–Hellman key exchange, but is based on walks in a supersingular isogeny graph and was designed to resist cryptanalytic attack by an adversary in possession of a quantum computer. Before it was broken, SIDH boasted one of the smallest key sizes of all post-quantum key exchanges; with compression, SIDH used 2688-bit public keys at a 128-bit quantum security level. SIDH also distinguishes itself from similar systems such as NTRU and Ring-LWE by supporting perfect forward secrecy, a property that prevents compromised long-term keys from compromising the confidentiality of old communication sessions. These properties seemed to make SIDH a natural candidate to replace Diffie–Hellman (DHE) and elliptic curve Diffie–Hellman (ECDHE), which are widely used in Internet communication. However, SIDH is vulnerable to a devastating key-recovery attack published in July 2022 and is therefore insecure. The attack does not require a quantum computer.
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 the Clare Boothe Luce Associate 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.
James Milton Renegar Jr. is an American mathematician, specializing in optimization algorithms for linear programming and nonlinear programming.
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 (2022). "Summing mu(n): a faster elementary algorithm" (PDF). arXiv: 2101.08773 .
{{cite journal}}: Cite journal requires|journal=(help) - ↑ "Call for Papers". ANTS XV. University of Bristol . Retrieved 10 August 2022.
