Pulse en una miniatura para ir a Google Books.
Cargando... Primality Testing in Polynomial Time: From Randomized Algorithms to “PRIMES Is in P” (2004)por Martin Dietzfelbinger
Ninguno Cargando...
Inscríbete en LibraryThing para averiguar si este libro te gustará. Actualmente no hay Conversaciones sobre este libro. Ninguna reseña sin reseñas | añadir una reseña
Pertenece a las series
On August 6, 2002,a paper with the title PRIMES is in P, by M. Agrawal, N. Kayal, and N. Saxena, appeared on the website of the Indian Institute of Technology at Kanpur, India. In this paper it was shown that the primality problem has a deterministic algorithm that runs in polynomial time. Finding out whether a given number n is a prime or not is a problem that was formulated in ancient times, and has caught the interest of mathematicians again and again for centuries. Only in the 20th century, with the advent of cryptographic systems that actually used large prime numbers, did it turn out to be of practical importance to be able to distinguish prime numbers and composite numbers of signicant size. Readily, algorithms were provided that solved the problem very efficiently and satisfactorily for all practical purposes, and provably enjoyed a time bound polynomial in the number of digits needed to write down the input number n. The only drawback of these algorithms is that they use randomization - that means the computer that carries out the algorithm performs random experiments, and there is a slight chance that the outcome might be wrong, or that the running time might not be polynomial. To find an algorithm that gets by without randomness, solves the problem error-free, and has polynomial running time had been an eminent open problem in complexity theory for decades when the paper by Agrawal, Kayal, and Saxena hit the web. No se han encontrado descripciones de biblioteca. |
Debates activosNinguno
Google Books — Cargando... GénerosSistema Decimal Melvil (DDC)512.9Natural sciences and mathematics Mathematics Algebra Foundations of AlgebraClasificación de la Biblioteca del CongresoValoraciónPromedio: No hay valoraciones.¿Eres tú?Conviértete en un Autor de LibraryThing. |