|
Schoof's Algorithm
Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve. The algorithm was published by René Schoof in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm for counting points on elliptic curves. Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive and baby-step giant-step algorithms were, for the most part, tedious and had an exponential running time. This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm. Introduction Let E be an elliptic curve defined over the finite field \mathbb_, where q=p^n for p a prime and n an integer \geq 1. Over a field of charact ... [...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 cubic cu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Imaginary Hyperelliptic Curve
A hyperelliptic curve is a particular kind of algebraic curve. There exist hyperelliptic curves of every genus g \geq 1. If the genus of a hyperelliptic curve equals 1, we simply call the curve an elliptic curve. Hence we can see hyperelliptic curves as generalizations of elliptic curves. There is a well-known group structure on the set of points lying on an elliptic curve over some field K, which we can describe geometrically with chords and tangents. Generalizing this group structure to the hyperelliptic case is not straightforward. We cannot define the same group law on the set of points lying on a hyperelliptic curve, instead a group structure can be defined on the so-called Jacobian of a hyperelliptic curve. The computations differ depending on the number of points at infinity. Imaginary hyperelliptic curves are hyperelliptic curves with exactly 1 point at infinity: real hyperelliptic curves have two points at infinity. Formal definition Hyperelliptic curves can be define ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Elliptic Curve Cryptography
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 (based on plain Galois fields) to provide equivalent security.Commercial National Security Algorithm Suite and Quantum Computing FAQ U.S. National Security Agency, January 2016. Elliptic curves are applicable for , s, [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
AGPLv3
The GNU Affero General Public License (GNU AGPL) is a free, copyleft license published by the Free Software Foundation in November 2007, and based on the GNU General Public License, version 3 and the Affero General Public License. The Free Software Foundation has recommended that the GNU AGPLv3 be considered for any software that will commonly be run over a network.List of free-software licences on the FSF website "''We recommend that developers consider using the GNU AGPL for any software which will commonly be run over a network.''" The Free Software Foundation explains the need for the license in the case when a free program is run on a server: The GNU Affero General Public License is a modified version of the ordinary GNU GPL version 3. It has one added requirement: if yo ... |
Generalized Riemann Hypothesis
The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, which are formally similar to the Riemann zeta-function. One can then ask the same question about the zeros of these ''L''-functions, yielding various generalizations of the Riemann hypothesis. Many mathematicians believe these generalizations of the Riemann hypothesis to be true. The only cases of these conjectures which have been proven occur in the algebraic function field case (not the number field case). Global ''L''-functions can be associated to elliptic curves, number fields (in which case they are called Dedekind zeta-functions), Maass forms, and Dirichlet characters (in which case they are called Dirichlet L-functions). When the Riemann hypothesis is formulated for Dedekind zeta-functions, it is known as the extended Riemann hypothes ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Las Vegas Algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the ''expected'' runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex. Las Vegas algorithms are prominent in the field of artificial intelligence, and in other ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modular Forms
In mathematics, a modular form is a (complex) analytic function on the upper half-plane satisfying a certain kind of functional equation with respect to the group action of the modular group, and also satisfying a growth condition. The theory of modular forms therefore belongs to complex analysis but the main importance of the theory has traditionally been in its connections with number theory. Modular forms appear in other areas, such as algebraic topology, sphere packing, and string theory. A modular function is a function that is invariant with respect to the modular group, but without the condition that be holomorphic in the upper half-plane (among other requirements). Instead, modular functions are meromorphic (that is, they are holomorphic on the complement of a set of isolated points, which are poles of the function). Modular form theory is a special case of the more general theory of automorphic forms which are functions defined on Lie groups which transform nicely wit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schoof–Elkies–Atkin Algorithm
The Schoof–Elkies–Atkin algorithm (SEA) is an algorithm used for finding the order of or calculating the number of points on an elliptic curve over a finite field. Its primary application is in elliptic curve cryptography. The algorithm is an extension of Schoof's algorithm by Noam Elkies and A. O. L. Atkin to significantly improve its efficiency (under heuristic assumptions). Details The Elkies-Atkin extension to Schoof's algorithm works by restricting the set of primes S = \ considered to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime l is called an Elkies prime if the characteristic equation: \phi^2-t\phi+ q = 0 splits over \mathbb_l, while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the Schoof–Elkies–Atkin algorithm. The first ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Noam Elkies
Noam David Elkies (born August 25, 1966) is a professor of mathematics at Harvard University. At the age of 26, he became the youngest professor to receive tenure at Harvard. He is also a pianist, chess national master and a chess composer. Early life Elkies was born to an engineer father and a piano teacher mother. He attended Stuyvesant High School in New York City for three years before graduating in 1982 at age 15. A child prodigy in 1981, at age 14, he was awarded a gold medal at the 22nd International Mathematical Olympiad, receiving a perfect score of 42, one of the youngest to ever do so. He went on to Columbia University, where he won the Putnam competition at the age of sixteen years and four months, making him one of the youngest Putnam Fellows in history. He was a Putnam Fellow two more times during his undergraduate years. He graduated valedictorian of his class in 1985. He then earned his PhD in 1987 under the supervision of Benedict Gross and Barry Mazur at Harva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prime Number Theorem
In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann (in particular, the Riemann zeta function). The first such distribution found is , where is the prime-counting function (the number of primes less than or equal to ''N'') and is the natural logarithm of . This means that for large enough , the probability that a random integer not greater than is prime is very close to . Consequently, a random integer with at most digits (for large enough ) is about half as likely to be prime as a random integer with at most digits. For example, among the positive integers of at most 1000 digits, about one in 2300 is prime ... [...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 lar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Elliptic Curves
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 cubic curve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
