Publication

Function Field Sieve in Characteristic Three

Related concepts (23)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties.

Finite field

In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod p when p is a prime number. The order of a finite field is its number of elements, which is either a prime number or a prime power.

Sieve theory

Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms.

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. Elliptic curves are applicable for key agreement, digital signatures, pseudo-random generators and other tasks. Indirectly, they can be used for encryption by combining the key agreement with a symmetric encryption scheme.

Algebraic function field

In mathematics, an algebraic function field (often abbreviated as function field) of n variables over a field k is a finitely generated field extension K/k which has transcendence degree n over k. Equivalently, an algebraic function field of n variables over k may be defined as a finite field extension of the field K = k(x1,...,xn) of rational functions in n variables over k. As an example, in the polynomial ring k [X,Y] consider the ideal generated by the irreducible polynomial Y 2 − X 3 and form the field of fractions of the quotient ring k [X,Y]/(Y 2 − X 3).

Function field of an algebraic variety

In algebraic geometry, the function field of an algebraic variety V consists of objects which are interpreted as rational functions on V. In classical algebraic geometry they are ratios of polynomials; in complex algebraic geometry these are meromorphic functions and their higher-dimensional analogues; in modern algebraic geometry they are elements of some quotient ring's field of fractions. In complex algebraic geometry the objects of study are complex analytic varieties, on which we have a local notion of complex analysis, through which we may define meromorphic functions.

Riemann zeta function

The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter ζ (zeta), is a mathematical function of a complex variable defined as for , and its analytic continuation elsewhere. The Riemann zeta function plays a pivotal role in analytic number theory, and has applications in physics, probability theory, and applied statistics. Leonhard Euler first introduced and studied the function over the reals in the first half of the eighteenth century.

L-notation

L-notation is an asymptotic notation analogous to big-O notation, denoted as for a bound variable tending to infinity. Like big-O notation, it is usually used to roughly convey the rate of growth of a function, such as the computational complexity of a particular algorithm. It is defined as where c is a positive constant, and is a constant . L-notation is used mostly in computational number theory, to express the complexity of algorithms for difficult number theory problems, e.g.

Discrete logarithm

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 = indr a (mod m) (read "the index of a to the base r modulo m") for rx ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1. Discrete logarithms are quickly computable in a few special cases.

Finite ring

In mathematics, more specifically abstract algebra, a finite ring is a ring that has a finite number of elements. Every finite field is an example of a finite ring, and the additive part of every finite ring is an example of an abelian finite group, but the concept of finite rings in their own right has a more recent history. Although rings have more structure than groups, the theory of finite rings is simpler than that of finite groups.