Trustworthy Systems

Mechanisation of AKS algorithm: Part 1 — the main theorem

Authors

Joseph Chan and Michael Norrish

Australian National University\ NICTA

Abstract

The AKS algorithm (by Agrawal, Kayal and Saxena) is a significant theoretical result proving “PRIMES in P”, as well as a brilliant application of ideas from finite fields. This paper describes the first step towards the goal of a full mechanisation of this result: a mechanisation of the AKS Main Theorem, which justifies the correctness (but not the complexity) of the AKS algorithm.

BibTeX Entry

  @inproceedings{Chan_Norrish_15,
    address          = {Nanjing, China},
    author           = {Chan, Joseph and Norrish, Michael},
    booktitle        = {International Conference on Interactive Theorem Proving},
    keywords         = {interactive theorem proving, number theory, mechanised mathematics},
    month            = aug,
    pages            = {117--136},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/8653.pdf},
    title            = {Mechanisation of {AKS} Algorithm: Part 1 --- the Main Theorem},
    year             = {2015}
  }

Download