Computational Cryptography: Algorithmic Aspects of Cryptology 1st Edition Joppe Bos

Computational Cryptography: Algorithmic Aspects of Cryptology 1st Edition Joppe Bos
Computational Cryptography: Algorithmic Aspects of Cryptology 1st Edition Joppe Bos
Computational Cryptography: Algorithmic Aspects of Cryptology 1st Edition Joppe Bos

1. Read Anytime Anywhere Easy Ebook Downloads at ebookmeta.com
Computational Cryptography: Algorithmic Aspects of
Cryptology 1st Edition Joppe Bos
https://ebookmeta.com/product/computational-cryptography-
algorithmic-aspects-of-cryptology-1st-edition-joppe-bos/
OR CLICK HERE
DOWLOAD EBOOK
Visit and Get More Ebook Downloads Instantly at https://ebookmeta.com

2. Recommended digital products (PDF, EPUB, MOBI) that
you can download immediately if you are interested.
Fundamentals of Cryptography: Introducing Mathematical and
Algorithmic Foundations (Undergraduate Topics in Computer
Science) Duncan Buell
https://ebookmeta.com/product/fundamentals-of-cryptography-
introducing-mathematical-and-algorithmic-foundations-undergraduate-
topics-in-computer-science-duncan-buell/
ebookmeta.com
Primary Mathematics 3A Hoerst
https://ebookmeta.com/product/primary-mathematics-3a-hoerst/
ebookmeta.com
Practical Aspects of Computational Chemistry V Jerzy
Leszczynski Manoj K. Shukla
https://ebookmeta.com/product/practical-aspects-of-computational-
chemistry-v-jerzy-leszczynski-manoj-k-shukla/
ebookmeta.com
Vicious Vows The Mafia Wives 2 1st Edition Ivy Davis
https://ebookmeta.com/product/vicious-vows-the-mafia-wives-2-1st-
edition-ivy-davis/
ebookmeta.com

3. Understanding Logic The First Order of Reasoning 2nd
Edition Guy Davies Love Ekenberg Johan Thorbiörnson
https://ebookmeta.com/product/understanding-logic-the-first-order-of-
reasoning-2nd-edition-guy-davies-love-ekenberg-johan-thorbiornson/
ebookmeta.com
The Opioid Epidemic: What Everyone Needs to Know 1st
Edition Yngvild Olsen
https://ebookmeta.com/product/the-opioid-epidemic-what-everyone-needs-
to-know-1st-edition-yngvild-olsen/
ebookmeta.com
Veterans Faces of World War II Sasha Maslov
https://ebookmeta.com/product/veterans-faces-of-world-war-ii-sasha-
maslov/
ebookmeta.com
The Crossing The Chronicles Of Micki O Sullivan 1 1st
Edition Jo Wilde
https://ebookmeta.com/product/the-crossing-the-chronicles-of-micki-o-
sullivan-1-1st-edition-jo-wilde/
ebookmeta.com
Learning GIS Using Open Source Software An Applied Guide
for Geo spatial Analysis 1st Edition Kakoli Saha & Yngve
K. Frøyen
https://ebookmeta.com/product/learning-gis-using-open-source-software-
an-applied-guide-for-geo-spatial-analysis-1st-edition-kakoli-saha-
yngve-k-froyen/
ebookmeta.com

4. Biochemistry 8th ed Lippincott Illustrated Reviews 8th
Edition Emine Ercikan Abali Susan D Cline David S Franklin
Susan M Viselli
https://ebookmeta.com/product/biochemistry-8th-ed-lippincott-
illustrated-reviews-8th-edition-emine-ercikan-abali-susan-d-cline-
david-s-franklin-susan-m-viselli/
ebookmeta.com

7. LONDON MATHEMATICAL SOCIETY LECTURE NOTE SERIES
Managing Editor: Professor Endre S¨uli, Mathematical Institute, University of Oxford,
Woodstock Road, Oxford OX2 6GG, United Kingdom
The titles below are available from booksellers, or from Cambridge University Press at
www.cambridge.org/mathematics
359 Moduli spaces and vector bundles, L. BRAMBILA-PAZ, S.B. BRADLOW, O. GARC´IA-PRADA &
S. RAMANAN (eds)
360 Zariski geometries, B. ZILBER
361 Words: Notes on verbal width in groups, D. SEGAL
362 Differential tensor algebras and their module categories, R. BAUTISTA, L. SALMER´ON & R. ZUAZUA
363 Foundations of computational mathematics, Hong Kong 2008, F. CUCKER, A. PINKUS & M.J. TODD (eds)
364 Partial differential equations and fluid mechanics, J.C. ROBINSON & J.L. RODRIGO (eds)
365 Surveys in combinatorics 2009, S. HUCZYNSKA, J.D. MITCHELL & C.M. RONEY-DOUGAL (eds)
366 Highly oscillatory problems, B. ENGQUIST, A. FOKAS, E. HAIRER & A. ISERLES (eds)
367 Random matrices: High dimensional phenomena, G. BLOWER
368 Geometry of Riemann surfaces, F.P. GARDINER, G. GONZ´ALEZ-DIEZ & C. KOUROUNIOTIS (eds)
369 Epidemics and rumours in complex networks, M. DRAIEF & L. MASSOULI´E
370 Theory ofp-adic distributions, S. ALBEVERIO, A.YU. KHRENNIKOV & V.M. SHELKOVICH
371 Conformal fractals, F. PRZYTYCKI & M. URBA´NSKI
372 Moonshine: The first quarter century and beyond, J. LEPOWSKY, J. MCKAY & M.P. TUITE (eds)
373 Smoothness, regularity and complete intersection, J. MAJADAS & A. G. RODICIO
374 Geometric analysis of hyperbolic differential equations: An introduction, S. ALINHAC
375 Triangulated categories, T. HOLM, P. JØRGENSEN & R. ROUQUIER (eds)
376 Permutation patterns, S. LINTON, N. RUˇSKUC & V. VATTER (eds)
377 An introduction to Galois cohomology and its applications, G. BERHUY
378 Probability and mathematical genetics, N. H. BINGHAM & C. M. GOLDIE (eds)
379 Finite and algorithmic model theory, J. ESPARZA, C. MICHAUX & C. STEINHORN (eds)
380 Real and complex singularities, M. MANOEL, M.C. ROMERO FUSTER & C.T.C WALL (eds)
381 Symmetries and integrability of difference equations, D. LEVI, P. OLVER, Z. THOMOVA &
P. WINTERNITZ (eds)
382 Forcing with random variables and proof complexity, J. KRAJ´IˇCEK
383 Motivic integration and its interactions with model theory and non-Archimedean geometry I, R. CLUCKERS,
J. NICAISE & J. SEBAG (eds)
384 Motivic integration and its interactions with model theory and non-Archimedean geometry II, R. CLUCKERS,
J. NICAISE & J. SEBAG (eds)
385 Entropy of hidden Markov processes and connections to dynamical systems, B. MARCUS, K. PETERSEN &
T. WEISSMAN (eds)
386 Independence-friendly logic, A.L. MANN, G. SANDU & M. SEVENSTER
387 Groups St Andrews 2009 in Bath I, C.M. CAMPBELLet al(eds)
388 Groups St Andrews 2009 in Bath II, C.M. CAMPBELLet al(eds)
389 Random fields on the sphere, D. MARINUCCI & G. PECCATI
390 Localization in periodic potentials, D.E. PELINOVSKY
391 Fusion systems in algebra and topology, M. ASCHBACHER, R. KESSAR & B. OLIVER
392 Surveys in combinatorics 2011, R. CHAPMAN (ed)
393 Non-abelian fundamental groups and Iwasawa theory, J. COATESet al(eds)
394 Variational problems in differential geometry, R. BIELAWSKI, K. HOUSTON & M. SPEIGHT (eds)
395 How groups grow, A. MANN
396 Arithmetic differential operators over thep-adic integers, C.C. RALPH & S.R. SIMANCA
397 Hyperbolic geometry and applications in quantum chaos and cosmology, J. BOLTE & F. STEINER (eds)
398 Mathematical models in contact mechanics, M. SOFONEA & A. MATEI
399 Circuit double cover of graphs, C.-Q. ZHANG
400 Dense sphere packings: a blueprint for formal proofs, T. HALES
401 A double Hall algebra approach to affine quantum Schur–Weyl theory, B. DENG, J. DU & Q. FU
402 Mathematical aspects of fluid mechanics, J.C. ROBINSON, J.L. RODRIGO & W. SADOWSKI (eds)
403 Foundations of computational mathematics, Budapest 2011, F. CUCKER, T. KRICK, A. PINKUS &
A. SZANTO (eds)
404 Operator methods for boundary value problems, S. HASSI, H.S.V. DE SNOO & F.H. SZAFRANIEC (eds)
405 Torsors,´etale homotopy and applications to rational points, A.N. SKOROBOGATOV (ed)
406 Appalachian set theory, J. CUMMINGS & E. SCHIMMERLING (eds)
407 The maximal subgroups of the low-dimensional finite classical groups, J.N. BRAY, D.F. HOLT &
C.M. RONEY-DOUGAL
408 Complexity science: the Warwick master’s course, R. BALL, V. KOLOKOLTSOV & R.S. MACKAY (eds)
409 Surveys in combinatorics 2013, S.R. BLACKBURN, S. GERKE & M. WILDON (eds)
410 Representation theory and harmonic analysis of wreath products of finite groups,
T. CECCHERINI-SILBERSTEIN, F. SCARABOTTI & F. TOLLI

8. 411 Moduli spaces, L. BRAMBILA-PAZ, O. GARC´IA-PRADA, P. NEWSTEAD & R.P. THOMAS (eds)
412 Automorphisms and equivalence relations in topological dynamics, D.B. ELLIS & R. ELLIS
413 Optimal transportation, Y. OLLIVIER, H. PAJOT & C. VILLANI (eds)
414 Automorphic forms and Galois representations I, F. DIAMOND, P.L. KASSAEI & M. KIM (eds)
415 Automorphic forms and Galois representations II, F. DIAMOND, P.L. KASSAEI & M. KIM (eds)
416 Reversibility in dynamics and group theory, A.G. O’FARRELL & I. SHORT
417 Recent advances in algebraic geometry, C.D. HACON, M. MUSTAT¸ˇA & M. POPA (eds)
418 The Bloch–Kato conjecture for the Riemann zeta function, J. COATES, A. RAGHURAM, A. SAIKIA &
R. SUJATHA (eds)
419 The Cauchy problem for non-Lipschitz semi-linear parabolic partial differential equations, J.C. MEYER &
D.J. NEEDHAM
420 Arithmetic and geometry, L. DIEULEFAITet al(eds)
421 O-minimality and Diophantine geometry, G.O. JONES & A.J. WILKIE (eds)
422 Groups St Andrews 2013, C.M. CAMPBELLet al(eds)
423 Inequalities for graph eigenvalues, Z. STANI´C
424 Surveys in combinatorics 2015, A. CZUMAJet al(eds)
425 Geometry, topology and dynamics in negative curvature, C.S. ARAVINDA, F.T. FARRELL &
J.-F. LAFONT (eds)
426 Lectures on the theory of water waves, T. BRIDGES, M. GROVES & D. NICHOLLS (eds)
427 Recent advances in Hodge theory, M. KERR & G. PEARLSTEIN (eds)
428 Geometry in a Fr´echet context, C.T.J. DODSON, G. GALANIS & E. VASSILIOU
429 Sheaves and functions modulop, L. TAELMAN
430 Recent progress in the theory of the Euler and Navier–Stokes equations, J.C. ROBINSON, J.L.RODRIGO,
W. SADOWSKI & A. VIDAL-L´OPEZ (eds)
431 Harmonic and subharmonic function theory on the real hyperbolic ball, M. STOLL
432 Topics in graph automorphisms and reconstruction (2nd Edition), J. LAURI & R. SCAPELLATO
433 Regular and irregular holonomic D-modules, M. KASHIWARA & P. SCHAPIRA
434 Analytic semigroups and semilinear initial boundary value problems (2nd Edition), K. TAIRA
435 Graded rings and graded Grothendieck groups, R. HAZRAT
436 Groups, graphs and random walks, T. CECCHERINI-SILBERSTEIN, M. SALVATORI & E. SAVA-HUSS
(eds)
437 Dynamics and analytic number theory, D. BADZIAHIN, A. GORODNIK & N. PEYERIMHOFF (eds)
438 Random walks and heat kernels on graphs, M.T. BARLOW
439 Evolution equations, K. AMMARI & S. GERBI (eds)
440 Surveys in combinatorics 2017, A. CLAESSONet al(eds)
441 Polynomials and the mod 2 Steenrod algebra I, G. WALKER & R.M.W. WOOD
442 Polynomials and the mod 2 Steenrod algebra II, G. WALKER & R.M.W. WOOD
443 Asymptotic analysis in general relativity, T. DAUD´E, D. H¨AFNER & J.-P. NICOLAS (eds)
444 Geometric and cohomological group theory, P.H. KROPHOLLER, I.J. LEARY, C. MART´INEZ-P´EREZ &
B.E.A. NUCINKIS (eds)
445 Introduction to hidden semi-Markov models, J. VAN DER HOEK & R.J. ELLIOTT
446 Advances in two-dimensional homotopy and combinatorial group theory, W. METZLER &
S. ROSEBROCK (eds)
447 New directions in locally compact groups, P.-E. CAPRACE & N. MONOD (eds)
448 Synthetic differential topology, M.C. BUNGE, F. GAGO & A.M. SAN LUIS
449 Permutation groups and cartesian decompositions, C.E. PRAEGER & C. SCHNEIDER
450 Partial differential equations arising from physics and geometry, M. BEN AYEDet al(eds)
451 Topological methods in group theory, N. BROADDUS, M. DAVIS, J.-F. LAFONT & I. ORTIZ (eds)
452 Partial differential equations in fluid mechanics, C.L. FEFFERMAN, J.C. ROBINSON & J.L. RODRIGO (eds)
453 Stochastic stability of differential equations in abstract spaces, K. LIU
454 Beyond hyperbolicity, M. HAGEN, R. WEBB & H. WILTON (eds)
455 Groups St Andrews 2017 in Birmingham, C.M. CAMPBELLet al(eds)
456 Surveys in combinatorics 2019, A. LO, R. MYCROFT, G. PERARNAU & A. TREGLOWN (eds)
457 Shimura varieties, T. HAINES & M. HARRIS (eds)
458 Integrable systems and algebraic geometry I, R. DONAGI & T. SHASKA (eds)
459 Integrable systems and algebraic geometry II, R. DONAGI & T. SHASKA (eds)
460 Wigner-type theorems for Hilbert Grassmannians, M. PANKOV
461 Analysis and geometry on graphs and manifolds, M. KELLER, D. LENZ & R.K. WOJCIECHOWSKI
462 Zeta andL-functions of varieties and motives, B. KAHN
463 Differential geometry in the large, O. DEARRICOTTet al(eds)
464 Lectures on orthogonal polynomials and special functions, H.S. COHL & M.E.H. ISMAIL (eds)
465 Constrained Willmore surfaces,´A.C. QUINTINO
466 Invariance of modules under automorphisms of their envelopes and covers, A.K. SRIVASTAVA,
A. TUGANBAEV & P.A.GUIL ASENSIO
467 The genesis of the Langlands program, J. MUELLER & F. SHAHIDI
468 (Co)end calculus, F. LOREGIAN
469 Computational cryptography, J.W. BOS & M. STAM

9. ‘This volume celebrates the research career of Arjen Lenstra. The volume covers the latest research
in many areas of applied cryptography: from algorithms for factoring and discrete log, to fast
implementations of computer algebra, to the selection of cryptographic key sizes. Each topic is
masterfully covered by a top researcher in the respective area. The information covered in this
volume will serve readers for many years to come, and is sure to inspire further research on these
topics.’
– Dan Boneh, Stanford University
‘This book demonstrates the breathtaking diversity of Arjen Lenstra’s research over the last 40
years, and the deep influence his work has had on computational aspects of cryptography. Each
chapter is written by a leading domain expert and provides an “in a nutshell” overview of a specific
topic. The book is sure to become an important reference for experts and beginners alike.’
– Kenneth Paterson, ETH Zurich
‘With highly accessible surveys by leading cryptographers, this book hits all pins with a single
strike: framing the important area of “computational cryptography” through its fascinating history,
peeking into its (no less prominent) future, and celebrating the impactful research career of one of
its principal architects, Arjen Lenstra.’
– Ronald Cramer, CWI Amsterdam and Leiden University

11. Computational Cryptography
Algorithmic Aspects of Cryptology
Edited by
JOPPE W. BOS
NXP Semiconductors, Belgium
MARTIJN STAM
Simula UiB, Norway

