Langkah pertama dari algoritma pengujian primality AKS adalah untuk memeriksa apakah nomor input adalah kekuatan yang sempurna. Tampaknya ini adalah fakta yang terkenal dalam teori bilangan karena makalah ini tidak menjelaskannya secara terperinci. Dapatkah seseorang memberi tahu saya bagaimana melakukan ini dalam waktu polinomial? Terima kasih.
23
Jawaban:
Dengan diberi nomor n, jika bisa dituliskan sebagai (b> 1), maka . Dan untuk setiap tetap , memeriksa apakah ada dengan dapat dilakukan dengan menggunakan pencarian biner. Karenanya total waktu yang berjalan adalah . b < log ( n ) + 1 b a a b = n O ( log 2 n )Sebuahb b < log( N ) + 1 b Sebuah Sebuahb= n O ( log2n )
sumber
Lihat Bach dan Sorenson, algoritma Sieve untuk pengujian daya sempurna, Algorithmica 9 (1993), 313-328, DOI: 10.1007 / BF01228507, dan DJ Bernstein, Mendeteksi kekuatan sempurna dalam waktu yang pada dasarnya linear, Matematika. Comp. 67 (1998), 1253-1283.
sumber
Saya menemukan solusi yang menarik dan elegan di koran: Tentang penerapan uji keutamaan kelas AKS, oleh R.Crandall dan J.Papadopoulos, 18 Mar 2003.
sumber
ps: Semua lg adalah basis 2.
Kode python:
sumber