𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the BKW algorithm on LWE

✍ Scribed by Albrecht, Martin R.; Cid, Carlos; Faugère, Jean-Charles; Fitzpatrick, Robert; Perret, Ludovic

Book ID
120966738
Publisher
Springer
Year
2013
Tongue
English
Weight
394 KB
Volume
74
Category
Article
ISSN
0925-1022

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

BKW-Operators on the Interval and the Se
BKW-Operators on the Interval and the Sequence Spaces
✍ Keiji Izuchi; Sin-Ei Takahasi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 354 KB

Let 1 be the closed unit interval or 1=[1Ân; n=1, 2, ..., ]. We give a complete characterization of BKW-operators on C(1) for the test functions [1, t, t 2 ]. 1996 Academic Press, Inc. \* &T \* f&Tf& =0 for f # S, it follows that [T \* ] \* converges strongly to T on X. We denote by BKW(X, Y; S ) th

Tight bounds on the complexity of the Ap
Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
✍ Maxime Crochemore; Thierry Lecroq 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 678 KB

The Apostolico-Giancarlo string-matching algorithm is analyzed precisely. We give a tight upper bound of $n text character comparisons when searching for a pattern in a text of length n. We exhibit a family of patterns and texts reaching this bound. We also provide a slightly improved version of the

On the complexity of the extended euclid
On the complexity of the extended euclidean algorithm (Extended Abstract)
✍ George Havas 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 92 KB

Euclid's algorithm for computing the greatest common divisor of 2 numbers is considered to be the oldest proper algorithm known ([10]). This algorithm can be amplified naturally in various ways. The GCD problem for more than two numbers is interesting in its own right. Thus, we can use Euclid's algo