A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.
The AKS primality test is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite and this without relying on mathematical conjectures such as the generalized Riemann hypothesis. The proof is also notable for not relying on the field of analysis. In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work.
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'.
Manindra Agrawal is an Indian computer scientist and professor at the Department of Computer Science and Engineering at the Indian Institute of Technology, Kanpur. He was the recipient of the first Infosys Prize for Mathematics, the Godel Prize in 2006; and the Shanti Swarup Bhatnagar Award in Mathematical Sciences in 2003. He has been honoured with Padma Shri, India's 4th highest civilian award, in 2013.
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.
Neeraj Kayal is an Indian computer scientist and mathematician noted for development of the AKS primality test, along with Manindra Agrawal and Nitin Saxena. Kayal was born and raised in Guwahati, India.
In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself.
Sanjay Mittal is a Professor of computational fluid dynamics in the Department of Aerospace Engineering at Indian Institute of Technology Kanpur, India.
Kalyanmoy Deb is an Indian computer scientist. Deb is the Herman E. & Ruth J. Koenig Endowed Chair Professor in the Department of Electrical and Computing Engineering at Michigan State University. Deb is also a professor in the Department of Computer Science and Engineering and the Department of Mechanical Engineering at Michigan State University.
In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant such that the worst-case running time of the algorithm, on inputs of size , has an upper bound of the form
In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally:
Trivandrum Ramakrishnan "T. R." Ramadas is an Indian mathematician who specializes in algebraic and differential geometry, and mathematical physics. He was awarded the Shanti Swarup Bhatnagar Prize for Science and Technology in 1998, the highest science award in India, in the mathematical sciences category.
Kapil Hari Paranjape is an Indian mathematician specializing in algebraic geometry. He is a Professor of Mathematics at the Indian Institute of Science Education and Research, Mohali.
Jaikumar Radhakrishnan is an Indian computer scientist specialising in combinatorics and communication complexity. He has served as dean of the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai, India, where he is currently a senior professor.
Amalendu Krishna is an Indian mathematician in the Department of Mathematics, Indian Institute of Science (IISc), Bangalore, specializing in algebraic cycles and K-theory. He was awarded the Shanti Swarup Bhatnagar Prize for Science and Technology, India's highest prize for excellence in science, mathematics and technology, in the mathematical sciences category in the year 2016.
Amalendu Chandra is an Indian theoretical physical chemist, a professor and the head of the Department of Chemistry at the Indian Institute of Technology, Kanpur. He is known for his microscopic theories and simulations on liquids, interface and clusters. He is an elected fellow of the Indian Academy of Sciences and the Indian National Science Academy. The Council of Scientific and Industrial Research, the apex agency of the Government of India for scientific research, awarded him the Shanti Swarup Bhatnagar Prize for Science and Technology, one of the highest Indian science awards, in 2007, for his contributions to chemical sciences.
Mangalore Anantha Pai was an Indian electrical engineer, academic and a Professor Emeritus at the University of Illinois at Urbana–Champaign. A former professor of electrical engineering at the Indian Institute of Technology, Kanpur, he is known for his contributions in the fields of power stability, power grids, large scale power system analysis, system security and optimal control of nuclear reactors and he has published 8 books and several articles. Pai is the first India born scientist to be awarded a PhD in Electrical Engineering from the University of California, Berkeley.
Yogesh Moreshwar Joshi is an Indian chemical engineer, rheologist and the Pandit Girish & Sushma Rani Pathak Chair Professor at the Indian Institute of Technology, Kanpur. He is known for his studies on metastable soft matter and is an elected fellow of the Society of Rheology, Indian National Science Academy, Indian Academy of Sciences, and Indian National Academy of Engineering. In 2015, the Council of Scientific and Industrial Research, the apex agency of the Government of India for scientific research, awarded Joshi the Shanti Swarup Bhatnagar Prize for Science and Technology for his contributions to Engineering Sciences. In 2023, he received prestigious J C Bose fellowship constituted by the Science and Engineering Research Board, Government of India.
Amit Kumar is Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Delhi. He received his B.Tech. degree from Indian Institute of Technology Kanpur in 1997, and Ph.D. from Cornell University in 2002. He worked as Member of Technical Staff at Bell Labs, Murray Hill, New Jersey, U.S. during 2002–2003. He joined IIT Delhi as faculty member in 2003. He works in the area of combinatorial optimization, approximation algorithms and online algorithms. He is working extensively on problems arising in scheduling theory, clustering, and graph theoretic algorithmic problems.
Amit Agrawal is an Indian engineer and an institute chair professor at the department of mechanical engineering of the Indian Institute of Technology, Bombay. He leads a group of scientists who are involved in the development of next-generation diagnostic microdevices.
