SGER: Concrete Complexity of Number-Theoretic Problems of Importance to Cryptography

现代密码学在很大程度上依赖于对某些数论问题的渐近难解性的假设。然而，在实现层面，必须对固定大小的问题的具体复杂性做出假设（例如，在实践中分解假设的难解性是“不可能分解1024位加密数字”）。确定什么“小尺寸”太小而不安全是这个项目的重点：设计和实现算法，在实践中解决那些数字理论问题，这些问题是现代密码学的支柱。这些对现代密码学至关重要的问题是：1)离散对数问题；Ii)确定合数的二次残差模；Iii)密码数的分解。这三个问题将是这个项目的核心。该项目还将考虑与这三个问题相关的一系列问题：素数测试、大数快速算术、丢芬图近似、小数快速因数分解、随机数因数分解，以及随着研究进展肯定会出现的其他问题

Modern cryptography relies heavily on assumptions about the asymptotic intractability of certain number-theoretic problems. However, at the implementation level, assumptions about the concrete complexity of problems of a fixed size must be made (e.g. the intractability of factorization assumption in practice is "factoring 1024-bit cryptographic numbers is impossible"). Determining what "small-size" is too small to be secure is the focus of this project: to design and implement algorithms which solve, in practice, those number-theoretic problems which are the pillars of modern cryptography. These problems which are vital to modern cryptography are i) the discrete logarithm problem; ii) deciding quadratic residuosity modulo a composite number; iii) factorization of cryptographic numbers. These three problems will be central to this project. The project will also consider a host of problems peripheral to these three: primality testing, fast arithmetric with large numbers, diophantine approximation, rapid factorization of small numbers, factorization of random numbers, and other problems that will surely arise as research progresses.***