12. University Printing House, Cambridge CB2 8BS, United Kingdom
One Liberty Plaza, 20th Floor, New York, NY 10006, USA
477 Williamstown Road, Port Melbourne, VIC 3207, Australia
314–321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre,
New Delhi – 110025, India
103 Penang Road, #05–06/07, Visioncrest Commercial, Singapore 238467
Cambridge University Press is part of the University of Cambridge.
It furthers the University’s mission by disseminating knowledge in the pursuit of
education, learning, and research at the highest international levels of excellence.
www.cambridge.org
Information on this title:www.cambridge.org/9781108795937
DOI:10.1017/9781108854207
© Cambridge University Press 2021
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2021
Printed in the United Kingdom by TJ Books Limited, Padstow Cornwall
A catalogue record for this publication is available from the British Library.
Library of Congress Cataloging-in-Publication Data
Names: Bos, Joppe W., editor.|Stam, Martijn, editor.
Title: Computational cryptography : algorithmic aspects of cryptology /
edited by Joppe W. Bos, NXP Semiconductors, Belgium, Martijn Stam,
Simula UiB, Norway.
Description: Cambridge, United Kingdom ; New York, NY, USA : Cambridge
University Press, 2021.|Series: London mathematical society lecture
note series|Includes bibliographical references and index.
Identifiers: LCCN 2021012303 (print)|LCCN 2021012304 (ebook)|
ISBN 9781108795937 (paperback)|ISBN 9781108854207 (epub)
Subjects: LCSH: Cryptography.|BISAC: MATHEMATICS / Number Theory|
MATHEMATICS / Number Theory
Classification: LCC QA268 .C693 2021 (print)|LCC QA268 (ebook)|
DDC 005.8/24–dc23
LC record available at
LC ebook record available at
ISBN 978-1-108-79593-7 Paperback
Cambridge University Press has no responsibility for the persistence or accuracy of
URLs for external or third-party internet websites referred to in this publication
and does not guarantee that any content on such websites is, or will remain,
accurate or appropriate.

13. Contents
List of Contributors pagex
Preface xi
1 IntroductionJoppe W. Bos and Martijn Stam 1
1.1 Biographical Sketch
1.2 Outline
Part I Cryptanalysis
2 Lattice Attacks on NTRU and LWE:
A History of RefinementsMartin R. Albrecht and Léo Ducas15
2.1 Introduction
2.2 Notation and Preliminaries
2.3 Lattice Reduction: Theory
2.4 Practical Behaviour on Random Lattices
2.5 Behaviour on LWE Instances
2.6 Behaviour on NTRU Instances
3 History of Integer FactorisationSamuel S. Wagstaff ,Jr 41
3.1 The Dark Ages: Before RSA
3.2 The Enlightenment: RSA
3.3 The Renaissance: Continued Fractions
3.4 The Reformation: A Quadratic Sieve
3.5 The Revolution: A Number Field Sieve
3.6 An Exquisite Diversion: Elliptic Curves
3.7 The Future: How Hard Can Factoring Be?

14. viii Contents
4 Lattice-Based Integer Factorisation:
An Introduction to Coppersmith’s MethodAlexander May 78
4.1 Introduction to Coppersmith’s Method
4.2 Useful Coppersmith-Type Theorems
4.3 Applications in the Univariate Case
4.4 Multivariate Applications: Small Secret Exponent RSA
4.5 Open Problems and Further Directions
5 Computing Discrete LogarithmsRobert Granger and
Antoine Joux 106
5.1 Introduction
5.2 Elliptic Curves
5.3 Some Group Descriptions with Easier Discrete Logarithms
5.4 Discrete Logarithms for XTR and Algebraic Tori
5.5 Discrete Logarithms in Finite Fields of Fixed Characteristic
5.6 Conclusion
6 RSA, DH and DSA in the WildNadia Heninger 140
6.1 Introduction
6.2 RSA
6.3 Diffie–Hellman 154
6.4 Elliptic-Curve Diffie–Hellman 170
6.5 (EC)DSA 174
6.6 Conclusion 181
7 A Survey of Chosen-Prefix Collision AttacksMarc Stevens 182
7.1 Cryptographic Hash Functions 182
7.2 Chosen-Prefix Collisions 186
7.3 Chosen-Prefix Collision Abuse Scenarios 190
7.4 MD5 Collision Attacks 212
Part II Implementations
8Efficient Modular ArithmeticJoppe W. Bos, Thorsten Kleinjung
and Dan Page 223
8.1 Montgomery Multiplication
8.2 Arithmetic for RSA
8.3 Arithmetic for ECC
8.4 Special Arithmetic

15. Contents ix
9 Arithmetic Software LibrariesVictor Shoup 251
9.1 Introduction
9.2 Long-Integer Arithmetic
9.3 Number-Theoretic Transforms
9.4 Arithmetic inZ
p[X] for Multi-Precisionp 270
9.5 Arithmetic inZ
p[X] for Single-Precisionp 282
9.6 Matrix Arithmetic overZ
p 286
9.7 Polynomial and Matrix Arithmetic over Other Finite Rings
9.8 Polynomial and Matrix Arithmetic overZ 289
9.9 The Future of NTL
10 XTR and ToriMartijn Stam 293
10.1 The Birth of XTR
10.2 The Magic of XTR
10.3 The Conservative Use of Tori
10.4 Pairings with Elliptic Curves
10.5 Over the Edge: Cyclotomic Subgroups Recycled
11 History of Cryptographic Key SizesNigel P. Smart and
Emmanuel Thomé 314
11.1 Introduction
11.2 Attacking Symmetric Algorithms with Software and
Hardware
11.3 Software Attacks on Factoring and Discrete Logarithms
11.4 Hardware for Factoring
11.5 Attacking Cryptosystems Based on Elliptic Curves
11.6 Post-Quantum Cryptography
11.7 Key-Size Recommendation
References 335
Index 383

16. Contributors
Martin R. AlbrechtInformation Security Group, Royal Holloway, University
of London, United Kingdom
Joppe W. BosNXP Semiconductors, Leuven, Belgium
Léo DucasCentrum Wiskunde&Informatica (CWI), Amsterdam, The Nether-
lands
Robert GrangerUniversity of Surrey, Guildford, United Kingdom
Nadia HeningerUniversity of California, San Diego, USA
Antoine JouxCISPA Helmholtz Center for Information Security, Saarbrücken,
Germany
Thorsten KleinjungEPFL, Lausanne, Switzerland
Alexander MayRUB, Bochum, Germany
Dan PageUniversity of Bristol, Bristol, United Kingdom
Victor ShoupNew York University, New York, USA
Nigel P. Smartimec-COSIC, KU Leuven, Leuven, Belgium
Martijn StamSimula UiB, Bergen, Norway
Marc StevensCentrum Wiskunde&Informatica (CWI), Amsterdam, The Nether-
lands
Emmanuel ThoméUniversité de Lorraine, CNRS, INRIA, Nancy, France
Samuel S. Wagstaff,Jr Purdue University, West Lafayette, USA

17. Preface
This book is a tribute to the scientific research career of Professor Arjen K.
Lenstra, on the occasion of his 65th birthday. Its main focus is on computa-
tional cryptography. This area, which he has helped to shape during the past
four decades, is dedicated to the development of effective methods in algo-
rithmic number theory that improve implementation of cryptosystems or that
further their cryptanalysis. Here, cryptanalysis of cryptosystems entails both
the assessment of their overall security and the evaluation of the hardness of
any underlying computational assumptions. In the latter case, the area inter-
sects non-trivially with high-performance scientific computing. The technical
chapters in this book are inspired by his achievements in computational crypto-
graphy.
Arjen is best known for his seminal work on the algorithmic aspects of vari-
ous factorisation problems. In the early 1980s, he started with efficient factori-
sation of polynomials with rational coefficients. This work led to the celebrated
Lenstra–Lenstra–Lovász lattice reduction algorithm. Furthermore, he devised
factorisation techniques for polynomials defined over other algebraic struc-
tures, such as finite fields or number fields. Towards the end of the decade, his
focus shifted to integer factorisation methods, particularly development of the
number field sieve, and its impact on the selection of strong cryptographic keys
for widely deployed cryptographic standards. His honours include the RSA
Award for Excellence in Mathematics in 2008 and his lifetime appointment as
Fellow of the International Association for Cryptologic Research (IACR) in
2009.
In addition to his rich research career, Arjen is a great educator and he
has provided lasting inspiration to many of his students. We both were lucky
enough to have him as our PhD supervisor and we will come back to our re-
spective experiences momentarily. This book is intended for students in se-
curity and cryptography as well as for security engineers and architects in

18. xii Preface
industry who want to develop a deeper understanding about the algorithms
used in computational cryptography.
When I (Martijn) started my PhD studies at the TU Eindhoven, Arjen was
not yet appointed as a part-time professor there, but as soon as he did, there was
an immediate click. Although he wasn’t physically in Eindhoven that often,
his availability and generosity with his time always struck me. We often met at
conferences, where he would invariably join the front row, providing me with
a running commentary, but also where he would introduce me to his wider
academic network. One peculiarity when working with Arjen is his absolute
aversion of footnotes, which he enthusiastically weeded out of early drafts
of papers and also discouraged by expecting some friendly ‘compensation’
for each footnote remaining in my final PhD thesis. When he was appointed
as a full professor at EPFL, a few years after my graduation, he asked me
whether I wanted to join as a post-doctoral researcher. During those years he
encouraged me to explore my own research agenda and helped me to mature
as an independent academic.
After I (Joppe) obtained my master’s degree in Amsterdam, the required
funding for a PhD position related to integer factorisation failed to materialise.
When Arjen learned about this, he arranged for me to come over and even-
tually start my PhD study in Lausanne. There we had the coolest equipment
to brag about at birthday parties: a cluster of PlayStation 3 game consoles.
More seriously, with his broad academic network he ensured I could collabo-
rate with the brightest minds in public-key cryptology. This led to a summer
internship under the supervision of Peter Montgomery at Microsoft Research,
where I eventually became a post-doctoral researcher which paved the way for
me to join the Competence Center Crypto & Security at NXP Semiconductors.
I learned a lot from Arjen’s direct but honest way of conducting research and
to always ask critical questions when people skim over the sometimes compli-
cated but necessary details.
It was a genuine pleasure for both of us (being PhD siblings) to honour
Arjen’s scientific career. We would like to thank all the contributors who are
leading researchers in the various fields for their participation and hope you
(the reader) will enjoy reading this book and be as enthusiastic about the fas-
cinating and interesting field of computational cryptography as we are.

19. 1
Introduction
Joppe W. Bos and Martijn Stam
This introductory chapter provides a sketch of Arjen Klaas Lenstra’s scientific
career, followed by a preview of the technical chapters. We are indebted to
Ronald Cramer and Herman te Riele for information about Arjen’s longstand-
ing connections to CWI, Monique Amhof for providing additional information
about Arjen’s time at EPFL and Peter van Emde Boas for his kind permission
to use a photograph from his private collection.
1.1 Biographical Sketch
Arjen Klaas Lenstra was born on 2 March 1956 in Groningen, the Nether-
lands. He received a BA and an MA degree in Mathematics and Physics at
the University of Amsterdam in 1975 and 1980, respectively. The picture in
Figure 1.1 shows Arjen defending his master’s thesis. Afterwards, he obtained
a research position at CWI – the Dutch national research institute for mathe-
matics and computer science – in Amsterdam and started conducting his PhD
research. Actually, when Arjen started in 1980, the institute was still called
Mathematisch Centrum, but in 1983 it would be renamed CWI, an abbrevi-
ation for ‘Centrum voor Wiskunde en Informatica’, using the Dutch words
‘wiskunde’ for mathematics and ‘informatica’ for computer science. This re-
naming reflected the emergence of computer science as a discipline in its own
right, separate from mathematics. In retrospect, the new name CWI turned out
to be indicative for Arjen’s research career as well. Throughout, his work has
provided exemplary proof of the impressive powers summoned by harnessing
both mathematics and computer science. Since his PhD days, he has always
maintained close links with CWI, for instance, as an officially appointed advi-
sor from 2004 until 2017, but also by co-supervision of various PhD students
from CWI over the years.

20. 2 Joppe W. Bos and Martijn Stam
Figure 1.1 Arjen defending his master’s thesis on 10 December 1980. The
committee, seated behind the desk, was formed by Th. J. Dekker, Peter van
Emde Boas and Hendrik W. Lenstra, Jr. Photo from the private collection of
van Emde Boas.
Arjen’s own PhD research at CWI was conducted under the external super-
vision of Peter van Emde Boas and, in 1984, he received his PhD degree at the
University of Amsterdam for his work on ‘polynomial time algorithms for the
factorization of polynomials’ [312, 362, 363, 364, 380], which was also the
title of his PhD thesis [365]. One key ingredient of this research became one of
his most widely known results: the Lenstra–Lenstra–Lovász (LLL) lattice basis
reduction algorithm, a polynomial time lattice basis reduction algorithm [380].
The LLL algorithm found countless applications, as described in more detail
in the LLL book [457] that was published to commemorate its 25th birthday.
Accurately predicting the effectiveness and efficiency of lattice reduction algo-
rithms continues to be a key tool in the cryptanalytic toolbox. Indeed, with the
ongoing post-quantum cryptographic standardisation effort, LLL and similar
algorithms play an essential role in determining the practical parameters for
lattice-based cryptography. This is detailed further in Chapter 2.
From 1984 to 1989, Arjen was a visiting professor at the computer science
department of the University of Chicago. During this time he retained a posi-
tion as visiting researcher at CWI and he conducted multiple summer research
visits to Digital Equipment Corporation (DEC) in Palo Alto, CA. These lat-
ter visits resulted in the famous distributed effort using factoring by electronic
mail together with Mark S. Manasse [371]. Such computational cryptanalysis

21. 1 Introduction 3
Figure 1.2 Reward for the factorisation of theScientific AmericanRSA chal-
lenge.
is essential to understand the practical security strength of the Rivest–Shamir–
Adleman (RSA) cryptosystem [501], which is related to the presumed hardness
of integer factorisation. It marked the start of Arjen’s research in all compu-
tational aspects of integer factorisation, leading to his involvement in virtu-
ally all integer factorisation records. His records include the factorisation of
the ninth Fermat number [382] using the first implementation of the number
field sieve [381], solving the famousScientific AmericanRSA challenge [24]
by using the quadratic sieve algorithm [478], the kilo-bit [22] special num-
ber field sieve factorisation [474], new elliptic-curve integer factorisation [388]
records by using game consoles [90] and the factorisation of the RSA-768 chal-
lenge [327] (but see also [90, 117, 118, 143, 156, 165, 329, 371, 372, 384]).
His work on theScientific AmericanRSA challenge was even featured on the
front page of theNew York Timeson 12 October 1988 and, after some delay,
he and his collaborators received their due reward for solving this challenge,
as evidenced by Figure 1.2. His brother Hendrik would eventually refer to him
as ‘world champion in factoring’.
Arjen’s involvement led to many practical optimisations of these algorithms
[167, 224, 372, 392, 428] and most notably to the development of the num-
ber field sieve [381]. A historical overview of integer factorisation techniques,
including the asymptotically best methods to which Arjen contributed, is pro-
vided in Chapter 3.
In order to run integer factorisation algorithms on a large variety of com-
puter architectures, a portable and fast arbitrary-length integer arithmetic soft-
ware library was needed. Arjen developed the software library FreeLIP (1988–
1992), later maintained by Paul Leyland. FreeLIP was used in the early integer
factorisation records and formed the early backbone of Shoup’s Number The-
ory Library (NTL). More details about the relationship between FreeLIP, NTL,

22. 4 Joppe W. Bos and Martijn Stam
and other high-performance, portable software libraries for doing number the-
ory are outlined and explained in Chapter 9.
Recall that Arjen’s PhD research on polynomial factoring included the LLL
algorithm for lattice reduction. In 1996, Coppersmith [136, 137] showed how
the LLL algorithm can be used to factor poorly generated RSA keys in poly-
nomial time. Lattice-based integer factorisation methods are the main topic of
Chapter 4. In this chapter, the details behind Coppersmith’s method and how
to use this for assessing the security of the RSA cryptosystem are explained.
Showing the practical impact of various asymptotic methods and deter-
mining, for given circumstances, which is superior is one of the main in-
gredients when recommending cryptographic key sizes in standards. Arjen
pioneered the concrete extrapolation of known factoring and DLP methods
to determine meaningful bit-level security estimates for common cryptosys-
tems, including their long-term security. His contributions in this field are
widely known and valued by academia, industry and government agencies
alike [328, 368, 376, 379] and served as the foundation to determine the ex-
act key sizes for different security levels for virtually all public-key crypt-
ographic standards. More details about the history of selecting appropriate
cryptographic keys and current recommendations are described in Chapter 11.
From 1989 to 1996, Arjen held various positions at Bell Communica-
tions Research, Morristown, NJ, in the Mathematics and Cryptology Research
Group. From 1996 to 2002 he was Vice President of Emerging Technologies
in the Corporate Technology Office of Citibank and from 2002 to 2004 Vice
President, Information Security Services, still at Citibank. He joined Lucent
Technologies’ Bell Labs in 2004 where he stayed until the end of 2005.
In addition to his corporate positions at Citibank and later Bell Labs, from
2000 to the end of 2005 Arjen held a position as part-time professor at the
Department of Mathematics and Computer Science at the Technische Univer-
siteit Eindhoven in the Netherlands. When the appointment was still being
negotiated, the Dean had to keep the Faculteitsraad (‘Departmental Council’)
informed, although without mentioning any concrete names. At the time, the
Dean happened to be his brother Jan Karel, who appeared to take some plea-
sure in referring to an excellent candidate for a part-time professorship as a
reknowned Dutch cryptographer who – tongue in cheek – had turned banker.
At the beginning of this period, Arjen invented XTR, together with Eric
Verheul [375, 377, 378]. In Eindhoven, Arjen remotely supervised a number
of PhD students, including this book’s second editor, whose topic was related
to XTR [559, 560]. An overview of XTR and subsequent developments is pro-
vided in Chapter 10.
At the start of 2006, Arjen was appointed a professor at the École

