Primality Testing in Polynomial Time

- From Randomized Algorithms to 'PRIMES Is in P'

af

indgår i serie Lecture Notes in Computer Science


Studiebog
Primality Testing in Polynomial Time
  • Leveringstid Straks (sendes på e-mail)
Format:
E-bog, PDF
Udgivelsesdato:
17-08-2004
Sprog:
Engelsk
  • Beskrivelse
  • Yderligere info
  • Anmeldelser

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'hasa'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 mathema- ciansagainandagainfor centuries. Onlyinthe 20thcentury,with theadvent 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 signi?cant size. Readily, algorithms were provided that solved the problem very e?ciently 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 ?nd an algorithmthat gets by without rand- ness, 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.

Andre udgaver:

Bog, paperback

Vis mereVis mindre

Udgivelsesdato:
17-08-2004
ISBN13:
9783540259336
Format:
PDF

Vis mereVis mindre

Vis mereVis mindre

Fandt du ikke hvad du søgte?

Hvis denne bog ikke er noget for dig, kan du benytte kategorierne nedenfor til at finde andre titler. Klik på en kategori for at se lignende bøger.

Se andre bøger, der handler om

Velkommen til Saxo – din danske boghandel!

Hos os kan du handle som gæst, Saxo-bruger eller Premium-medlem – du bestemmer helt selv. Skulle du få brug for hjælp, sidder vores kundeservice-team klar ved både telefonerne og tasterne.

Om fordelspriser hos Saxo

For at købe bøger til fordelspris, skal du være medlem af Premium, Premium Shopping eller Premium Studie. De første 30 dage er gratis for nye medlemmer. Medlemskabet fornyes automatisk og kan altid opsiges. Læs mere om fordelene ved vores forskellige medlemskaber her.

Machine Name: SAXO082