Diophantine approximation

Diophantine approximation refers to the process of approximating a vector of rational or real numbers with a smaller denominator or rational number that is close to the given vector. It can be simultaneous, where multiple vectors are approximated at once, or singular, where a single number is approximated.From: Handbook of Applied Cryptography [2018], A class of optimization problems motivated by rank estimators in robust regression [2022]

Number-Theoretic Reference Problems

View Chapter

Purchase Book

Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone

Simultaneous diophantine approximation is concerned with approximating a vector (q1q,q2q,⋯,qnq) of rational numbers (more generally, a vector (α1, α2, …, αn) of real numbers) by a vector (p1p,p2p,⋯,pnp) of rational numbers with a smaller denominator p. Algorithms for finding simultaneous diophantine approximation have been used to break some knapsack public-key encryption schemes (§8.6).

Non-rigid rank-one infinite measures on the circle

View Article

Journal Information

Published in Dynamical Systems, 2023

Hindy Drillick, Alonso Espinosa-Dominguez, Jennifer N. Jones-Baro, James Leng, Yelena Mandelshtam, Cesar E. Silva

As is well known, every irrational number α can be uniquely described as a continued fraction where the are called the coefficients of the continued fraction. The rational numbers are called the convergents for α. The sequence of convergents provides a best Diophantine approximation of α by rational numbers. We can express the convergents in terms of the coefficients by the following recursive formulas, for ,

A class of optimization problems motivated by rank estimators in robust regression

View Article

Journal Information

Published in Optimization, 2022

Michal Černý, Miroslav Rada, Jaromír Antoch, Milan Hladík

Sometimes, property (a) will not be necessary; then, we will use the notation We will also need the following form of Diophantine approximation. Recall that the Diophantine approximation is a method for finding a rational number with a small denominator close to a given rational number.

Diophantine approximation

Explore chapters and articles related to this topic

Number-Theoretic Reference Problems

Non-rigid rank-one infinite measures on the circle

A class of optimization problems motivated by rank estimators in robust regression