23. 1 Introduction 5
Figure 1.3 Photo of Arjen in front of the PS3 cluster taken in 2014. Copy-
right @Tamedia Publications romandes/Sabine Papilloud.
Polytechnique Fédérale de Lausanne (EPFL) in Lausanne, Switzerland. At
EPFL, it is customary for professors to name their group a ‘laboratory’ with
associated acronym. Arjen proudly settled on LACAL, as it worked both in
French and in English. Of course, for any abbreviation to work in both those
languages, it helps if this is a palindrome and LACAL fitted the bill perfectly.
In English it stands for LAboratory for Cryptologic ALgorithms, whereas in
French it reads LAboratoire de Cryptologie ALgorithmique.
At LACAL, Arjen continued his focus on the design and analysis of algo-
rithms used in cryptographic protocols or security assessments. Given Arjen’s
interest in computational cryptography, in hindsight it was no surprise that
he started to investigate cheap and powerful alternatives to conventional com-
puter clusters, culminating in the purchase of 215 first generation PlayStation 3
(PS3) game consoles in 2007. The purchase of this exotic computer cluster co-
incided with the start of the PhD of this book’s first editor in Arjen’s group
at EPFL. Arjen and his cluster were featured in a local newspaper in 2014; a
photo as used by the newspaper of Arjen posing in front of the cluster is shown
in Figure 1.3.
The main motivation for using the PS3 game console for computational
cryptography was the Cell processor: a powerful general-purpose processor,
which on the first generation PS3s could be accessed using Sony’s hypervisor.
What made a PS3’s Cell processor especially interesting were its eight Syner-
gistic Processing Units (SPUs), although when running Linux only six of these
SPUs can be used (as one is disabled and one is reserved by the hypervisor).

24. 6 Joppe W. Bos and Martijn Stam
Each SPU runs independently from the others at 3.2GHz, using its own 256
kilobyte of fast local memory for instructions and data. It is cache-less and
has 128 registers of 128 bits each, allowing Single Instruction, Multiple Data
(SIMD) operations on 16 8-bit, 8 16-bit, or 4 32-bit integers. This opens up a
myriad of algorithmic possibilities to enhance cryptographic as well as crypt-
analytic applications. Indeed, a wide variety of projects were executed on the
PS3 cluster.
A particular notorious one was a continuation of Arjen’s previous work with
Xiaoyun Wang and Benne de Weger related to the possibility of constructing
meaningful hash collisions for public keys [369, 385]. This research effort, led
by Marc Stevens, resulted in short chosen-prefix collisions for MD5 and, more
impactful, rogue CA certificates [570, 573, 574]. The details are described in
Chapter 7.
The PS3 cluster was also used by the first author for a PhD project to com-
pute a 112-bit elliptic curve discrete logarithm, an effort roughly equivalent to
14 full 56-bit DES key searches and, at the time, a new ECDLP record [89, 91].
It is worth highlighting that members of Arjen’s lab LACAL played an impor-
tant role in the fall of discrete logarithms in finite fields of fixed character-
istic over the past decade. Arjen’s involvement in computing discrete loga-
rithms [91, 330, 366] as well as recent progress is detailed in Chapter 5.
Other computational research sparked by the cluster include fast modular
multiplication [85, 86, 90]. Chapter 8 provides a detailed description on fast
modular reduction.
Working with the cluster was a fun and unique experience: after all, not ev-
ery PhD student gets the opportunity to work with such challenging computer
equipment. The bespoke installation of the cluster also led to some hilarious
moments. At some point, after a global power glitch at EPFL, the PhD students
(first author included) had to climb the racks in order to manually switch on
every PS3 again, all much to Arjen’s entertainment.
In an original twist on ‘dual-use cryptography’, Arjen had part of the cluster
reconfigured as PlayLab: a room of 25 PS3s equipped with game controllers
and headsets (see Figure 1.4). This room was used to host groups of children
between 7 and 18 years old. There were various kinds of demos and presen-
tations, ranging from explaining the Cell processor as an eight-headed dragon
to a live demo on MD5 password cracking. The presentations in the PlayLab
always ended with the opportunity for the children to play some games. Arjen
himself is not in any sense a gamer, a fact that is emphasised in an interview in
2011 [607]:

25. 1 Introduction 7
Figure 1.4 PlayLab: a room of 25 PS3s equipped with game controllers and
headsets for visits of groups of children aged 7 to 18.
My first exposure to computer games was in 1974, in the basement of the mathematics
department of the university of Amsterdam, where about half a dozen terminals were
remotely connected to Amsterdam’s only computer (a CDC with 12-bit bytes, and com-
putationally speaking probably less powerful than a current microwave oven). It may
have been the dungeon-like environment or the unhealthy look of those who were play-
ing, but it did not attract me and that never changed. But, 25 of our playstations are
equipped with monitors and students can come and play one of the many games that
we have.
Besides these computational results, Arjen has a keen interest in the security
assessment of widely deployed security systems. One year he enthusiastically
returned from the RSA conference with a sizeable stash of security dongles
that, upon pressing a button, would reveal a supposedly random six-digit se-
curity code. He had been using this exact same device for some application
already and, after an eery feeling of not-quite-randomness, he had started keep-
ing track of the numbers, which indeed revealed a pattern. Now, the question
was whether the problem was device specific or not, so upon spotting a large
bowl of such devices at the RSA conference, he quietly set upon collecting a
few more samples to confirm his suspicions. After a responsible disclosure to
those hosting the stand with the bowl, the bowl promptly disappeared for the
rest of the conference. Yet, enough devices had been secured to task a mas-
ter’s student with pressing the button sufficiently often to reverse-engineer and
successfully cryptanalyse the device.

26. 8 Joppe W. Bos and Martijn Stam
More seriously, the interest in deployed security system extended to imple-
mentation mistakes or misuse [374, 386]. An age-old adage in cryptanalysis
is ‘to look for plaintext’. In the context of RSA public keys, specifically the
public moduli, this can be translated to look for primes (indeed!) or common
factors. It turns out RSA moduli are often not as random as one might wish.
Progress in this fascinating area is described in Chapter 6.
Arjen’s expertise, broad interest and entertaining way of asking questions,
make him a regular member of PhD committees. Memorable are the moments
where he asks seemingly naive questions which, in the heat of a defense, can
catch a candidate off guard. In one instance, a candidate working on lattice
reduction to find the shortest vector was asked why one would not look for the
longest vector in lattice instead. In another instance, a candidate working on
weaknesses of RSA when either the public exponenteor the private exponent
dis small, was asked what would happen ifeanddare small simultaneously.
Among EPFL students, Arjen is well known for his clear, fun and interesting
lectures. To illustrate examples, he often uses characters from popular televi-
sion series, for example from the American television sitcomThe Big Bang
Theory. The students’ appreciation is highlighted by him twice receiving the
‘polysphère de faculté IC’ (the teaching award handed out by the students from
the computer science department), first in 2008 and then again in 2018. Even
more impressively, in 2011 he received the overall, EPLF-wide best teaching
award (the ‘polysphère d’or’).
The Big Bang Theoryalso featured at LACAL’s movie lunches, where the
team watched an episode of the series, or 30 to 45 minutes of a movie, ev-
ery day while eating: one summer we consumed a substantial part of the
best Spaghetti Westerns. Perhaps it is a tradition inspired by an earlier one,
where Arjen would watch the latest movies with Professor Johannes Buch-
mann while visiting the flagship conference ‘Crypto’ in Santa Barbara, USA.
One such movie wasPulp Fiction, an all-time favorite. Indeed, Arjen’s pref-
erence for movies from the director Quentin Tarantino or the Coen brothers
is no secret. His ideal table partner would be Jules Winnfield (a character in
Pulp Fictionplayed by Samuel L. Jackson) ‘to make philosophy lessons less
unbearable’ [177]. His adoration for Tarantino even made it into a scientific
publication: see e.g. ‘that’s a bingo’ [327, Section 2.5] from the movieInglou-
rious Basterds.

27. 1 Introduction 9
1.2 Outline
Computational cryptography has two sides: a potentially destructive side and
a constructive one. The destructive side challenges the hardness assumptions
underlying modern cryptographic systems by the development of suitable
number-theoretic algorithms; the constructive side offers techniques and rec-
ommendations that help implement and deploy cryptosystems. Although the
two sides are intricately intertwined, this book is divided into two parts ac-
cordingly. The first part is dedicated to cryptanalysis, whereas the second part
focusses on the implementation aspects of computational cryptography.
In Chapter 2, ‘Lattice Attacks on NTRU and LWE: A History of Refine-
ments’, Martin R. Albrecht and Léo Ducas provide an overview of the ad-
vances and techniques used in the field of lattice reduction algorithms. Four
decades after its invention, the LLL algorithm still plays a significant role in
cryptography, not least because it has become one of the main tools to assess
the security of a new wave of lattice-based cryptosystems intended for the new
post-quantum cryptographic standard. The runtime of the LLL algorithm was
always well understood, but the quality of its output, i.e., how short its output
vectors were, could be hard to predict, even heuristically. Yet, an important
aspect in the evaluation of the new lattice schemes are accurate predictions of
the hardness of the underlying lattice problems, which crucially relies on esti-
mating the ‘shortness’ of the vectors that can be efficiently found using lattice
reduction and enumeration. Albrecht and Ducas have been on the forefront of
improving such estimators and build upon their expertise in their chapter.
In Chapter 3, ‘History of Integer Factorisation’, Samuel S. Wagstaff, Jr, gives
a thorough overview of the hardness of one of the cornerstones of modern
public-key cryptography. The history starts with the early effort by Eratos-
thenes and his sieve, eventually leading to the modern number field sieve, cur-
rently the asymptotically fastest general-purpose integer factorisation method
known. Also included are ‘special’ integer factorisation methods like the el-
liptic curve method, where the run-time depends mainly on the size of the
unknown prime divisor. Modern factorisation efforts often include a gradual
escalation of different methods, so it is essential to be familiar with a wide
range of methods and the essence of all relevant algorithms is explained clearly.
Wagstaff ’s chapter is based on his far more extensive book on the same topic
[611].
In Chapter 4, ‘Lattice-Based Integer Factorisation: An Introduction to Cop-
persmith’s Method’, Alexander May investigates the use of LLL to factor in-
tegers as pioneered by Coppersmith. Conceptually, Coppersmith’s method can
be deceptively simple: given additional information about an integer to factor

28. 10 Joppe W. Bos and Martijn Stam
(e.g., the knowledge that an RSA key pair (N,e) has a small corresponding
private exponentd), derive a system of equations with a small root that reveals
the factorisation and use LLL to find the small root. As a result, it becomes
possible to explore exponentially sized search spaces, while preserving poly-
nomial time using the famous LLL lattice reduction algorithm. Yet, exploiting
Coppersmith’s method in a cryptographic context optimally often involves a
number of clever choices related to which system of equations to consider. At
first, a tantalisingly annoying problem where the choice may appear obvious
only in retrospect. May uses his extensive experience in improving the state of
the art to explain the reasoning behind various applications in his chapter.
In Chapter 5, ‘Computing Discrete Logarithms’, Robert Granger and An-
toine Joux discuss the question ‘how hard is it to compute discrete logarithms
in various groups?’. The key ideas and constructions behind the most efficient
algorithms for solving the discrete logarithm problem are detailed, with a focus
on the recent advances related to finite fields of extension degree>1. A high-
light is the rapid development, in the period 2012–2014, of quasi-polynomial
time algorithms to solve the DLP in finite fields of fixed charaterstic. Both
Granger and Joux contributed significantly to this development, albeit on com-
peting teams. For this book, they join forces and explain how different ideas
eventually led to the fall of the fixed characteristic finite field discrete logarithm
problem.
In Chapter 6, ‘RSA, DH and DSA in the Wild’, Nadia Heninger outlines
the various cryptographic pitfalls one can – but really should not – make in
practice. Often it is possible to bypass the ‘hard’ mathematical problem a cryp-
tosystem is based upon, and instead take advantage of implementation, deploy-
ment or protocol mistakes to extract the private key. Often, the techniques used
are excellent examples of the interplay of mathematics and computer science,
requiring a combination of ingenuity to find the core idea and perseverance to
exploit the weakness in practice. Heninger gives a wide-ranging overview of
the multitude of cryptographic implementation vulnerabilities that have been
found in the past decades and their impact in practice, including a fair num-
ber where she was personally involved in identifying the vulnerability. In her
chapter, she wonders whether after several decades of implementation chaos
and catastrophic vulnerabilities, we are doomed, but concludes that there is
hope yet by bringing into practice the lessons learned.
In Chapter 7, ‘A Survey of Chosen-Prefix Collision Attacks’, Marc Stevens
surveys the technical advances, impact and usage of collision attacks for the
most widely used cryptographic hash functions. Cryptographic hash functions
are the Swiss army knives within cryptography and are used in many ap-
plications including digital signature schemes, message authentication codes,

29. 1 Introduction 11
password hashing, cryptocurrencies and content-addressable storage. Stevens
was one of the driving forces in turning initial weaknesses in the compression
function into practical attacks against various widely deployed protocols re-
lying on hash function collision resistance for their security. In his chapter, he
explains how each scenario involves the development of slightly different ideas
to exploit weaknesses in especially MD5.
Chapters 2 to 7 constitute the ‘Cryptanalysis’ part of the book. They directly
affect the vast majority of currently deployed public-key cryptography, as well
as an important family of future, post-quantum schemes. In the second part
of this book, ‘Implementations’, the emphasis shifts to techniques and recom-
mendations to deploy public-key cryptosystems.
In Chapter 8, ‘Efficient Modular Arithmetic’, Joppe W. Bos, Thorsten Klein-
jung and Dan Page discuss how to realise efficient modular arithmetic in prac-
tice on a range of platforms. They cover generic modular multiplication rou-
tines such as the popular Montgomery multiplication as well as special routines
for primes of a specific shape. Moreover, especially fast methods are outlined
that might produce errors with a very small probability. Such faster ‘sloppy
reduction’ techniques are especially beneficial in cryptanalytic settings. Bos,
Kleinjung and Page have all been involved in various cryptographic and crypt-
analytic record-setting software implementations. In their chapter, they explain
how to select the most efficient modular arithmetic routines for the cryptologic
implementation task at hand.
In Chapter 9, ‘Arithmetic Software Libraries’, Victor Shoup provides a peek
under the hood of NTL, a software library for doing number theory, as well as
its relation to a few other related software libraries. NTL supports data struc-
tures and arithmetic operations manipulating signed, arbitrary-length integers,
as well as extensions dealing with vectors, matrices, finite fields, and poly-
nomials over the integers. These mathematical objects are essential building
blocks for any efficient cryptologic implementation. As Shoup explains, he
started development of NTL around 1990 in order to implement novel number-
theoretic algorithms and determine at what point theoretical, asymptotic gains
turned practical. NTL has become an essential tool for number-theoretic crypt-
analysis to answer how well algorithms perform in practice and contains sev-
eral algorithms for lattice basis reduction, including LLL. As explained in
Shoup’s chapter, NTL might have been initially based on FreeLIP, and it con-
tinues to evolve to make best use of GMP and modern hardware to provide
cutting-edge performance.
In Chapter 10, ‘XTR and Tori’, Martijn Stam discusses how to work effi-
ciently and compactly in certain multiplicative subgroups of finite fields. The
emphasis is on XTR, which works in the cyclotomic subgroup ofF
p
6. Stam

30. 12 Joppe W. Bos and Martijn Stam
worked extensively on speeding up XTR and related systems based on alge-
braic tori and uses his first-hand knowledge to provide a historical perspective
of XTR in his chapter.
In Chapter 11, ‘History of Cryptographic Key Sizes’, Nigel P. Smart and
Emmanuel Thomé provide an overview of improvements over the years in es-
timating the security level of the main cryptographic hardness assumptions.
These improvements heavily rely on the algorithmic innovations discussed in
Chapters 2 to 5, but combining all those ideas into concrete key-size recom-
mendations is not immediate. Smart and Thomé have been at the forefront of
cryptanalytic research and recommending cryptographic key sizes and con-
clude with current recommendations in their chapter.

31. PART I
CRYPTANALYSIS

33. 2
Lattice Attacks on NTRU and LWE:
A History of Refinements
Martin R. Albrecht and Léo Ducas
2.1 Introduction
Since its invention in 1982, the Lenstra–Lenstra–Lovász (LLL) lattice re-
duction algorithm [380] has found countless applications. In cryptanaly-
sis, the two most prominent applications of LLL and its generalisations,
e.g., Slide [205], Block-Korkine–Zolotarev (BKZ) [512, 520] and Self-Dual
BKZ (SD-BKZ) [425], are factoring RSA keys with extra information on the
secret key via Coppersmith’s method [136, 451] (see the chapter by Alexander
May) and the cryptanalysis of lattice-based schemes.
After almost 40 years of cryptanalytic applications, predicting and optimis-
ing lattice reduction algorithms remains an active area of research. While we
do have theorems bounding the worst-case performance of these algorithms,
those bounds are asymptotic and not necessarily tight when applied to practi-
cal or even cryptographic instances. Reasoning about the behaviour of those
algorithms relies on heuristics and approximations, some of which are known
to fail for relevant corner cases.
Recently, decades after Arjen Lenstra and his co-authors gave birth to this
fascinating and lively research area, this state of aff airs became a more press-
ing issue. Motivated by post-quantum security, standardisation bodies, govern-
ments and industries started to move towards deploying lattice-based crypto-
graphic algorithms. This spurred the refinement of those heuristics and approx-
imations, leading to a better understanding of the behaviour of these algorithms
over the past few years.
Lattice reduction algorithms, such as LLL and BKZ, proceed with re-
peated local improvements to the lattice basis, and each such local improve-
ment means solving the short(est) vector problem in a lattice of a smaller di-
mension. Therefore, two questions arise: how costly is it to find those local

