Lecture

Integer Factorization: Quadratic Sieve

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

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture delves into the analysis of integer factorization using the quadratic sieve method, discussing the factor base, polynomial degree manipulation, and the challenges of working with algebraic number fields. The instructor explains the importance of finding generators in groups and presents various algorithms, including the index calculus method and its limitations in elliptic curves. The lecture concludes with a focus on the discrete logarithm problem in cryptography, highlighting its relevance in key exchange protocols and signature schemes. The instructor also touches upon the birthday paradox and its application in finding collisions in cryptographic functions.

Instructor

Dimitar Petkov Jetchev

Official source

Related concepts (32)

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.

Factorization

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x2 – 4. Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any can be trivially written as whenever is not zero.

Algebraic number field

In mathematics, an algebraic number field (or simply number field) is an extension field of the field of rational numbers such that the field extension has finite degree (and hence is an algebraic field extension). Thus is a field that contains and has finite dimension when considered as a vector space over . The study of algebraic number fields, and, more generally, of algebraic extensions of the field of rational numbers, is the central topic of algebraic number theory.

Cryptography

Cryptography, or cryptology (from κρυπτός "hidden, secret"; and γράφειν graphein, "to write", or -λογία -logia, "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others.

Key exchange

Key exchange (also key establishment) is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm. If the sender and receiver wish to exchange encrypted messages, each must be equipped to encrypt messages to be sent and decrypt messages received. The nature of the equipping they require depends on the encryption technique they might use. If they use a code, both will require a copy of the same codebook. If they use a cipher, they will need appropriate keys.

Related lectures (64)

Integer Factorization: Quadratic Sieve

Covers the Quadratic Sieve method for integer factorization, emphasizing the importance of choosing the right parameters for efficient factorization.

Galois Fields and Elliptic Curves

Introduces Galois fields, elliptic curves, factorization algorithms, and the discrete logarithm problem in cryptography.

Elliptic Curves and Lattices

Explores Elliptic Curve Discrete Logarithm Problem, lattice-based cryptography, and cryptographic schemes like ECDSA.

Diffie-Hellman Cryptography: Key Exchange and ElGamal Encryption

Covers the Diffie-Hellman key exchange protocol and the ElGamal public-key cryptosystem.

Public-Key Cryptography: Key Exchange and Signatures