PYI: Arithmetic and Geometric Methods in Computational Complexity

PYI：计算复杂性中的算术和几何方法

• 批准号: 8957317
• 负责人: Ming-Deh Huang
• 金额: $ 15.95万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-10-01 至 1995-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8957317&HistoricalAwards=false
• 关键词: PYI; Arithmetic; Geometric; Methods; Computational

The injection of ideas from number theory and algebraic geometry has brought about remarkable progress in recent years in the study of primality testing and integer factoring, and in computational number theory in general. It is plan to continue the exploration of arithmetric and geometric methods as a fundamental tool in the study of computational problems, particularly those that are related to number theory. The goal is to develop efficient algorithms for them, to study complexity theoretic relation among them, and to explore application to cryptography, as well as other problems in computational complexity. The primary focus will be: (1) Further investigation into primality testing and integer factoring, and other fundamental problems in computational number theory. (2) Development of efficient algorithms for computing with curves and higher dimensional algebraic varieties, particularly as they apply to the computational problems mentioned above. (3) Application of arithmetic and geometric techniques in the analysis of security of public key cryptosystems. Development of new cryptosystems based on geometric ideas.

近年来，数论和代数几何思想的注入在素数检验和整数因数分解的研究以及一般的计算数论方面取得了显著的进展。计划继续探索算术和几何方法作为研究计算问题的基本工具，特别是那些与数论有关的问题。目标是为它们开发有效的算法，研究它们之间的复杂性理论关系，并探索在密码学中的应用，以及其他计算复杂性问题。主要的重点将是：(1)进一步研究质数检验和整数因数分解，以及计算数论中的其他基本问题。(2)开发曲线和高维代数变量计算的有效算法，特别是当它们适用于上述计算问题时。(3)算法和几何技术在公钥密码系统安全性分析中的应用。基于几何思想的新密码系统的发展。