34. 16 Martin R. Albrecht and Léo Ducas
improvements and what is the global behaviour when those improvements are
applied.
While these two questions may not be perfectly independent, we will, in
this chapter, survey the second one, namely, the global behaviour of such algo-
rithms, given oracle access for finding local improvements. Our focus on the
global behaviour is motivated by our intent to draw more of the community’s
attention to this aspect. We will take a particular interest in the behaviour of
such algorithms on a specific class of lattices, underlying the most popular
lattice problems to build cryptographic primitives, namely the Learning with
Errors (LWE) problem and the NTRU problem. We will emphasise the approx-
imations that have been made, their progressive refinements and highlight open
problems to be addressed.
2.1.1 LWE and NTRU
The LWE problem and the NTRU problem have proven to be versatile build-
ing blocks for cryptographic applications [104, 218, 274, 493]. For both of
these problems, there exist ring and matrix variants. More precisely, the origi-
nal definition of NTRU is the ring variant [274] and the matrix variant is rarely
considered whereas for LWE the original definition is the matrix variant [494]
with a ring variant being defined later [401, 561]. In this chapter, we gener-
ally treat the matrix variants since our focus is on lattice reduction for general
lattices.
Definition 2.1(LWE [494]). Letn,qbe positive integers,χbe a probability
distribution onZandsbe a uniformly random vector inZ
n
q
. We denote byL s,χ
the probability distribution onZ
n
q
×Zqobtained by choosinga∈Z
n
q
uniformly at
random, choosinge∈Zaccording toχand considering it inZ
q, and returning
(a,c)=(a,σa,sφ+e)∈Z
n
q
×Zq.
Decision-LWE is the problem of deciding whether pairs (a,c)∈Z
n
q
×Zqare
sampled according toL
s,χor the uniform distribution onZ
n
q
×Zq.
Search-LWE is the problem of recoveringsfrom pairs (a, c)=(a,σa,sφ+e)∈
Z
n
q
×Zqsampled according toL s,χ.
We note that the above definition puts no restriction on the number of sam-
ples, i.e., LWE is assumed to be secure for any polynomial number of samples.
Further, since for many choices ofn,q,χsolving Decision-LWE allows solv-
ing Search-LWE [105, 494] and vice versa, it is meaningful just to speak of
the LWE problem (for those choices of parameters). By rewriting the system
in systematic form [23], it can be shown that the LWE problem, where each
component of the secretsis sampled from the error distributionχ, is as secure

35. 2 Lattice Attacks on NTRU and LWE: A History of Refinements17
as the problem for uniformly random secrets. LWE with such a secret, follow-
ing the error distribution, is known as normal form LWE. We will consider
normal form LWE in this chapter. Furthermore, in this note, the exact spec-
ification of the distributionχwill not matter, and we may simply specify an
LWE instance by giving the standard deviationσofχ. We will, furthermore,
implicitly assume thatχis centred, i.e., has expectation 0. We may also write
LWE in matrix form asA·s+e≡cmodq. The NTRU problem [274] is
defined as follows.
Definition 2.2(NTRU [274]). Letn,qbe positive integers,f,g∈Z
q[x]be
polynomials of degreensampled from some distributionχ, subject tofbeing
invertible modulo a polynomialφof degreen, and leth=g/fmod (φ, q).
The NTRU problem is the problem of findingf,ggivenh(or any equivalent
solution (x
i
·f,x
i
·g) for somei∈Z).
Concretely, the reader may think ofφ=x
n
+1 whennis a power of two and
χto be some distribution producing polynomials with small coefficients. The
matrix variant considersF,G∈Z
n×n
q
such thatH=G·F
−1
modq.
2.2 Notation and Preliminaries
All vectors are denoted by bold lower case letters and are to be read as column
vectors. Matrices are denoted by bold capital letters. We write a matrixBas
B=(b
0,...,b d−1) whereb iis theith column vector ofB.IfB ∈R
m×d
has full-
column rankd, the latticeΛgenerated by the basisBis denoted byΛ(B)=
{B·x|x∈Z
d
}. A lattice isq-ary if it containsqZ
d
as a sublattice, e.g.,{x∈Z
d
q
|
x·A≡0}for someA∈Z
d×d
π
. We denote by (b
≡
0
,...,b
≡
d−1
) the Gram–Schmidt
(GS) orthogonalisation of the matrix (b
0,...,b d−1). Fori∈{0,...,d−1},we
denote the orthogonal projection to the span of (b
0,...,b i−1)byπ i;π0denotes
‘no projection’, i.e., the identity. We writeπ
vfor the projection orthogonal
to the space spanned byv. For 0≤i<j≤d, we denote byB
[i:j]the local
projected block (π
i(bi),...,πi(bj−1)), and when the basis is clear from context,
byΛ
[i:j]the lattice generated byB [i:j]. We write lg(·) for the logarithm to base
two.
The Euclidean norm of a vectorvis denoted byγvγ. The volume (or de-
terminant) of a latticeΛ(B) is vol(Λ(B)) =
χ
iγb
≡
i
γ. It is an invariant of the
lattice. The first minimum of a latticeΛis the norm of a shortest non-zero
vector, denoted byλ
1(Λ). We use the abbreviations vol(B) =vol(Λ(B)) and
λ
1(B)=λ 1(Λ(B)).
The Hermite constantγ
βis the square of the maximum norm of any shortest

36. 18 Martin R. Albrecht and Léo Ducas
vector in all lattices of unit volume in dimensionβ:
γ
β=sup
σ
λ
2
1
(Λ)|Λ∈R
β
,vol(Λ) =1
φ
.
Minkowski’s theorem allows us to derive an upper boundγ
β=O(β), and
this bound is reached up to a constant factor:γ
β=Θ(β).
2.3 Lattice Reduction: Theory
All lattices of dimensiond≥2 admit infinitely many bases, and two bases
B,B
π
generate (or represent) the same lattice if and only ifB=B
π
·Ufor some
unimodular matrixU∈GL
d(Z). In other words, the set of (full-rank) lattices
can be viewed as the quotient GL
d(R)/GL d(Z). Lattice reduction is the task of
finding a good representative of a lattice, i.e., a basisB∈GL
d(R) representing
Λ∈GL
d(R)/GL d(Z).
While there exists a variety of formal definitions for what is a good repre-
sentative, the general goal is to make the Gram–Schmidt basisB
Θ
as small as
possible. Using the simple size-reduction algorithm (see [454, Algorithm 3]),
it is possible to also enforce the shortness of the basisBitself.
It should be noted that because we have an invariant
χ
iγb
Θ
i
γ=vol(Λ), we
cannot make all GS vectors small at the same time, but the goal becomes to
balance their lengths. More pictorially, we consider the log profile of a basis as
the graph of (
i=lgγb
Θ
i
γ)
i=0...d −1
as a function ofi. By the volume invariant,
the area under this graph is fixed, and the goal of reduction is to make this
graph flatter.
A very strong
1
notion of reduction is the Hermite–Korkine–Zolotarev
(HKZ) reduction, which requires each basis vectorb
ito be a shortest non-zero
vector of the remaining projected latticeΛ
[i:d]. The Block-Korkine–Zolotarev
(BKZ) reduction relaxes HKZ, only requiringb
ito be close-to-shortest in a
local ‘block’. More formally, we have the following.
Definition 2.3(HKZ and BKZ [454]). The basisB=(b
0,...,b d−1) of a lattice
Λis said to be HKZ reduced ifγb
Θ
i
γ=λ 1(Λ(B [i:d])) for alli<d.ItissaidBKZ
reduced with block sizeβand≥0ifγb
Θ
i
γλ(1+)·λ 1(Λ(B [i:min(i+β,d )] )) for
alli<d.
In practice, the BKZ algorithm [512, 520] and its terminated variant [257]
1
HKZ should nevertheless not be considered to be the strongest notion of reduction. Indeed
HKZ is a greedy definition, speaking of the shortness of each vector individually. One could
go further and require, for example,Λ
[0:d/2]to be a densest sublattice ofΛ[491].

37. 2 Lattice Attacks on NTRU and LWE: A History of Refinements19
Algorithm 2.1High-level description of the BKZ algorithm.
Input:LLL-reduced lattice basisBand block sizeβ
1:repeat
2:fori←0tod−2do
3: LLL onB [i:min(i+β,d )]
4: v←find a short vector inΛ
≡
B [i:min(i+β,d )]
π
5: insertvintoBat indexiand handle linear dependencies with LLL
6:untiluntil no more change
are commonly employed to perform lattice reduction. BKZ is also the algo-
rithm we will focus on in this chapter.
The BKZ algorithm will proceed by enforcing the conditionγb
≡
i
γλ(1+)·
λ
1(Λ(B [i:min(i+β,d )] )) cyclically fori=0,...,d−2,0,...,d−2,0..., see Algo-
rithm 2.1. However, each modification ofb
≡
i
may invalidate the same condition
forjχi. The value of, which allows to account for numerical instability, is
typically chosen very close to 0 (say 0.01); we may sometimes omit it and just
speak of a BKZ-β reduced basis. Overall, we obtain the following guarantees
for the BKZ algorithm.
Theorem 2.4(BKZ). If a basisBis BKZ-β reduced with parameter>0it
satisfies
?γb
0γλ
λ
(1+)·γ β
d−1
β−1
+1
·vol(Λ(B))
1/d
(Hermite factor) and
?γb
0γλ
≡
(1+)·γ β
πd−1
β−1
·λ1(Λ(B))(approximation factor).
Remark.The approximation factor is established in [517], the Hermite factor
bound is claimed in [206]. In [257] a bound of 2·
√
γβ
d−1
β−1
+3
is established for
the terminating variant. In [258] this bound is improved toK·
√
β
d−1
β−1
+0.307
for
some universal constantK.
Asymptotically, the lattice reduction algorithm with best, known worst-case
guarantees is Slide reduction [205]. We refer to its introduction by Gama and
Nguyen [205] for a formal definition, which requires the notion of duality, and
only state some of its guarantees concerning Gram–Schmidt length here.
Theorem 2.5(Slide reduction [205]). If a basisBis Slide reduced for param-
etersβ|d and>0it satisfies
?γb
0γλ
λ
(1+)·γ β
d−1
β−1·vol(Λ(B))
1/d
(Hermite factor) and
?γb
0γλ
≡
(1+)·γ β
π
d−β
β−1
·λ1(Λ(B))(approximation factor).

38. 20 Martin R. Albrecht and Léo Ducas
In practice, BKZ is not implemented as in Algorithm 2.1. Most notably,
stronger preprocessing than LLL is applied. A collection of improvements to
the algorithm (when enumeration is used to instantiate the SVP oracle) are
collectively known as BKZ 2.0 [122] and implemented, e.g., in FPLLL [587]
and thus Sage [562]. Slide reduction is also implemented in FPLLL.
2.4 Practical Behaviour on Random Lattices
2.4.1 Shape Approximation
The Gaussian heuristic predicts that the number|Λ∩B|of lattice points inside a
measurable bodyB⊂R
n
is approximately equal to vol(B)/ vol(Λ). Applied to
Euclideand-balls, it leads to the following prediction of the length of a shortest
non-zero vector in a lattice.
Definition 2.6(Gaussian heuristic). We denote by gh(Λ) the expected first
minimum of a latticeΛaccording to the Gaussian heuristic. For a full-rank
latticeΛ⊂R
d
,itisgivenby
gh(Λ) =
Ω
vol(Λ)
vol(B)

1/d
=
Γ
≡
1+
d
2
Γ
1/d
√
π
·vol(Λ)
1/d
≈

d
2πe
·vol(Λ)
1/d
,
whereBdenotes thed-dimensional Euclidean ball. We also denote by gh(d )
the quantity gh(Λ)ofanyd -dimensional latticeΛof volume 1: gh(d )≈
√
d/2πe. For convenience we also denote lgh(x) for lg(gh(x)).
Combining the Gaussian heuristic with the definition of a BKZ reduced ba-
sis, after BKZ-β reduction we expect

i=lg
≡
λ 1(Λ(B [i:min(i+β,d )] ))
Γ
≈lgh(min(β, d−i))+
lg
≡
vol(Λ(B
[i:min(i+β,d )] ))
Γ
min(β,d−i)
=lgh(min(β, d−i))+

min(i+β,d )−1
j=i
j
min(β,d−i)
.
Ifdτβthis linear recurrence implies a geometric series for theΩb
≡
i
Ω.
Considering one block of dimensionβand unit volume, we expect
i=(β−
i−1)·lg(α
β) fori=0,...,β−1 and someα β. We obtain

0=(β−1)·lg(α β)≈lgh(β) +
1
β
β−1

j=0
j·lg(α β)
=lgh(β) +(β−1)/2·lg(α
β).

39. 2 Lattice Attacks on NTRU and LWE: A History of Refinements21
Solving forα
βassuming equality we obtainα β=gh(β)
2/(β−1)
.
Applying the same argument to a basis in dimensiondτβwith
i=(d−
i−1)·lg(α
β) fori=0,...,d−1, we getγb 0γ/vol(Λ)
1/d
=α
d−1
β
/α
(d−1)/2
β
=
α
(d−1)/2
β
=gh(β)
(d−1)/(β−1)
. This is known as the geometric series assumption
(GSA).
Definition 2.7(GSA [518]). LetBbe a BKZ-β reduced basis of a lattice of
volumeV. The geometric series assumption states that
lgγb
Θ
i
γ= i=
d−1−2i
2
·lg(α
β)+
1
d
lgV,
whereα
β=gh(β)
2/(β−1)
.
The above assumption is reasonably accurate in the caseβϕd(andβτ
50), but it ignores what happens in the lastd−βcoordinates. Indeed, the last
block is HKZ reduced, and should therefore follow the typical profile of an
HKZ reduced basis.
Under the Gaussian heuristic, we can predict the shape
0...d−1of an HKZ
reduced basis, i.e., the sequence of expected norms for the vectorsb
Θ
i
. This,
as before, implicitly assumes that all the projected latticesΛ
ialso behave as
random lattices. The sequence is inductively defined as follows.
Definition 2.8.The (unscaled) HKZ shape of dimensiondis defined by the
following sequence fori=0,...,d−1:
h
i=lgh(d−i)−
1
d−i

j<i
hj.
This leads to the following refinement of the GSA.
Definition 2.9(Tail-adapted geometric series assumption (TGSA)). LetBbe
a BKZ-β reduced basis of a lattice of volumeV. The TGSA states that

i=
d−1−2i
2
·lgα
β+s if 0≤i≤d−β,

i=hi−(d−β) +d−β−h0 ifd−β≤i<d,
wheres∈Ris the scaling term such that


i=lgV.
We plot an example for a basis after BKZ reduction under the GSA and
the TGSA in Figure 2.1 to illustrate their respective shapes. In Figure 2.1 we
chosed=2βto highlight the difference between the two models. As can be
seen from that figure, the first few indices of the HKZ shape drop slower than
predicted by the GSA and the last indices drop faster.

40. 22 Martin R. Albrecht and Léo Ducas
0 200 400 600 800 1000
i

i
GSA
TGSA
Figure 2.1 GSA and TGSA ford=1000 andβ=500.
Appealing to the Gaussian heuristic, we may also replace
√
γβ, i.e., worst-
case bounds, with gh(β), i.e., average-case expectations, in Theorems 2.4
and 2.5. This suggests the following heuristics.
Definition 2.10(Estimates for block reductions).If a basisBis BKZ-β re-
duced for 50ϕβϕdwe expect
γb
0γχmin
√
αβ
d−1·vol(Λ(B))
1/d
(Hermite factor)
α
d−1
β
·λ1(Λ(B)) (approximation factor).
If a basisBis Slide reduced with parameterβwe expect
γb
0γχmin
⎧
⎪⎪ ⎨
⎪⎪ ⎩
√
αβ
d−1·vol(Λ(B))
1/d
(Hermite factor)
α
d−β
β
·λ1(Λ(B)) (approximation factor).
The cases over which the minimum is taken define two regimes: the ‘Hermite
regime’ and the ‘approximation regime’.
If the lattice is random, thenλ
1≈gh(Λ) and we expect to be in the Hermite
regime; the approximation regime is only triggered by the presence of an un-
usually short vector. In the Hermite regime, we can replaceχby≈and we will
discuss what happens in the approximation regime further in Section 2.5.4.
We note that the literature usually writes the above approximate equations
in terms of the so-called root-Hermite factorδ
βσ(γb 0γ/vol(Λ)
1/d
)
1/d
. We can
therefore establish thatδ
β=
√
αβ
1−1/d ≈
√
αβ. We note that making this approx-
imation or not leads to the ‘−1 discrepancy’ blamed on [19] in a footnote

41. 2 Lattice Attacks on NTRU and LWE: A History of Refinements23
0 10203040 50 60 70 80 90
0
2
4
6
·10
−2
β
lg(α
β
)
2 lg(δ β) withδ βas in Eq. (2.1)
Average observed lg(α β)
Figure 2.2 Experimentally observed slopes of 16 lattices compared withδ
β
as predicted in Eq. (2.1). The input lattices areq-ary lattices in dimension
d=170 withq=2
20
−3; the experimental lg(α β) are established using a
least-square fit of the log Gram–Schmidt vectors.
of [15]: the analysis of [19] simply did not apply this approximation step.
In [121] an expression forδ
βis given as
lim
β→∞
δβ=
∞
β
2πe
·(πβ)
1
β
∗
1
2(β−1)
(2.1)
assumingdτβ. Experimentally, Eq. (2.1) also holds with good accuracy for
β>50 and typicaldused in cryptography (say,d≥c·βfor somec>1). We
compare experimentally observed lg(α
β) with the right-hand side of Eq. (2.1)
in Figure 2.2.
2.4.2 Simulators
While the (T)GSA provides a first rough approximation of the shape of a basis, it is known to be violated in small dimensions [122]. Indeed, it also does not hold exactly for larger block sizes whendis a small multiple ofβ, the case
most relevant to cryptography. Furthermore, it only models the shape after the algorithm has terminated, leaving open the question of how the quality of the basis improves throughout the algorithm. To address these points, Chen and Nguyen [122] introduced a simulator for the BKZ algorithm which is often re- ferred to as the ‘CN11 simulator’. It takes as input a list of
irepresenting the

