Cuốn sách này có cách tiếp cận adifferent giới thiệu mật mã: tofit quan tâm nhiều hơn nữa cho các khía cạnh ứng dụng của mật mã. Nó giải thích tại sao "sách giáo khoa mật mã" isonly tốt trong một thế giới lý tưởng, nơi dữ liệu ngẫu nhiên và kẻ xấu hoạt động tiết lộ | Equation ì3-l 2 _ I inocỊ pj Euler s Criterion provides a criterion to test whether or not an element in is a quadratic residue if congruence is satisfied then xEQRp otherwise is satisfied and x QNRp. Letn be a composite natural number with its prime factorization as Equation Ei Eo t- n pf Po Pfe Then byTheorem is isomorphic to . Since isomorphism preserves arithmetic we have . Theorem Let n be a composite integer with complete factorization in . Then x c QRnif and only if X mod ple i . Ti and hence if and only if x mod p i c QRpifor prime Pi with i 1 2 k o r z Therefore if the factorization of n is known given the quadratic residuosity of x modulon can be decided by deciding the residuosity of x mod p for each prime p n. The latter task can be done by testing Euler s criterion. However if the factorization of n is unknown deciding quardratic residuosity modulo n is a nontrivial task. Definition Quadratic Residuosity QR Problem INPUT n a composite number X e z . OUTPUT YESif x e QRn. The QRP is a well-known hard problem in number theory and is one of the main four algorithmic problems discussed by Gauss in his Disquisitiones Arithmeticae 119 . An efficient solution for it would imply an efficient solution to some other open problems in number theory. In Chapter 14 we will study a well-known public-key cryptosystem named the Goldwasser-Micali cryptosystem that cryptosystem has its security based on the difficult for deciding the QRP. CombiningTheorem and Theorem we can obtain . Theorem 1 Let n be a composite integer with k 1 distinct prime factors. Then exactly - fraction of . . . V . . . n elements in are quadratic residues modulo n. Thus for a composite number n an efficient algorithm for deciding quadratic residuosity modulo . . r . 7 n will provide an efficient statistic test on the proportion of quadratic residues in and hence byTheorem provide an efficient algorithm for answering the question
