I read that the test of Agrawal-Kayal-Saxony was improved by some craftsmen, so that his work requires not O (log ^ 7.5 (n)), but O (log ^ 3 (n)). Nowhere on the Internet did I find a normal code with more or less clear explanations of the work (maybe I was just looking bad)

Could someone give an example of the implementation of this test with explanations why it works? Implementation is desirable on c / c ++, but in general any language will go =)

Thanks in advance to all who responded!

  • habrahabr.ru/qa/7255 here some useful links are indicated, maybe there is something useful. it’s not easy to evaluate the efficiency of the O (log ^ 7.5 (n)) algorithm from O (log ^ 3 (n)) ... - Yura Ivanov
  • and tried to go to the Russian Wikipedia, scroll to the bottom and see the list of links? one by one I found the implementation on java (although it is in the form of a jar file, but there are also source codes inside, I don’t know if it’s all), on another pdf link describing the algorithm’s work. - KoVadim

0