42. 24 Martin R. Albrecht and Léo Ducas

i
0 200 400 600800 1000 1200 1400
i

i
−
i−1
i−i−1
Figure 2.3 CN11 simulator output forβ=500 on randomq-ary lattice in
dimensiond=1500.
shape of the input basis and a block sizeβ. It then considers blocks i,...,i+β−1
of dimensionβ, establishes the expected norm of the shortest vector in this
block using the Gaussian heuristic and updates
i. To address that the Gaussian
heuristic does not hold forβ<50, the simulator makes use of a precomputed
list of the average norms of a shortest vector of random lattices in small di-
mensions. The simulator keeps on going until no more changes are made or a
provided limit on the number of iterations or ‘tours’ is reached.
The simulator is implemented, for example, in FPyLLL [588] and thus in
Sage. In Figure 2.3 we plot the output of the simulator for a basis in dimension
1500 with block size 500 (solid line). We also plot the derivative (dotted line)
to illustrate that the GSA also does not hold fori<d−β. In fact, we observe
a ripple effect, with the tail shape exhibiting a damped echo towards the left of
the basis. The TGSA is in some sense only a first-order approximation, only
predicting the first ripple.
A further simulation refinement was proposed in [27]. Building upon [631],
the authors confirmed that the CN11 simulator can be pessimistic about the
norm of the first vector output by BKZ. This is because it assumes that the
shortest vector in a lattice always has the norm that is predicted by the Gaus-
sian heuristic. By, instead, modelling the norm of the shortest vector as a ran-
dom variable, the authors were able to model the ‘head concavity’ behaviour
of BKZ as illustrated in Figure 2.4 after many tours and in small block sizes.
They also proposed a variant of the BKZ algorithm (pressed-BKZ) that is tai-
lored to exploit this phenomenon. For example, they manage to reach a basis

43. 2 Lattice Attacks on NTRU and LWE: A History of Refinements25
02040 60 80 100
i

i
Experiment
CN11 simulator [122]
BSW18 simulator [27]
Figure 2.4 Head concavity: dimensiond=2000 and block sizeβ=45 after
2000 tours, reproduced from [27].
reduction equivalent to BKZ-90 while only using block size 60. The authors
note, though, that the head concavity phenomenon does not significantly af-
fect cryptographic block sizes. Indeed, exploiting luck on this random variable
seems to be interesting for small block sizes only.
2.4.3q-ary Lattices and theZ-Shape
Recall that both NTRU and LWE give rise toq-ary lattices. These lattices al-
ways contain the vector (q, 0,...,0) and all its permutations. These so-called
‘q-vectors’ can be considered short, depending on the parameters of the in-
stance being considered, and might be shorter than what we would expect to
obtain following predictions such as the GSA or the TGSA. Furthermore, some
of thoseq-vectors naturally appear in the typical basis construction ofq-ary lat-
tices. Even when this is not the case, they can be made explicit by computing
the Hermite Normal Form.
To predict lattice reduction on such bases, we may observe that one of the
guarantees of the LLL algorithm is that the first vectorb
0never gets longer. For
certain parameters this can contradict the GSA. In fact, ifb
∗
i
does not change
for alli<j, thenb
∗
j
cannot become longer either, which means that after the
reduction algorithm has completed we may still have many suchq-vectors at
the beginning of our basis, unaffected by the reduction. It is therefore tempting
to predict a piecewise linear profile, with two pieces. It should start with a flat
line at lgq, followed by a sloped portion following the predicted GSA slope.

44. 26 Martin R. Albrecht and Léo Ducas
02040 60 80 100 120 140 160180
−4
−2
0
2
4
6
8
i

i
Input shape
GSA prediction for LLL
LLL reduced bases
Figure 2.5 GSA andq-ary lattice contradiction. Norms of Gram–Schmidt
vectors of 180-dimensional randomq-ary lattices withq=17 and volume
q
80
. The grey, blurry lines plot ifor LLL reduced bases of 16 independent
lattices.
In fact, the shape has three pieces, and this is easy to argue for LLL, since
LLL is a self-dual algorithm.
2
This means in particular that the last Gram–
Schmidt vector cannot get shorter, and following the same argument, we can
conclude that the basis must end with a flat piece of 1-vectors. All in all, the
basis should follow aZ-shape, and this is indeed experimentally the case [280,
625], as depicted in Figure 2.5, where we picked a smallqto highlight the
effect. We shall call such a prediction [169, 625] the ZGSA.
It is tempting to extend such a ZGSA model to other algorithms beyond LLL
and this has been used for example in [169]. We might also attempt to refine
it to a ZTGSA model, where we put an HKZ tail just before the flat section
of Gram–Schmidt vectors of norm 1. However, this is a questionable way of
reasoning, because BKZ, unlike LLL, is not self-dual. However, it is worth
noting that it seems possible to force BKZ to behave in such a way, simply by
restricting BKZ to work on the indices upi<j, wherejis carefully calibrated
so thatγb
≡
j
γκ1. This is not self-dual, but up to the tail of BKZ, it would
produce aZ-shape as well.
Yet, we could also let BKZ work freely on the whole basis, and wonder
what would happen. In other words, we may ask whether it is preferable to
apply such a restriction to BKZ or not. A natural approach to answering this
2
This is not entirely true, as the size-reduction condition is not self-dual, but the constraints on
the Gram–Schmidt vectors themselves are, which is enough for our purpose.

45. Other documents randomly have
different content

46. Helposti saatiin Alhosta tietää, koska hevonen oli lähetetty vastaan
asemalle, ja tulon jälkeisenä aamuna alettiin Ottoa hyvissä ajoin
odottaa Kankaanpäähän. Leni, jonka kangaspuut olivat ikkunan
ääressä, joten hän saattoi nähdä tielle, sai toimekseen valvoa, koska
tutut ajopelit ilmestyisivät tienkäänteeseen. Samassa hetkessä
pantiin kahvipannu tulelle ja leipäkori täytettiin kaikenlaisilla
herkuilla.
Sykkivin sydämin ja salaa katseli Leni uudinten takaa entistä
leikkitoveriaan, jonka kanssa ei enää sopinut leikkiä. Kuinka hän oli
miehistynyt ja käynyt kauniiksi!
Oli kuin suuri, lämmin laine olisi alkanut nousta tytön sisässä ja
posket täyttyivät kuumalla verellä. Hetkisen aikaa hän painoi käsiä
rinnalleen, ikäänkuin tyynnyttääkseen aaltoa, mutta astui sitten
eteiseen, Otto-herraa vastaan… Täti ja setä siellä jo ihmettelivät
kummipoikansa kasvamista, piika auttoi yltä palttoon, armo kävi
kiinni käteen, patruuna hartioihin ja niin vietiin nuorukainen saliin.
Leniä ei kukaan ollut huomaavinaan.
Hänen lämmin suloinen tunteensa kävi äkkiä katkeraksi, kädet
pusertuivat nyrkeiksi ja kyyneleet kohosivat silmiin. Kuinka hän tunsi
vihaavansa sekä Ottoa että armoa ja kaikkia. Hänpä ei menekään
tarjoamaan kahvia, kun käsketään, hän ei ensinkään näyttäydy.
Mutta hetkisen oltuaan ruokasalissa ja oven takaa kuunneltuaan
heidän ääniänsä valtasi hänet niin suuri uteliaisuus, että hän
sittenkin päätti tarjota kahvit ja hillot ja omenat — talviomenat
Kankaanpään omasta puutarhasta.
Kaiken aamua oli hän pukeutunut, mutta yhä vielä teki hänen
mielensä peilin edessä tarkastaa, olivatko hiukset hyvin. Hän valeli

47. kasvojaan vedellä, mutta yhä ne vaan hehkuivat ja hän astui saliin
niin hämillään, että tuskin uskalsi silmiään nostaa…
Otto-herran todistus ei ollut oikein hyvä ja hän selitti voimiensa
takaa, että heidän koulussaan ollaan ankarampia kuin missään
muissa kouluissa. Mitäpä nuo vanhat ihmiset sitten olisivat ruvenneet
poika-raukkaa nuhtelemaan! He uskoivat niin mielellään hänen
sanoihinsa. Täti suuteli häntä otsalle ja setä taputti olkapäälle ja veti
esiin kultarahansa.
Otto oli aina harmitellut noita tapauksia ja suudelmia. Ihan
varmaan se tyttö, se Leni oli jossakin katselemassa! Hän ei voinut
kärsiä sitä tyttöä, häntä hävetti muistellakin, että he joskus olivat
leikkineet yhdessä. Hän päätti nolata hänet perinpohjin, päätti olla
aivan tuntematta häntä. Mutta kun Leni tuli saliin ja seisahtui tädin
eteen, niin vilkaisi Otto häneen syrjästä ja hämmästyi, sillä tyttö oli
aivan muuttunut: hänen hameensa helmat ulottuivat lattiaan asti,
vartalo oli kuin täysikasvaneilla ja päälaelle oli koottu pehmeä,
kiiltävä hiusmätäs. Hänen silmänsä olivat hyvin kauniisti maahan
luodut. Oton teki äkkiä mieli mennä häntä tervehtimään, oikein
kädestä, mutta samassa muisti hän päätöksensä, muisti myöskin,
ettei se sedän ja tädin talossa olisi sopinut, ja punastui omia
ajatuksiaan. Hän odotti jäävänsä kahdenkesken Lenin kanssa, sillä
hän tunsi, että hänen välttämättömästi täytyy saada sanoa hänelle
jokin sana. Siihen ei kuitenkaan ilmaantunut tilaisuutta. Rekeen
noustessaan vilkaisi hän ikkunoihin ja erotti silloin selvästi
uudinharsojen takaa tytön kukoistavat kasvot. Mutta ne hävisivät
samassa.
Ensimmäisenä joulupäivänä tuli Otto Kankaanpäähän enemmän
saadakseen nähdä Leniä kuin tervehtiäkseen vanhuksia.

48. Setä nukkui päivällisuntaan ja täti, kissa sylissä, uinui ruokasalin
suuressa nojatuolissa. Hän ilostui suuresti, kun Otto tuli, ja rupesi
paikalla purkamaan hänelle huoliaan. Hänen oli kesken joulupäivää
pitänyt torua Leniä.
— Jaa, minä en tiedä, mitä minun pitää siitä tytöstä ajatella!
huokasi hän. — Omana lapsenamme olemme häntä pitäneet, kaikki
olemme koettaneet hänelle antaa. Näillä omilla käsilläni olen
opettanut häntä ompelemaan ja kirjoittamaan ja tänään, ihan
yhtäkkiä hän purskahtaa itkuun ja sanoo, että lähtee pois meiltä.
— Onko se mahdollista! sopersi Otto, peläten että hänen
sydämensä tykytys kuuluisi.
— Hän syyttää minua siitä, ettei saa olla nuori eikä huvitella.
Olenko minä koskaan kieltänyt häntä huvittelemasta, kun se
tapahtuu sopivaisuuden rajain sisäpuolella, mutta ymmärtäähän
jokainen, ettei se sellainen, mitä hän nyt tahtoo, käy päinsä. Hän
tahtoisi huomisiin tanssiaisiin, oletko mokomaa kuullut…! Hän aivan
unohtaa kuka hän on: kerjäläisvaimon lapsi!
Otto hämmästyi. Vai heidän, herrasväen tanssiaisiin! Niin, olisi se
tuntunut aika kummalliselta, jos hän olisi ilmestynyt sinne muitten
vieraitten joukkoon… Olisikohan hän saanut tanssia?
— Kukaan ei voine syyttää minua ylpeydestä, jatkoi vanha rouva
kiihkeästi. — Minä kohtelen renkiä ja piikaa kuin vertaistani, jos he
ymmärtävät antaa minulle minun arvoni. Mutta liian tutunomaisiksi
eivät he saa ruveta. Sitä minä en kärsi.
— Tietysti, sopersi Otto. Hänen ajatuksensa kierteli pitkän aikaa,
etsien sanoja, joilla taitaisi rauhoittaa loukkaantunutta armoa.

49. — Missä… missä se Leni nyt on? kysyi hän vihdoin niin
välinpitämättömänä kuin suinkin.
Rouva Liljefelt lähetti palvelijan noutamaan mamsselia. Mutta
mamsseli ei tullut.
— Näetkö sitä sisua. Otto, näetkö!
Otto kävi ensin hyvin neuvottomaksi, mutta hetkisen perästä pääsi
hän sanojen päähän kiinni ja sai aikaan enemmän kuin ikinä itsekään
olisi voinut toivoa.
Leni istui huoneessaan nyrpeänä, itkettynein kasvoin, ankarasti
miettien, mihin nyt suuntaisi kulkunsa, sillä hän ei rupea olemaan
täällä, hän kuolee täällä ikävään, hän menehtyy ja tukahtuu… Ah,
kuinka hän vihaa armoa ja…
Samassa kuului koputus oveen ja kynnykselle astui Otto herra.
Leni tunsi hänet paikalla, vaikkei huoneessa ollut muuta valoa kuin
se, minkä pilvien peittämä kuu loi, ja sävähti kiireesti seisomaan,
silitellen hiuksiaan.
— Hyvää iltaa, alkoi Otto hämillään. — Minä… minä… mitä kuuluu?
— Ei mitään, vastasi Leni kuivasti ja jäi paikoilleen.
Ottokaan ei tullut lähemmäksi. Heidän välillään olivat valkealla
vaatteella peitetyt kangaspuut, niiden ohi näkyi Lenin voimakas
vartalo ikkunaa vastaan. Otto näki, miten hänen rintansa kohoili.
— Armo… täti pyytää tulemaan luokseen, jatkoi Otto epävarmasti.
Ei vastausta.

50. — Täti odottaa.
Leniltä pääsi pieni nauru, katkera ja kiukkuinen.
— Jos mentäisiin…
— Eikö hän sitten vielä ole tarpeekseen torunut! puhkesi Leni
puhumaan. — Minä en tule, en tahdo häntä nähdä.
Otto likeni pari askelta.
— Tietääkös Leni, mitä hän juuri ehdotti? Että me tanssittaisiin.
— Tanssittaisiin! Kuka ja kuka?
— Minä ja Leni. Ruokasalissa.
— Minä! huudahti Leni, — minäkö ja… ja Otto-herra?
— Niin, niin, täti istuu jo soittokoneen ääressä.
Otto tarttui hänen käteensä. Kuinka se oli kuuma!
Ensin hän vastusti, ikäänkuin olisi tahtonut olla päätökselleen
uskollinen, mutta sitten koko hänen katkeruutensa laukesi, hänen
nyrpeytensä haihtui kuin pyyhkäisemällä ja kun he tulivat valaistuun
ruokasaliin, olivat hänen kasvonsa säteilevässä hymyssä.
Nojatuolissa nukkui nyt vain vanha kissa, sillä armo istui todella
salissa soittokoneen ääressä.
— No, Leni, huusi hän ystävällisellä äänellä ruokasaliin, — herra
von Holten on luvannut tanssia sinun kanssasi. Nostakaa nyt pöytä
syrjään, niin voitte tanssia.

51. Sitten alkoi hän kosketella soittokoneen vanhoja, heikkoja kieliä
vanhoilla, kankeilla sormillaan ja pääsi vihdoin kiinni ainoan vanhan
valssinsa päähän. Mutta Lenin mielestä oli tämä soitto ihanaa, hänen
sydämensä sykki kuuluvasti eikä hän uskaltanut nostaa silmiään.
Otto-herra tarttui pöydän toiseen päähän, Leni toiseen, ja yhdessä
käden käänteessä siirsivät he koko kapineen nurkkaan.
— Kunhan minä nyt osaisin! kuiskasi Leni Oton kiertäessä
käsivarttaan hänen ympärilleen.
Se oli kaunis tyttö, jota Otto piteli käsissään. Hän hurmaantui, kun
sitä katseli.
Silmä oli maahan luotu, sen kansi oli kalpea ja lahea kuin
lumivuokon lehti ja siitä valui sinertäviä, hienoja suonia, jotka
päättyivät silmän ripseihin. Mutta poskea vastaan näyttivät ripset
pitkiltä, mustilta… Kuinka hänen hiuksensa lemusivat lehahtaessaan
tanssitoverin kasvoja vastaan! Kuinka hänen ruumiinsa oli pehmeä ja
lämmin, kuinka se värähteli!
— Sehän menee mainiosti! vastasi Otto vihdoin hänen viime
sanoihinsa.
— Kuka onkaan ollut opettajana?
— Minä itse vain. Olen katsellut, kuinka herrasväet tanssivat… Voi
kuinka tämä on lystiä! Ettekö jaksaisi viedä vielä kovemmin… noin,
noin! Kuinka te saitte tätinne suostumaan?
— Selitin hänelle, että… olette nuori.
— Kuinka te olette hyvä, Otto-herra…! Jos te käsittäisitte, miten
ikävää se on, kuin ei kuulu herrasväkeen eikä talonpoikiin, kun ei saa

