The Computational Complexity of Problems Related to         Number Theory
{'Code': '05010200', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'John D. Gannon', 'PO_EMAI': None, 'PO_PHON': None}
The primary focus of this research is the computational complexity of           problems related to number theory.  The goal is to develop efficient            algorithms for these problems, to investigate complexity theoretic              relations among them, and to apply the results obtained to the design           and analysis of public key cryptographic systems.                                                                                                               In the last few years, researchers have begun to explore the use of the         geometric and arithmetic theory of number fields and Abelian varieties          as fundamental tools in the study of the computational complexity of            number theoretic problems.  Very recently, the principal investigator           (jointly with L. M. Adleman) used such tools to show that primality             testing is in random polynomial time.  This is the first time the               problem was proved to be tractable (in the sense of randomized                  computation) without any hypothesis.  In this result, extensive use is          made of the theory of Abelian varieties.  The theoretic machinery and           algorithmic techniques developed in this work are quite general.  The           project explores further applications of these techniques particularly          as they apply to primality testing, integer factoring, deterministic            polynomial factorization over finite fields, and other fundamental              problems in this area.                                                                                                                                          In addition, the project investigates computational complexity under the        parallel network model and the virtual-memory model, and in                     addition studies approximation algorithms for the generalized                   satiafiability problem.                                                                                                                                         The project addresses important computational tasks involving integers,         in particular primality testing and factorization.  If successful, the          new techniques will enable computation with much larger integers which          will have several practical ramifications particularly to cryptography.
{'FirstName': 'Ming-Deh', 'LastName': 'Huang', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Ming-Deh Huang', 'EmailAddress': 'mdhuang@usc.edu', 'NSF_ID': '000201135', 'StartDate': '07/01/1987', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'University of Southern California', 'CityName': 'LOS ANGELES', 'ZipCode': '90033', 'PhoneNumber': '2137407762', 'StreetAddress': '3720 S FLOWER ST FL 3', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'California', 'StateCode': 'CA', 'CONGRESSDISTRICT': '34', 'CONGRESS_DISTRICT_ORG': 'CA34', 'ORG_UEI_NUM': 'G88KLJR3KYT5', 'ORG_LGL_BUS_NAME': 'UNIVERSITY OF SOUTHERN CALIFORNIA', 'ORG_PRNT_UEI_NUM': None}
{'Name': None, 'CityName': None, 'StateCode': None, 'ZipCode': None, 'StreetAddress': None, 'CountryCode': None, 'CountryName': None, 'StateName': None, 'CountryFlag': None, 'CONGRESSDISTRICT': None, 'CONGRESS_DISTRICT_PERF': '""'}
[{'Code': '126400', 'Text': 'ALGEBRA,NUMBER THEORY,AND COM'}, {'Code': '127100', 'Text': 'COMPUTATIONAL MATHEMATICS'}, {'Code': '286500', 'Text': 'NUMERIC, SYMBOLIC & GEO COMPUT'}]
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1987&All=true', 'xml': '8701541.xml'}