سوال الگوریتمیک

[zeinalkhani]

الگوریتمی که باقیمانده تقسیم xبه توان nبر pرا محاسبه کند(صفحه 50 از کتاب نی÷ولیتان)
اگه کسی بتونه کمکم کنه ممنون میشم
در ضمن از مرتبه nlognباشه

فرض کنید:
a = k1 * p + r1
b = k2 * p + r2
در این صورت باقیمانده حاصلضرب آنها (a * b) بر p برابر باقیمانده r1 * r2 بر p خواهد بود.
از طرفی با توجه به صورت سوال می توان n را توانی از 2 در نظر گرفت. پس باقیمانده 2 به توان n*k بر p برابر است با:
[(2^(nk-1)) mod p]*[2 mod p]
بنابراین کافیست مقدار بالا را تا رسیدن به یک مقدار آستانه محاسبه کنید.