Lecture

Windowing Exponentiation

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 covers the concept of windowing exponentiation using base-B representation, where the small powers of x are precomputed and stored efficiently. The instructor explains the binary ladders LR and RL, and how to compute y using base-B representation. The lecture emphasizes the importance of precomputing small powers of x and demonstrates the process with various examples. It also discusses the benefits of windowing exponentiation and its application in efficiently computing exponentiation. The lecture concludes with a detailed explanation of the Montgomery ladder and its role in optimizing exponentiation calculations.

Instructor

Dimitar Petkov Jetchev

Official source

Related concepts (32)

Exponentiation by squaring

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

Windowing system

In computing, a windowing system (or window system) is a software suite that manages separately different parts of display screens. It is a type of graphical user interface (GUI) which implements the WIMP (windows, icons, menus, pointer) paradigm for a user interface. Each currently running application is assigned a usually resizable and usually rectangular surface of the display to present its GUI to the user; these windows may overlap each other, as opposed to a tiling interface where they are not allowed to overlap.

Great power

A great power is a sovereign state that is recognized as having the ability and expertise to exert its influence on a global scale. Great powers characteristically possess military and economic strength, as well as diplomatic and soft power influence, which may cause middle or small powers to consider the great powers' opinions before taking actions of their own. International relations theorists have posited that great power status can be characterized into power capabilities, spatial aspects, and status dimensions.

Modular exponentiation

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys. Modular exponentiation is the remainder when an integer b (the base) is raised to the power e (the exponent), and divided by a positive integer m (the modulus); that is, c = be mod m. From the definition of division, it follows that 0 ≤ c < m.

Middle power

In international relations, a middle power is a sovereign state that is not a great power nor a superpower, but still has large or moderate influence and international recognition. The concept of the "middle power" dates back to the origins of the European state system. In the late 16th century, Italian political thinker Giovanni Botero divided the world into three types of states: grandissime (empires), mezano (middle powers), and piccioli (small powers).

Related lectures (39)

Stability of Feigenbaum Fixed Point

Explores the stability of the Feigenbaum fixed point with infinite criticality and its applications in chaos theory.

Quantum Random Number Generation

Explores quantum random number generation, discussing the challenges and implementations of generating good randomness using quantum devices.

Dependability Overview

Explores dependability in industrial automation, covering reliability, safety, fault characteristics, and examples of failure sources in various industries.

Snowpack Modeling: Physics and Applications

Explores the physics of snowpack modeling and its practical applications in vapor transport and hydrology simulations.

Wave Equations: Vibrating String