code_warrior's blog

By code_warrior, history, 2 months ago,

Hello, freinds recently i was confronted with a problem which goes like this->

Given a positive odd prime number p and another positive integer k (1<k<=p-1) find the minimum value of m such that pow(k,m)%p=1.

One straight way of approaching this is to iterate untill we get what we need thus contributing a time complexity of O(p), but i fancy if there exists even a more efficient way to do so. Can anyone help me or give some clue of how to solve it in less than O(p) time complexity.

• 0

 » 2 months ago, # |   0 Although it now seems to me that it has to don something with euler tuoteint function but couldn't figure it out! xD.
•  » » 2 months ago, # ^ |   0 iterate over divisors of phi(p).
•  » » » 2 months ago, # ^ |   0 I tried it over few samples and found it correct. Will you please explain the logic behind it?
•  » » » » 2 months ago, # ^ |   +1 modular powers are perodic with period phi(p).if there exist a period smaller than phi(p) than, phi(p) must be multiple of that period.
 » 2 months ago, # | ← Rev. 2 →   0 claim: $m=p-1$. If possible let there exist smallest $rr$ so \$p=rq+r_1 \,\, ,r_1
•  » » 2 months ago, # ^ |   0 It is not always true. For example, if p=5 and k=4 then by your logic it should be m=5-1=4. Though pow(4,4)%5=1, but for m=2 also pow(4,2)%5=16%5=1. Hence , the right answer would then be 2 and not 4.
•  » » » 2 months ago, # ^ |   +1 Oh I write that to find mistake in my proof. Now I got it you should ask minimum positive m (otherwise m=0 always work) and in my proof part mistake is r1-1 should not be equal to 0 then only that proof is correct otherwise not. Thanks btw.