English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Although a deterministic polytime algorithm for primality testing is nowknown, the Rabin-Miller randomized test of primality continues being the mostefficient and widely used algorithm.  We prove the correctness of the Rabin-Miller algorithm in the theory V1 forpolynomial time reasoning, from Fermat's little theorem. This is interestingbecause the Rabin-Miller algorithm is a polytime randomized algorithm, whichruns in the class RP (i.e., the class of polytime Monte-Carlo algorithms), witha sampling space exponential in the length of the binary encoding of the inputnumber. (The class RP contains polytime P.) However, we show how to express thecorrectness in the language of V1, and we also show that we can prove theformula expressing correctness with polytime reasoning from Fermat's Littletheorem, which is generally expected to be independent of V1.  Our proof is also conceptually very basic in the sense that we use theextended Euclid's algorithm, for computing greatest common divisors, as themain workhorse of the proof. For example, we make do without proving theChinese Reminder theorem, which is used in the standard proofs.

A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem