Lecture

Legendre and Jacobi Symbols: RSA Cryptography

Graph Chat

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.

In course

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how they work and sketch how they can be implemented. ...

Description

This lecture covers Legendre and Jacobi symbols, explaining their computation and application to quadratic residuosity. It also delves into computing element orders in Z, and the process of factoring in RSA Cryptography, highlighting the complexity and strategies involved.

Instructor

Serge Vaudenay

Serge Vaudenay entered at the Ecole Normale Supérieure in 1989 with a major in mathematics. He earned his agrégation (secondary teaching degree) in mathematics in 1992, then a PhD in Computer Science at the University of Paris 7 - Denis Diderot in 1995. He subsequently became a senior research fellow at the CNRS, prior to being granted his habilitation à diriger des recherches (a postdoctoral degree authorizing the recipient to supervise doctoral students). In 1999, he was appointed as a Professor at the EPFL, where he created the Security and Cryptography Laboratory.

Official source

Ontological neighbourhood

Mathematics

Number theory: Topics in number theory

Related concepts (32)

Legendre symbol

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0. The Legendre symbol was introduced by Adrien-Marie Legendre in 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol and Dirichlet characters of higher order.

Jacobi symbol

Jacobi symbol k/n for various k (along top) and n (along left side). Only 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if k is a quadratic residue modulo a coprime n, then k/n = 1, but not all entries with a Jacobi symbol of 1 (see the n = 9 and n = 15 rows) are quadratic residues. Notice also that when either n or k is a square, all values are nonnegative.

Kronecker symbol

In number theory, the Kronecker symbol, written as or , is a generalization of the Jacobi symbol to all integers . It was introduced by . Let be a non-zero integer, with prime factorization where is a unit (i.e., ), and the are primes. Let be an integer. The Kronecker symbol is defined by For odd , the number is simply the usual Legendre symbol. This leaves the case when . We define by Since it extends the Jacobi symbol, the quantity is simply when .

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4.

Group homomorphism

In mathematics, given two groups, (G, ∗) and (H, ·), a group homomorphism from (G, ∗) to (H, ·) is a function h : G → H such that for all u and v in G it holds that where the group operation on the left side of the equation is that of G and on the right side that of H. From this property, one can deduce that h maps the identity element eG of G to the identity element eH of H, and it also maps inverses to inverses in the sense that Hence one can say that h "is compatible with the group structure".

Related lectures (64)

Prime Numbers and Primality Testing

Covers prime numbers, RSA cryptography, and primality testing, including the Chinese Remainder Theorem and the Miller-Rabin test.

RSA Cryptography: Primality Testing and Quadratic Residues

Explores RSA cryptography, covering primality testing, quadratic residues, and cryptographic applications.

Elementary Algebra: Numeric Sets

Explores elementary algebra concepts related to numeric sets and prime numbers, including unique factorization and properties.

Cryptography and Information Theory

Explores cryptography, perfect secrecy, group theory, and modern cryptographic milestones, emphasizing the trade-off between security and cost.

Primes in Arithmetic Progression