52. jutella neitien kanssa eikä piikojen kanssa…
— Kyllä minä ymmärrän.
Kun he tanssivat nojatuolin ohi, sattui Lenin esiliina sitaisemaan
nukkuvan kissan korvaa. Se loukkaantui siitä, korva ei enää oiennut,
vaan jäi luppuun ja vihdoin kissa nousi, oikaisi selkäänsä ja hyppäsi
maahan, suuttuneena koko tästä uudenaikaisesta komennosta. Se
vain huvitti tanssivia. Lenin mieleen muistui ohimennen, kuinka
hirveästi hän kerran oli suuttunut Otolle, kun Otto oli sitonut kiven
saman kissan kaulaan ja kiusannut sitä rannassa. Mutta siitä oli
monta vuotta ja häntä kummastutti, että hän oli saattanut Otolle
suuttua. Nyt ei hän varmaankaan olisi voinut suuttua mistään! Otto-
herra olisi hänelle saanut tehdä mitä hyvänsä!
— Aijai, jatkoi hän hetken perästä, — kuinka minun tekisi mieli
niihin huomisiin tanssiaisiin! Armo sanoo, ettei kukaan viitsisi tanssia
kanssani, mutta tanssittehan tekin, Otto-herra, ettekö?
Siihen kysymykseen ei Otto todellakaan olisi voinut vastata, mutta
hän keksi äkkiä keinon ja virkkoi:
— Minäpä tiedän jotakin vielä hauskempaa. Jäädään tänne
Kankaanpäähän ja tanssitaan täällä!
Leni ilostui niin, ettei hän keksinyt mitään sanomista. Laine hänen
sisässään oli pulpahtamaisillaan yli laitainsa, kyynelet tuntuivat jo
silmissä.
— Niin me tehdään, jatkoi Otto varmemmin. — Mahtavatkohan täti
ja setä lähteä?
— Kyllä he ainakin aikovat. Mutta kuka meille soittaa?

53. — Emme tarvitse soittoa!
Heidän äänensä olivat alenemistaan alenneet, lopulta he puhuivat
kuiskaten ja vihdoin kokonaan vaikenivat, onnellisina päätöksestään.
Äkkiä lakkasi soitto ja Otto tunsi, että hänen täytyy päästää Leni
käsistään. Leni vei käden otsalleen, ikäänkuin häntä olisi
pyörryttänyt, hän ei taaskaan uskaltanut katsoa ylös ja unohti
kokonaan kiittää tanssitoveriaan. Kun hän sen huomasi, oli jo
myöhäistä ja hän riensi vain juoksujalan saliin kiittämään armoa.
Hänen olisi tehnyt mieli karata vanhan rouvan kaulaan, hänen siinä
istuessaan soittokoneen ääressä kuin unelmiin vaipuneena. Koko
maailma tuntui niin ihanalta, niin kaunis oli salikin. Sitä valaisi ainoa
kynttilä, paksussa hopeajalassa soittokoneen kannella, kasvit loivat
suuria varjoja valkeille seinille, joilla riippui perhekuvia,
maalaamattomalla permannolla juoksi valkoisia, siniraitaisia mattoja,
kattokruunun hiotut lasit välkkyivät taivaankaaren kaikissa väreissä.
— Kiitoksia, armo! kuiskasi Leni, ylen onnellisena, valmiina mihin
tahansa.
— Pidä hyvänäsi, lapsi, vastasi armo kummissaan ja hiukan
hämillään jalomielisen suostumuksensa odottamattoman suuresta
vaikutuksesta. — Toivottavasti sinä nyt käsität, että minä aina olen
ajatellut parastasi… No niin, no niin… Kiitä nyt vain herra von
Holtenia, sillä hänhän tämän oikeastaan pani alkuun.
Otto oli ruokasalin kynnyksellä ja Leni likeni häntä hiukan
keikaillen, mutta hyvin hämillään, sillä hän ei oikein tietänyt, pitikö
Otto-herralle nyt niiata vaiko vain kumartaa. Lopuksi hän sitten teki
ujon liikkeen, joka oli puoleksi niiaus, puoleksi kumarrus. Laine
hänen rinnassaan nousi suurena, lämpimänä, taivaan karvaisena.

54. Hän vaikutti Ottoonkin ikäänkuin hän olisi näkynyt sinertävän laineen
läpi. Hänessä oli jotakin niin utuista, kiehtovaa ja houkuttelevaa…
— Nostakaa nyt ruokasalin pöytä paikoilleen, kehoitti täti.
Pöytää nostaessa loivat he toisiinsa vielä katseen ja se katse puhui
paremmin kuin kaikki sanat. Sitten piti Lenin mennä toimittamaan
sisään teetä, patruuna tuli ruokasaliin ja ilta kului niin hauskasti,
ettei sellaista iltaa ollut koskaan ollut.
Otto jäi Kankaanpäähän yöksi. Hänellä oli siellä oma kulmakamari,
jossa hän jo ennenkin oli viettänyt monta yötä. Alhossa ei häntä
kaivattu, tiedettiin, ettei hän ollut hukassa.
Lenin silmiin ei tahtonut tulla unen hiventä. Hän lepäsi
liikkumattomana vuoteellaan ja sydän takoi särkyäkseen. Mielessään
kertasi hän jokaisen hänen sanansa, hänen liikkeensä ja katseensa.
Se ei ole unta, se on todella totta ja tapahtunutta! Hän on korotettu
sen sorjan pojan rinnalle niinkuin sadussa tuhkimus… Onko kukaan
kuolevainen niin onnellinen kuin hän?… Mutta kestääkö tätä, eikö
sittenkin päivä peity pilviin, ja hän herää näkemään, että se kaikki oli
unta, valo, joka syttyi juhlayönä ja katoaa juhlien kanssa!
Yö on tyyni ja pimeä, ikkuna on alhaalta vetäytynyt kuuraan. Hän
tuijottaa jäätähtiin ja tuntuu äkkiä siltä, kuin talviyöstä ojentuisi
koura tavoittelemaan hänen onneaan. Se on armo, hänen
emäntänsä, joka ei ikinä suostu hänen onneensa. Hän tulee, hän
tulee!… Ei, hän ei tahdo ajatella sitä, hän tahtoo vain muistella Otto-
herraa, jonka kanssa hän tanssi! Mutta jos hänkin laski leikkiä eikä
jääkään huomenillalla kotiin… Leni hypähtää istumaan, ojentaa
kätensä ikäänkuin pitääkseen kiinni jotakin ja purskahtaa itkuun…

55. Tuntuu niin oudolta tietää, että hän, hän, hän on täällä samassa
talossa! Oi kuinka peloittaa…
Ottokin on mennyt levolle epätavallisessa mielentilassa. Hänkään
ei saa ajatuksistaan, että se tyttö on täällä parin kolmen oven
takana, jotka ehkä eivät ole lukossakaan. Hän on yhä tuntevinaan,
että vaaleat hiussuortuvat hipaisevat hänen kasvojaan ja että tuossa
hänen silmäinsä alla on silmäluomi kalpean pehmeänä kuin
lumivuokon lehti, josta valuu alas sinertäviä suonia. Hänen
katseensa hipoaa alas silmäluomea, kaulaa, rintaa… Mikä siinä
tytössä onkaan, joka houkuttelee ja kiehtoo?
Hän nukkui pikemmin kuin Leni, mutta näki hullunkurisia unia,
joihin aina sekaantui Leni.
Kun hän aamulla ehdotti jäävänsä tanssiaisista pitääkseen seuraa
Lenille, purskahti täti suureen nauruun. Otto punastui korvia myöten
ja selitti tarpeettomalla kiihkolla, että hänellä tietysti olisi paljon
hauskempi tanssiaisissa. Hän vain ajatteli, koska se tyttö nyt on niin
huvinhaluinen…
— Jumala siunatkoon sinun hyvää sydäntäsi! sanoi täti. — Mutta
täytyyhän tytön oppia järkeä. Käsitäthän sinä, mitä huomiota se
herättäisi, jos kuultaisiin, että Otto von Holten istuu pitämässä
seuraa Kankaanpään talousmamsselille…
Talousmamsseli! Niin, sitä se eilinen tyttö oli. Jota hän oli pitkin
yötä ajatellut ja jonka kauneutta hän oli pitänyt niin hienona! Hän
muisti äkkiä, että sillä oli suuret, karkeat kädet ja mustuneet kynnet.
Se oli kuin olikin talousmamsseli! Hyi, jo häntä hävetti! Setä tuli vielä
lisäksi siihen ja rupesi tekemään hänestä pilaa.

56. — Sitähän voitaisiin selittää miten hyvänsä, sanoi täti. — Ei, rakas
Otto, tule sinä vain meidän kanssamme.
— Leikkiähän se oli, selitti Otto pontevasti ja rupesi kovasti
mielimään tupakkaa. Tähän saakka oli hän tupakoinut vain salaa,
mutta nyt hän äkkiarvaamatta aivan julkisesti ja ujostelematta kysyi
sedältä, saisiko hän mennä ottamaan sikaarin. Setä hymähti ja antoi
suostumuksensa, häntä huvitti nähdä, että poika alkaa miehistyä.
Senjälkeen ei Otto vahingossakaan puuttunut puheisiin Lenin
kanssa. Ja Leni tunsi, että koko sen illan onni on pyyhkäistävä pois
mielestä niinkuin uni päivän tullen. Mutta on unia, joita ei saa pois
päivälläkään, eikä Leni saanut tätä. Se kalvoi häntä ja kulutti kuin
tauti. Jota enemmän muuria hänen ja Oton välille korotettiin, sitä
kuumemmaksi hän kuumeni.
Kaiken talvea kutoi täti sukkia kummipojalleen. Hänen täytyi
heikkojen silmiensä takia käyttää vaaleita lankoja, mutta kun
silmikko putosi, niin täytyi Lenin tulla sitä nostamaan. Joskus kysyi
armo Lenin mielipidettä sukkien raidottamisestakin. Pari kertaa
lähetettiin Otolle laatikollinen leivoksia: pipari- ja sokerikakkuja,
roonia, kanelileipiä ja mantelikiehkuroita — kaikkea, mistä tiedettiin
Oton pitävän. Leni leipoi jokaiseen piparkakkusydämeen sydämensä
ikävät ja surut ja toivoi koko mielensä hartaudella, että Otto
nakerrellessaan leivoksia ehkä muistelisi häntäkin.
Mutta hänen sydämiään söi moni muukin kuin Ottoherra itse. Otto
kutsui luokseen joukon iloisia poikia ja Kankaanpään herkuilla oli
hyvä menekki. Päälle ryypättiin punssia. Pullot olivat kätketyt
piironginlaatikkoon ja juomalasista tai pullonsuusta otti jokainen
kulauksensa.

57. Samana keväänä piti Oton tulla ylioppilaaksi ja Kankaanpään
herrasväki oli jo kauan miettinyt, miten tätä merkkitapausta olisi
vietettävä. Vihdoin olivat he tulleet siihen johtopäätökseen, että he
tarjoavat Otolle Kankaanpään aivan polkuhinnasta. Hehän ovat
vanhoja ja kivulloisia ja vaikka pehtori olisikin kunnon mies, niin ei
hänen silmänsä ole samanarvoinen kuin isännän silmä. Eihän heillä
ole ketään likeisempää kuin Otto, hänhän on kuin heidän oma
poikansa. Jos he nyt Kankaanpäästään luopuvatkin, niin jäähän heille
vielä sittenkin tarpeeksi, ja jakakoot kaukaisemmat sukulaiset heidän
kuoltuaan sen keskenään.
Kankaanpäähän toimitettiin puusepät ja maalarit ja muutaman
viikon aikana kalkuteltiin aamusta iltaan vanhassa talossa. Kuinka
nuori ylioppilas tuleekaan ilostumaan, kun hän tapaa kaikki niin
uutena ja siistinä ja kun hän vielä lisäksi saa kuulla, että koko talo
tulee hänen omakseen! Vanhukset iloitsivat jo edeltäkäsin niin
sydämen pohjasta.
Leni pantiin kutomaan uusia mattoja hänen huoneensa lattialle.
Hän ryhtyi työhönsä kiihkeästi ikäänkuin sillä ravitakseen mielensä
nälkää ja päästäkseen Otto-herraa likemmä. Tavallaan se lohduttikin,
sillä syntyihän hänen käsissään vaate, jota hänen jalkansa tulisivat
koskettamaan. Oi, kuinka hän olisi suonut itse olevansa sen vaatteen
sijassa, saavansa lyyhistyä vaikkapa maan tasalle… Oi, kuinka hänen
oli ikävä, ikävä!
Tuli kirkkaita, keväisiä päiviä ja lumi suli hänen silmiensä alla,
mutta hän vain suri, ja heiluttellessaan sukkulaa, äänteli itsekseen
ikäväänsä.
Nähdessään kirjavat raidat täytyisi Oton muistaa kenen kamarissa
kangaspuut seisovat ja silloin täytyisi hänen ajatella tyttöä, joka

58. häntä rakastaa…
Puuseppien joukossa oli muuan Kalle-niminen mies, joka tuon
tuostakin puhutteli Leniä, kun sattui hänet näkemään. Milloin hän
huomautti, että on kaunis ilma, milloin sanoi ilmaa rumaksi. Se oli
harteva, rehellisen näköinen mies. Leni huomasi hänet sivumennen.
Mutta eräänä sunnuntaina sattuivat he yhteen, molemmat matkalla
kirkkoon. Heille tuli puolen virstan pituinen yhteinen matka ja kun
Lenin päähän äkkiä muistui asia, jossa ehkä tästä miehestä saattaisi
olla apua, puhutteli hän miestä.
— Tehän olette kirvesmies, virkkoi hän. — Ettekö tekisi minulle
kukkatelineitä? Kukkani seisovat liian matalalla. Aurinko ei ylety
niihin.
— Se on paha, ettei aurinko ylety, vastasi mies huolestuneesti,
ikäänkuin olisi ollut kysymys ihmishengestä, joka ei tule toimeen
ilman aurinkoa. Ja samalla katsahti hän arasti ja ihaillen mamsseliin.
Lenissä heräsi halu olla ystävällinen tuolle miehelle. Hän ei ollut
ruma, kyllä hiukan kömpelö, mutta aika hauskan näköinen.
— Oletteko ennen tehnyt kukkatelineitä? kysyi hän ja hänen
silmänsä loistivat lempeästi. — Vai ettekö? No, mitä te olette tehnyt?
— Rakennustöissähän minä enimmäkseen, ja sitten veistellyt
kaikenlaisia, tuoleja ja pöytiä ja ruumiskirstuja ja…
— Ruumiskirstuja! keskeytti Leni ja silmien suuri terä vetäytyi
pelästyneeksi ja ikäänkuin musteni. Ja se pysyi yhä mustana, vaikka
suu jo hymyili, kun hän jatkoi: — Joko te nyt noin nuorena rupeatte
tekemään kuolleille majoja. Ihan minua peloittaa!

59. Nyt hymähti tuo vakava mieskin ja kävi oikein miellyttävän
näköiseksi.
Hänellä oli niin suuret siniset silmät.
— Kuollahan meidän kaikkien pitää!
— Kunhan eivät kukkani kuolisi, kun joutuvat telineittenne päälle!
He nauroivat molemmat ja juttelivat lopputien oikein iloisesti ja
tutunomaisesti. Kirkon ovesta he vielä astuivat yhdessä, mutta sitten
erkani Leni naisten penkkeihin, nuorukainen miesten puolelle.
Parin päivän perästä tuli Kalle ruokatunnillaan tuomaan telineitä.
Ne olivat kauniisti kirjaillut, ja kun Leni kysyi, mitä hän on velkaa,
niin vastasi mies ettei mitään. Ja oikein hän loukkaantui, kun Leni
vain olisi tahtonut maksaa.
Samana päivänä, jolloin korjaustyöt kartanossa loppuivat, läksi
Leni kävelemään. Oli lämmin, valoisa ilta. Hiirenkorvat puhkeilivat ja
lintuja ilakoi joka oksalla. Hän kokoili vuokkoja ja kissankäpäliä tien
vierestä ja kulki kaihoihinsa vaipuneena. Otto-herran tulo likeni
likenemistään.
Äkkiä huomasi hän miehen seisovan keskellä tietä, kädessään
koppa, jossa oli höylä ja muita työkaluja. Mies asetti kopan
pientareelle ja läheni Leniä hitain askelin, katse maahan luotuna.
Ensin Leni kavahti, mutta huomasi samassa, että sehän on se
puuseppä.
Mies tervehti ja pysähtyi, mutta ei pitkään aikaan virkkanut
sanaakaan.
Leni järjesteli kukkasiaan.

60. — Mikä teidän on? kysyi hän vihdoin. — Näytätte niin surulliselta.
— Minä vähän puhuisin mamsselille, kun ette suuttuisi.
— Mitä minä suuttuisin!
— Ehkä siksi, että olette mamsseli ja minä vain talonpoika.
— Puhukaa nyt vain! kehoitti Leni hiukan levottomana.
— Eihän sellaisia pitäisi puhua kuin vertaisilleen.
Hän jäi taas pitkäksi aikaa ääneti katsomaan eteensä ja
hypistelemään petäjän kylkeä suurella kourallaan. Leni seurasi hänen
temppujaan hämmästyneenä. Koko hänen silmänsä oli ainoana
suuren teränä, josta milloin loisti levottomuus, milloin veitikkamainen
huudahdus: mitä sinä, hyvä mies, nyt oikein tahdot? Nuori puuseppä
ei sitä huomannut, hän oli hyvin tosissaan.
— Minä pyytäisin, pääsi häneltä vihdoin, — että mamsseli tulisi
minun vaimokseni.
Leni oli purskahtamaisillaan nauruun, mutta pidättyi. Vai sitä se
oli!
Oli hän ehkä sitä hiukan pelännyt.
— Mutta ettehän te ensinkään tunne minua, sanoi hän vihdoin
jotakin sanoakseen.
— Jaa minäkö? Ei mamsseli tiedä, kuinka kauan minä olen teidän
mutkiinne katsellut! Rippikouluakin käytiin yhteen aikaan, vaikka
mamsseli kävi yksityisesti rovastin edessä. Ja kun
juhannusaattopäivänä herrasväki kaikki oli kirkkoa koristamassa, olin

