Kompleksitas mengambil mod

Ini sepertinya pertanyaan yang seharusnya memiliki jawaban yang mudah, tapi saya tidak punya yang pasti:

Jika saya memiliki dua $n$ bit angka $a, p$ , apa kerumitan komputasi ?$a\bmod p$

Membagi dengan akan membutuhkan waktu mana adalah kompleksitas dari perkalian. Tetapi bisakah dilakukan sedikit lebih cepat?$a$$p$ $O(M(n))$$M(n)$$\bmod$

Shoup (Bagian 3.3.5, Teorema 3.3, hal. 62) memberikan batasan untuk menghitung residu dalam waktu mana a = q ⋅ p + r dan mencatat a = n .$r$$O(n\log q)$$a = q\cdot p +r$$\log a = n$

Saya kira jika dan a keduanya kira-kira n angka bit, maka q (dan karenanya log q ) harus agak kecil, memberikan O ( n ) .$p$$a$$n$$q$$\log q$$O(n)$

Jika adalah angka n- bit, dan p relatif kecil, maka pendekatan multiplikasi harus lebih cepat.$a$$n$$p$