How to guess \(\ell\)-th roots modulo n by reducing lattice bases. (English) Zbl 0692.10005

Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conference, AAECC-6, Rome/Italy 1988, Lect. Notes Comput. Sci. 357, 427-442 (1989).
[For the entire collection see Zbl 0671.00023.]
The authors develop a new method based on lattice basis reduction which allows to compute the \(\ell\)-th root x of an integer y modulo a composite integer n. It requires some reasonable assumptions on n and that some approximation to x is known. The results have important consequences in cryptography and especially allow to attack Okamoto’s cryptosystem [I. Okamoto and A. Shiraishi, Proc. 1985 Symp. on Security and Privacy (1985), and T. Okamoto, Electron. Lett. 58, 582 (1986)]. The paper generalizes and improves on earlier work by A. M. Frieze, J. Hastad, R. Kannan, J. C. Lagarias and A. Shamir [SIAM J. Comput. 17, No.2, 262-280 (1988; Zbl 0654.10006)] and M. Blum [ACM Trans. Comput. Syst. 1, No.2, 175-193 (1983)].
Reviewer: M.Pohst


11A15 Power residues, reciprocity
94A60 Cryptography
68Q25 Analysis of algorithms and problem complexity
11H55 Quadratic forms (reduction theory, extreme forms, etc.)
11H06 Lattices and convex bodies (number-theoretic aspects)
11T99 Finite fields and commutative rings (number-theoretic aspects)
11A41 Primes