61. minä kantamassa koivuja. Minä muistan mamsselin puvunkin ihan
niinkuin tämänpäiväisen aamiaisen, muistan senkin, kun herrasväki
sunnuntaina tuli kirkkoon ja mamsseli istui vaunuissa vastapäätä
armoa ja patruunaa… Sitten kun suomalainen rippi jo oli ollut, jäin
minä vielä kirkkoon ruotsalaiseen. Mamsseli niin itki, kun astuitte
alttarille…
Leniä liikutti kuunnella miehen kömpelöjä sanoja. Vai oli siis ollut
ihminen, joka kaikkina näinä vuosina oli kantanut häntä mielessään,
kärsinyt, kuten hän itse Otto-herran takia! Se tuntui hyvältä, eikä
Lenillä ollut sydäntä sanoa, ettei hän ollut nuorukaista edes
huomannut.
— Taidan minäkin nyt muistaa teidät, puhui hän. — Mutta en minä
tätä olisi odottanut!
— Mistäs mamsseli sitä. Ja enhän minä nyt heti tahdo vastausta.
Lähden tästä matkalle. Jos sitten tulooni asti olisitte ehtinyt ajatella.
Tai jos niinkuin aikaisemmin olisitte päättänyt, niin voisitte vain
sanoa sisarelleni, joka on sen suutarin vaimona siellä punaisessa
mökissä hautausmaan takana…
— Punaisessa mökissä hautausmaan takana, toisti Leni kuin
unissaan, varmana siitä, ettei ikinä mene sitä sanaa viemään.
Mies puhui hänelle vielä pitkältä, puhui tyynellä äänellään, josta
mielenliikutus, toivo ja epätoivo värähteli. Leni katseli häneen
vilkkumatta, nyökäytti tuon tuostakin päätään tai hymyili, mutta ei
hän kuunnellut miehen sanoja. Hänen ajatuksensa olivat ihan
epämääräiset ja tietämättään kylvi hän toivoa nuoren miehen
rintaan. Hyvästi jättäessä painoi hän silmänsä maahan, häneen
koski, hänen kävi sääli.

62. Niin he erosivat. Leni luuli nähneensä hänet viimeisen kerran eikä
häntä sen enempää ajatellut.
* * * * *
Otto-herra ei läpäissyt ylioppilastutkinnossa. Sitä mahdollisuutta ei
kukaan ollut tullut ajatelleeksi ja se pani mielet kuohuksiin.
Patruuna suuttui.
— Pojalta ei puutu päätä, torui hän, — mutta se on laiska. Ei se
nyt
Kankaanpäätä saa, minä vain en sille Kankaanpäätä anna!
— Mutta, yritti armo välittää, — jos hänelle nyt todella on tehty
väärin. Tiedämmehän, miten persoonallisia opettajat voivat olla…
— Mitä syytä kenelläkään olisi häntä vainota. Se lurjus luulee
voivansa meidän vanhojen päähän ajaa mitä palttua hyvänsä, mutta
hän erehtyy. Minun silmäni ovat jo auenneet, minä en enää sokeasti
usko häneen… Ja kirjeessä sitten ilmoittaa kaiken tämän. Olisi vain
saanut tulla itse puhumaan… Ruotsiin, Ruotsiin sitä sitten lähdetään
niinkuin karkulaiset ainakin.
— No mutta etkö ymmärrä, ettei hän uskalla tulla kotiin?
— Se on kurjaa, se on raukkamaista! Mutta millähän rahoilla hän
aikoo Ruotsiin lähteä? Olisi hauska tietää. Veli hänelle ei lähetä
rahoja, eikä hän niitä pyydä minulta.
— Mutta Erik, rivien välistä kyllä lukee pyynnön…

63. — En tahdo lukea mitään rivien välistä. Tulkoon suullisesti
puhumaan tai kirjoittakoon edes suoraan. Rivien välistä lukekoot
rakastuneet, ei se ole miesten kieltä. Ja miestä minä olen hänestä
toivonut, mutta…
Vanhukset elivät siinä luulossa, että Otto sentään pian tulee kotiin,
sillä millä hän Ruotsiin pääsee, kun he eivät ole lähettäneet hänelle
rahaa. Mutta he suuresti erehtyivät, sillä kuinka ei Otto von Holten,
jonka vuoden päästä piti tulla suurten omaisuuksien omistajaksi, olisi
saanut irti rahaa miten paljon hyvänsä!
Hän läksi kuin läksikin Ruotsiin, tutustui sukulaisiinsa, piti hauskaa
ja ilmoitti syksyllä Kankaanpäähän, että hän on päättänyt ruveta
maanviljelijäksi. Hän seuraa täällä suurten kartanoiden
maanviljelystä ja karjanhoitoa ja menee sitten maanviljelysopistoon.
— Näetkö nyt, riemuitsi rouva Liljefelt kyynelsilmin, — kuinka
väärin häntä tuomitsit. Hän on sittenkin se, jota hänestä toivomme.
Voi, miten väärin teimme hänelle!
— No niin, myönsi patruuna kaikin puolin hyvillään. — Mutta olisi
hän silti voinut tulla ylioppilaaksikin.
Leni suri häntä kuin kuollutta, voimatta häntä unohtaa.
Kului vuosi. Oli syksy.
Vanhat herrasväet olivat lähteneet häihin naapuripitäjään.
Syyshallat olivat jo alkaneet ja kukkalavat olivat yöksi peitetyt
niinimatoilla ja havuilla. Aamulla oli Leni lähtenyt puutarhaan
ottamaan pois peitteitä. Nurmi oli paksussa, hopeankarvaisessa
kasteessa, teillä oli keltaisia lehtiä, tuuli alkoi herätä liikuttelemaan

64. niitä. Päivä paistoi lämpöisesti ja kaikki kukat olivat säilyneet hallalta.
Hän pisti resedanoksan napinläpeensä ja alkoi taitella astereita
vaaseihin.
Äkkiä kuuli hän koiran haukuntaa ja rattaitten jyrinää pihasta,
mutta ei malttanut lähteä katsomaan. Hetkisen perästä hän sentään
kävi uteliaaksi, oikaisihe suoraksi ja alkoi kuulostella, kasvot
kääntyneinä päärakennuksen pitkään ikkunariviin.
Salin keskimmäisen ikkunan uudinta työnnettiin syrjään ja ruudun
taakse ilmaantuivat kasvot… Lenin sydän tuntui seisahtuvan ja koko
ruumis kangistui, sillä hän luuli näkevänsä näyn: Otto-herran kasvot!
Hän ei voinut liikkua paikalta, hän ei voinut ajatella sinne eikä
tänne… Hetkisen perästä Otto-herra ilmielävänä kiersi rakennuksen
nurkan ja lähestyi käytävää pitkin. Silloin karkasi veri Lenin poskille
ja sydän alkoi sykkiä.
Otto-herra oli hienossa, kellertävän harmaassa puvussa, punainen
kravatti kaulassa, päässä leveäreunainen, ruskea huopahattu. Hän oli
kookas ja solakka, hiukset pikimustat ja lyhyiksi leikatut, parta
suippeni leuan alle ja viiksien päät nousivat somasti pystyyn. Hänen
silmissään oli sama epämääräisen ruskehtava väri kuin ennenkin.
Muuten hän oli kovasti kaunistunut, miehistynyt ja… ja käynyt niin
ulkomaalaisen näköiseksi.
Hän nosti hattuaan ja oli ojentamaisillaan kätensä, mutta kun
huomasi Lenin käden multaiseksi, niin ei ojentanutkaan, vaan rupesi
paikalla puhumaan. Puhui virallisella, vakavalla äänellä kuin herra
palvelijalle ja kasvot olivat jääkylmät. Hänen äänensä kuullessaan
kävi Leni kalpeaksi, tuntui siltä kuin viimeisetkin toiveet olisivat
särkyneet. Tyynesti ja virallisesti vastasi hän herran kysymyksiin,
kertoi, missä herrasväet olivat, ilmoitti Alhon herrasväkienkin olevan

65. samoissa häissä ja kehoitti lähtemään perässä. Varmaan vielä ehtisi,
hevosia oli kyllä joutilaina talossa… Herra sanoi olevansa väsyksissä
ja pyysi laittamaan aamiaista.
Kuinka Leni olisikin suonut hänen lähtevän pois! Tuolle hänellä ei
ollut mitään asiaa. Häntäkö hän oli itkenyt ja ikävöinyt? Mahdotonta,
sillä tuohan on ventovieras mies… Jospa olisikin eikä kantaisi Otto-
herran kasvoja ja puhuisi hänen äänellään!… oi, kun ei hän ikinä olisi
palannut, että olisi saanut itkeä ja ikävöidä eheästi!… Lenistä tuntui
entistä tyhjemmältä ja kolkommalta. Hän ei koko päivänä mennyt
vieraan näkyviin, vaan lähetti palvelustytön tarjoamaan ruokia.
Sentään hän ei voinut estää silmiään seuraamasta vierasta, kun
tämä liikkui ulkona, eikä korviaan kuuntelemasta hänen askeleitaan
ja ääntään. Kerran oli hän jo hiipimäisillään oven taakse
kuuntelemaan, nukkuiko Otto-herra, mutta pelästyi omaa ajatustaan
ja päätti entistä itsepintaisemmin pysyä hänestä, vieraasta miehestä,
loitolla.
Mutta jota illemmaksi päivä painui, sitä levottomammaksi,
raskaammaksi kävi hänen olonsa. Hänen oli niin kalvavan ikävä.
Kunhan edes olisi ollut joku, jonka kaulaan olisi saanut heittäytyä
itkemään. Mutta ei ollut ketään, piti vain painamistaan painaa
kyynelvirtaa alas kurkkuun, ettei se pääsisi puhkeamaan
nyyhkytykseksi.
Tuuli tyyntyi ja kuu nousi kirkkaana puoliskona taivaalle. Taivas oli
syvän sininen ja kuulakka. Järvi oli liikkumaton ja kuollut, korkeat,
kellastuneet rannat heijastuivat sen kalvoon kuin lasiin.
Lenin pitää taasen peittää lavat, sillä yöllä varmaan tulee halla.

66. Ah, kuinka hänen sielunsa isoo ja huulet janoavat! Sydän on
täynnä kuin puu mahlajan aikana. Hän kuulee sen takovan, kuulee
omat askelensa hiekkakäytävällä. Hänen ympärillään kohoavat
satavuotiset puut, niiden varjoja juoksee hopeankarvaisella nurmella
ja yli hiekkakäytävien, jotka kuunvalossa ovat kaamean näköiset kuin
matalapohjaiset joet…
Nurmi on vahvassa kasteessa. Resedat ja hajuherneet lemuavat.
Joku ajelee maantiellä ja Alhon koira haukkuu. Läheltä ei erota
muuta kuin hänen omat puuhansa, kun hän liikuttelee niinimattoja.
Sitä mitä hän odottaa, sitä ei kuulu… Onko hän todella jo nukkunut,
eikö kuunvalokaan houkuttele häntä puutarhaan? Hän on matkasta
väsynyt, Jumalan kiitos! Ei, ei, ei Leni tahdo häntä nähdä!
Ja ikäänkuin kiusausta peläten hän kiiruhtaa peitteitten
levittämistä ja päättää lähteä sisään. Mutta hän ei lähde. Hän painuu
syvemmälle puutarhaan.
Hän halajaisi syleillä näitä puita, koskettaa niitä huulillaan… Kuinka
ne kohisevat kummallisesti! Peloittaa… Hän tahtoisi heittäytyä
tuohon käytävälle, tuohon valkeaan hiekkavirtaan, jäädä siihen ja
siihen kuolla… Nyt kuuluu askeleita läheltä, ovi käy, hiekka
narahtelee: se on hän, joka tulee…
Mitä tehdä? Paetako vai rientää vastaan? Hän pelkää ja iloitsee
eikä tiedä mitä tehdä… Jää paikoilleen nojautuneena puunkylkeen ja
päättää olla ihan hiljaa, hengittämättäkin, käyköön sitten miten
hyvänsä: jollei hän huomaa, niin merkitsee se, että kaikki on
lopussa; jos huomaa, niin se on sillä lailla sallittu…
Sallittu, sallittu…

67. Tyttö seisoo siinä silmät kiinni kuin elämäntuomiotaan odotellen.
Askelet likenevät suoraan häntä. Pyörryttää. Täytyy pitää kiinni
puusta, käyköön sitten kuinka tahansa!
Hänen ympärilleen kietoutuu käsivarsi ja kasvojen päällitse käy
kuuma henkäys. Tahdotonna, rentona raukeaa hän syliin, joka käärii
hänet kuin lämpöiseen aaltoon.
— Leni, kuiskaa ääni, se ikävöity, kaivattu ääni, — ethän vielä
kokonaan ole minua unohtanut? Muistathan vielä meidän
tanssimme!
Hän suutelee ja painaa itseään vasten. Hänen kätensä soluu pitkin
kaulaa ja niskaa ja pysähtyy pusertamaan rintaa…
Leni pelästyy ja avaa silmänsä. Silloin näkee hän vastassaan
hirveät, nälkäiset kasvot… Hyvä Jumala, nyt täytyy paeta, nyt täytyy
riistäytyä irti…
— Miksi vapiset, tyttö? kuiskaa ääni korvan juuressa ja taas käy
henkäys yli Lenin kasvojen. — Etkö minua rakastakaan?
Leni pääsee hetkeksi irti, vain hänen kättänsä pitelee vielä kuuma
käsi.
— Etkö rakasta? Vastaa!
Eikö hän rakastaisi, hän, joka kaikkina näinä vuosina on kärsinyt ja
kitunut rakkaudessaan? Eikö hän saisi tunnettaan tunnustaa? Hän
tahtoo sen julkilausua, huutaa sen ilmoille koko sielullaan ja
mielellään.

68. — Rakastan, virkkaa hän. — Minä luulin, että olitte minut
unohtanut, voi miten kärsin!
— Älä itke, kulta!
— Miksi te olitte niin kylmä, kun tulitte?
— Tahdoin tutkia olitko muuttunut.
— Mutta mitä ihmiset, mitä armo ja patruuna sanovat…? kuiskaa
Leni kiihkeästi ja koettaa riistäytyä irti.
— Emme ajattele heitä. Sanokoot mitä hyvänsä.
— Voi minua, voi minua!
Otto kietoo käsivarret hänen ympärilleen ja pusertuu häntä ihan
likelle. He astuvat alas käytävää vierekkäin kuin olisivat yksi ihminen.
Puut suhisevat hiljaa, kuu loistaa, koko maailma nukkuu.
Leniä alkaa värisyttää, hän kulkee kuin pyörryksissä. Se toinen on
hehkuva ja kuuma ja vie yhä eteenpäin, kohti vettä. Laiturin kyljessä
on valkoinen vene, joka kertautuu järven kalvoon. Siellä näkyy syvä
taivaskin ja kuu…
Äkkiä he erkanevat tiestä, eivät astukaan veneelle, vaan metsään,
suurten puitten alle…
Lenille tulee hätä. Hän aavistaa jotakin hirmuista ja rumaa. Pois,
pois tästä kauhistuksen paikasta! Mutta hän ei enää pääse. Hän
voihkii, hän itkee ja rukoilee… Koira kartanolla alkaa haukkua. Hän
kuulee sen kuin hukkuva pelastuksen huudon rannalta ja vaipuu
samassa veden alle, kadottaa tahtonsa ja tajuntansa…

69. III
Pelonsekaisen jännittyneenä ja epäluuloisena Liena kohtaa jokaisen
vieraan, sillä voihan se tuoda tietoja kirkonkylästä. Hän pelkää
Kalleakin, kun Kalle palaa kirkkoretkiltään.
Tavallisesti ovat uutiset pikkuasioita, joita ei laisinkaan olisi
kannattanut pelätä: Kankaanpään herrasväki on ollut sairaana; joku
palvelijoista on mennyt naimisiin ja kartanossa on pidetty häät. Tuuli
on kaatanut suuren puun puutarhasta. Alhon rouvalla on taas pieni,
niitä syntyy siellä yhtä tiheään kuin täällä Pimeässäpirtissä… Alhon
patruunasta on aina paljon uutisia. Se syöttää väelleen silakoita,
jotka ovat viiden vuoden vanhoja, ja juottaa armollaan ruiskahvia.
Palvelijat vaihtuvat siltä ihan joka kuukausi, kuka sillä rupeaisi
olemaan, joka ei anna työtäkään työmiehilleen! Kankaanpään armo
on tavallisesti pannut Kallen mukaan tuomisia lapsille. Siellä on
hiivaleipää ja vehnäkorppuja, joskus koreapaperinen konvehti tai
orehtia. Lapset mainitsevatkin armoa sadun hyvänä haltiana, joka
hyville lapsille aina lähettää tuliaisia, ja odottavat isää kotiin
malttamattomina. Kun hän vihdoin on päässyt pirttiin, käy hänen
ympärillään kihinä ja kähinä. Kukaan ei ehdi huomata Lienan
levottomuutta.

