Computer Science – Computational Complexity
Scientific paper
2008-11-24
Computer Science
Computational Complexity
Scientific paper
Although a deterministic polytime algorithm for primality testing is now known, the Rabin-Miller randomized test of primality continues being the most efficient and widely used algorithm. We prove the correctness of the Rabin-Miller algorithm in the theory V1 for polynomial time reasoning, from Fermat's little theorem. This is interesting because the Rabin-Miller algorithm is a polytime randomized algorithm, which runs in the class RP (i.e., the class of polytime Monte-Carlo algorithms), with a sampling space exponential in the length of the binary encoding of the input number. (The class RP contains polytime P.) However, we show how to express the correctness in the language of V1, and we also show that we can prove the formula expressing correctness with polytime reasoning from Fermat's Little theorem, which is generally expected to be independent of V1. Our proof is also conceptually very basic in the sense that we use the extended Euclid's algorithm, for computing greatest common divisors, as the main workhorse of the proof. For example, we make do without proving the Chinese Reminder theorem, which is used in the standard proofs.
Herman Grzegorz
Soltys Michael
No associations
LandOfFree
A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-303542