70. — Nyt se tulee, nyt se tulee! ajattelee hän ja sydän takoo
kuuluvasti. Mutta tavallisesti ei tule mitään vaarallista. Hän
rauhoittuu, lakkaa pelkäämästä ja kuvittelee vaaran jo ainiaaksi
menneen. Silloin saattaa joku yht'äkkiä, hitaalla, rauhallisella äänellä
mainita Otto-herran nimeä.
Kuuluu yhä olevan siellä Ruotsissa, vai missä kaukana lieneekään.
Oli kirjoittanut itsellään olevan morsiamen ja lähettänyt sen kuvan.
Ja se oli ollut paljain kauloin ja käsivarsin ja niin hepenissä, että ihan
kuin keisarillisten kuvat. Hyvin rikkaan sanovat olevan ja Otto-herra
kuuluu jäävän sinne sen suurille kartanoille kotivävyksi.
— Jumalan kiitos! Jumalan kiitos! ajattelee Liena ja hänen
rinnassaan tuntuu helpommalta. Kunhan jäisikin!
Mutta jonkin ajan perästä tuo huhu sydänmaille tiedon, että hän
on käymässä kotona, on yksin. Ne naimakaupat ovatkin puretut.
Iloisena miehenä liikkuu pitäjällä, käy kesteissä ja metsästysmailla…
Talveksi painuu taas pois Suomesta eikä sinä kesänäkään palaa.
Mutta seuraavana kuuluu Pimeäänpirttiin viesti, että sillä taas on
morsian, ovat jo kuulutuksissa ja häät vietetään ennen juhannusta.
Se tuo nuoren armonsa Suomeen ja kuuluvat asettuvan
Kankaanpäähän asumaan. Vanhat lahjoittavat sen kummipojalleen.
Siellä onkin nyt kova puuha, huoneita maalataan ja paperoidaan,
työmiehiä on tuotettu Helsingistä asti.
Tämän tiedon tuo mies, joka tulee suoraan pappilasta ruumista
kirjoituttamasta. Koko pitäjähän nämä asiat tietää, ihme, ettei
tiedetä Pimeässäpirtissä… No, on tässä juuri ollut kelirikon ajat, eikä
ole satuttu missään käymään.

71. Miehen mentyä jää torppaan kolkko hiljaisuus. Vaari ja Kalle
istuvat kukin penkillään eteensä tuijottaen. Liena askaroitsee lieden
ääressä, selin heihin. Hanni liikkuu puna poskilla, silmissä kysyvä,
kummastunut ilme. Hän ei käsitä, mitä suremista siinä on, että nuori
patruuna viettää häitä ja muuttaa Kankaanpäähän. Hänen silmissään
se kaikki on kuin kaunista satua, komeat häät, nuori armo
silkkivaatteissa… Mutta isä ja vaari ovat kuin kivettyneet ja äiti vallan
vapisee, mahtaa siis olla jotakin hirveää tulossa. Lapsetkin,
karatessaan tupaan leikeistään, tuntevat ilman painostavuuden ja
pysähtyvät ikäänkuin olisivat iskeneet päänsä seinään.
— Jo taisi tulla muutto tästä paikasta, virkkaa vaari vihdoin.
— Ei sitä niinkään tee mieli muuttaa paikasta, jonka alastomaan
korpeen rakensit, vastaa Kalle siihen hämmästyttävän kiivaasti. —
Sinun on, Liena, lähdettävä kirkonkylään vanhan herrasväen
puheille. Kyllä se patruuna antaa sellaisen kontrahdin, että
kohtuullista veroa vastaan saadaan olla tässä rauhassa.
— Mihinkäs minä tästä pääsen! vastaa Liena ja hänen äänensä
värisee.
— Paras, että aletaan etsiä toista torppaa.
— Vai toista! kiivastuu Kalle. — Vai toista! Eikä aletakaan…
Kummoinen lienee tämä Otto-herra? Ehkä on parempi kuin Alhon
patruuna.
Eivät ole aina samaa maata samojen vanhempien lapset.
— Sama se susien luonto aina on, ärähtää vaari.
— Sano nyt sinä, Liena, kehoittaa Kalle tyynemmin, — mitä sinä
luulet, sinähän tämän Otto-pojan olet nähnyt lapsena.

72. Veri tyrkkäytyy Lienan kasvoille, hän painuu puhaltamaan
pataansa ja vastaa sieltä:
— Paljonkos minä sitä näin. Koulussahan se aina oli… Kerran
heristeli kepillä kerjäläisiä kyökistä, kerran sitoi kiven armon vanhan
kissan kaulaan ja kiusasi sitä järvessä. Ja ainahan se taas ajoi
hevoset niin pahasti, ettei niistä sitten enää ollut mihinkään. Ei taida
vain senkään luonnossa olla kehumista.
— Johan minä sanoin, ärähtää vaari, — että sudet on susia ja
Holtit on Holtteja. Jo tästä muutto tuli, jos vain Holtit haltijoiksi
joutui.
— Jaa, jaa, vai muutto! puhelee Kalle ja katselee kummissaan
isäänsä. — Vai pitäisikö minun lähteä toista korpea rakentamaan ja
jättää tämä mustalaisten kortteeriksi! Hyvä teidän on sanoa, mutta
kuka minut tänne korpeen käski, kuka?
Kallen jokainen sana vihloo Lienan mieltä kuin veitsi. Oi, voi, kun
saisikin sen lepytetyksi! Jäähän hän tännekin, eihän hän tahdo pois…
Kalle ei suutu paljon koskaan ja nyt hän on oikein kiukuissaan. Oi,
voi, kun kulkee noin levottomana pitkin pihaa, katselee rakennuksia
kuin varas. Niin, kaikki ne ovat sen rakentamia, ei ole ihme, ettei tee
mieli heittää vieraille…
Äkkiä Kalle astuu sisään ja seisahtuu vaimonsa eteen.
— Sinäkö lähdet vai minä? kysyy hän tiukasti.
Liena ei uskalla katsoa häntä silmiin eikä hän tiedä mitä vastaisi.
Hän vapisee niin, ettei kauha tahdo pysyä käsissä.

73. — Ehkä sinä sittenkin toimitat asiat paremmin, jos itse menet,
vastaa hän vihdoin hiljaa.
Sanaa sanomatta Kalle menee ulos, valjastaa hevosen, sitoo sen
aitaan ja lähtee aittaan muuttamaan vaatteita.
— Ethän ilman päivällistä lähde? kysyy Liena arasti.
Kalle tulee tupaan, haukkaisee kiireesti eikä puhu sanaakaan.
Liena valmistaa eväskontin hänen viereensä pöydänkulmalle.
Hetken perästä kolisevat rattaat kivisellä kujalla ja Liena huomaa
eväskontin unohtuneen tupaan… Vai tahallaanko heitti? Oliko tosiaan
niin vihoissaan?… Hän koppaisee sen pöydältä ja lähtee juoksemaan
perässä lapset kintereillä. Heistä on hauskaa juosta kilpaa äidin
kanssa ja he huutavat ja ilakoivat. Puna poskilla Liena saa kiinni
Kallen. Liena ojentaa hänelle unohtuneen kontin ja katsoo häneen
rukoilevasti. Kalle ei sano mitään, mutta Liena huomaa pahimman
puuskan jo menneen ohi, sillä lapsillehan hän jo hymyilee.
Hän katoaa metsään, mutta kauan kuuluu vielä rattaitten kolina
kivisellä tiellä. Liena kuuntelee sitä pihaportilla ja hänen on paha
olla. Hän on loukannut Kallea, ei olisi pitänyt kehoittaa muuttamaan
Pimeästäpirtistä. Eihän hän sitä ilokseen tehnyt, tulisihan hänenkin
ikävä tätä korpea… Mutta asua Otto-herran maalla, olla riippuvaisena
hänen armostaan, joutua ehkä näkemään häntä. Yhä vielä kuuluu
tieltä rattaiden röyke. Kalle-raukka!
Toiset lapset leikkivät jo iloisesti pihassa, mutta pikku Hanni istuu
miettiväisenä tuvassa kehdon ääressä. Hän kääntää äitiin syvät,
mustansiniset silmänsä, jotka ovat kuin vanhalla ihmisellä, ja kysyy
hiljaa ja varovaisesti:

74. — Mamma, mitä on tapahtunut?
Äiti koettaa selittää asiat niin luonnollisesti, yksinkertaisesti ja
välinpitämättömästi kuin suinkin, mutta Hanni kyllä huomaa, että
siihen jää jotakin, jota ei sanota hänelle, ja hänen silmänsä pysyvät
kaiken päivää syvinä ja surullisena niinkuin kehittyneellä ihmisellä,
joka miettii elämän ongelmoita.
Kallea ei kuulu kotiin seuraavana päivänä. Vasta illallahan Liena
häntä oikeastaan odottaakin. Vaari lämmittää saunan ja keitto seisoo
yöhön asti hiilloksessa. Mutta Kallea ei kuulu.
Liena käy levottomaksi. Jos jotakin on tapahtunut, jos on sattunut
sairastumaan. Vaari vastaa siihen kiukkuisesti, että mitä turhia,
mutta Liena huomaa hänenkin seisoskelevan veräjällä
kuulostamassa, eivätkö kivet tiellä jo kolise… Entä jollei Kalle
palaakaan, jos hän matkalla on saanut tietää…
— Hyvä Jumala, ole minulle armollinen, vaikeroi Liena itsekseen,
rintojaan pidellen. — Mitäpä jos astuisi Kallen eteen ja paljastaisi
kaikki! Sitten ei enää olisi tätä ainaista pelkoa. Kalle varmaan antaisi
anteeksi. Mutta jollei antaisi? Vaari voisi suuttua niin, että surmaisi.
Ja Hannin, viattoman lapsen he hylkäisivät ja työntäisivät maantielle
ihmisten jalkoihin…
Hanni kyllä tietää, että äiti on huolissaan. Hän koettaa olla niin
kiltti, hän täyttää äidin toivomukset jo ennen kuin äiti on ne
lausunutkaan. Illalla hän tekeytyy pieneksi lapseksi, kapuaa äidin
polville, kietoo kädet kaulaan ja pusertaa vastaansa.
— Mamma, oma hyvä mamma! Sinulla on niin kauniit silmät,
Hanni rakastaa sinua, älä itke!

75. Hän hymyilee syvine silmineen, joitten kiilto on kostea kuin
lähteen kalvon, heittäytyy taapäin, keikauttaa päätään ja katselee
veitikkamaisesti ja kiehtovasti. Jo alkaa puhua ruotsia.
— Mamma, älä itke! Isä on niin väkevä, kuka hänelle uskaltaisi
mitään tehdä. Kyllä isä tulee takaisin… Mamma, rakastathan sinä
Hannia?
Äiti ei vastaa, painaa vain Hannia syliinsä, huojuttelee häntä siinä
hiljaa ja kyynelet valuvat alas poskia. He istuvat kuistin portailla.
Ilta on lämmin ja vasta-auenneet koivut lemuavat. Niiden kukkeita
latvoja kohoilee pitkin rantoja, siellä täällä hennon vihannan keskellä
ylenee mänty tai kuusi. Järven tyynessä näkyy syvä taivas ja lahden
suussa lepää pienoinen saari koivuineen, jotka ojentuvat vettä kohti,
ikäänkuin heittäytyäkseen sen syliin. Herkkinä vaeltelevat pilvet
taivaalla, niiden värit vaihtelevat lakkaamatta. Käki kukkuu saarelta,
toinen vastaa rannalta, kolmas ja neljäs kukahtelevat koivusta kaivon
vierellä. Koiranputket pihamaalla ovat sysänneet meheviä lehtiä ja
nuppupäisiä runkoja. Nokkosten päät ovat vielä punertavat, ilma on
täynnä pieniä, keveitä hyönteisiä ja kevään lemua.
Vaikea, vaikea täältä olisi lähteä, hyvä täällä on ollut. Paljon syntiä
tuntee Liena tehneensä miestään ja sydänmaata kohtaan, kun on
valittanut kohtaloaan. Kun saisikin takaisin Kallen ja entiset hyvät
ajat, niin ei ikinä toivoisi muuta…
Otto-herra tulee Kankaanpäähän nuoren armonsa kanssa, hän
asettuu asumaan niihin huoneisiin, yhdessä he tulevat käyskelemään
siinä puistossa… Ei, ei, pois ne ajatukset, hän ei tahdo ajatella
mitään, ei muistaa mitään!… Hän huutaa Hannin nimeä ja tarttuu
hänen käsivarteensa.

76. — Lapseni, on jo yö, mennään levolle!
Hanni säpsähtää unenhorroksista ja katselee kummastuneena
äitiin.
Kolmantena päivänä palasi Kalle erinomaisella tuulella. Hänelle oli
sattunut sellainen onni, että oli joutunut Kankaanpäähän juuri
nuoren herrasväen tuliaiskesteihin.
Sitä iloa ja riemua! Kun siinä, missä Kankaanpään maat alkavat, oli
ollut vastassa mahdottoman iso kunniaportti ja lippuja riukujen
nenässä ja kirjoituksia, joitten sanottiin merkitsevän "tervetuloa". Ja
tällaisia portteja oli ollut useampia ja päärakennuksen ovipieleen oli
kiedottu jos minkälaisia köynnöksiä ja laitoksia ja portaille oli
levitetty hieno tulipunainen villamatto. Piiat ja rengit olivat
pyhävaatteissaan ja pehtori kävi neuvomassa, että kun nuori
patruuna ja hänen armonsa astuvat vaunuista, niin pitää huutaa
"hurraa". Sattui sitten vielä sellainen korea päivänpaiste ja pihlajat
aukaisivat juuri kukkiaan ja komean näköistä oli, kun vaunut
tomupilven keskellä ilmestyivät tienkäänteestä. Hevosten valjaat
välkkyivät hopealta, vaahdossa olivat lautaset ja nuorten pään päällä
armo piteli punertavaa päivänvarjoa. Hän oli ihkasen silkkisessä
puvussa, hatussa kukkia ja töyhtöjä ja kun hän astui alas vaunusta,
niin näkyi suippokärkinen kenkä ja alushame, joka oli paljaista
pitseistä ja silkkisistä nauhoista. Siinä samassa jyräyttivät jyvämiehet
ja rengit ja piiat hurraa-huudon. Armo kääntyi, nyökäytti päätään ja
suu oli makeassa naurussa… Sillä on mustat hiukset kuin kuuman
maan ihmisillä, kasvoja ja silmiä ei oikein voinut erottaa kaikilta niiltä
harsoilta ja hepeniltä, mutta kyllä se hyvin korea mahtaa olla.
Muhkean näköinen se taas oli patruunakin. Vanhat olivat vastassa
portailla ja antoivat siinä suuta nuorille.

77. Mutta tuvassa oli väelle valmistettu kestit, ja niissä ne vasta oli
voit, viilit, rieskat. Kahvia juotettiin ja olutta ja viinaa niin paljon kuin
ikinä miehiin mahtui ja illalla tanssittiin. Oli kolmet viulut
soittamassa. Herrasväet tulivat ovensuuhun katselemaan ja nyt oli
armo taas toisenlaisissa hepenissä: vaaleanpunaisissa, ja niin
ohkaisissa, että hihojen läpi paistoi pinta.
— No, kuinka kontrahdin kävi? keskeytti vaari vihdoin äreästi
poikansa kertomuksen. — Taisit juoda juovuksiin ja antaa nahkasi
mennä huutokaupalla.
— Eikö mitä! Kävinhän minä vanhan patruunan puheilla ja hän
vakuutti meidän saavan hyvän isännän ja lupasi vielä erittäin puhua
meidän torpastamme.
— No, teittekö kirjalliset kaupat?
— Eihän siinä olisi aikaa ollut, kun juuri nuorta paria odotettiin,
mutta sen patruuna merkitsi kontrahdin syrjään, että vielä
kymmenen vuotta eteenpäin saamme asua tässä entisellä verolla.
— Mahdoit panna lisäämään, että elinajan…
— Onhan sitä nyt taas kymmenessäkin vuodessa tällä verolla.
Sitten vaurastuvat lapset ja rupeaa saamaan irti tuosta suostakin.
— Jo pistit käpäläsi ketun paulaan.
Kalle on täynnä toiveita, vanha patruuna on vakuuttanut, että
nuoresta patruunasta tulee hyvä isäntä. Mitä tässä siis rupeaa
suremaan! Hetken päästä on hän jo jatkamassa juttuaan
tuliaiskesteistä.

78. Hän oli aidanraosta nähnyt nuorten kävelevän puutarhassa. Armon
liepeet olivat lakaisseet käytävää, jotta hiekka pölysi. Sitten olivat
lähteneet soutelemaan ja armo oli laulaa liritellyt veneessä.
— Ei nyt hullumpata, kuinka sillä piti olla koreat alushameet!
Päällepäin minä ne hänen sijassaan olisin pannut.
Pienemmät lapset kähisevät vanhan armon lähettämien tuliaisten
ympärillä, mutta Hanni kuuntelee isän kertomusta, kuuntelee
hohtavin poskin, silmät loistaen ja huulet auki, ikäänkuin särpimässä
joka sanaa.
Liena tuntee inhoavansa miestään. Missä kesteissä hän on
ollutkaan juomassa ja syömässä! Hän tuntee kauheaa halua karata
esiin, iskeä nyrkkinsä pöytään ja tukkia hänen suunsa. Tai paeta pois
kuulemasta! Mutta uteliaisuus pidättää häntä huoneessa.
— Sillä kuuluu olevan niin kauheasti vaatteita, päivittelee Kalle yhä
innoissaan, — että piti kolmella hevosella vedettämän asemalta,
paljasta vaatetta!
Lienan sisu kiehuu, hänen täytyy välillä käydä ulkoilmassa, jotta
saisi hengitetyksi.
— Mahtaneeko vanha patruuna mainita mitään siitä, että
Kankaanpään kasvatti on Pimeänpirtin miehellä? kysäisee hän
vihdoin, jäätyään kahdenkesken Kallen kanssa.
— Kyllä minä kumminkin pyysin, vastaa Kalle reippaasti. — Senhän
siinä juuri pitääkin tepsiä…
Liena on ääneen huutamaisillaan.