An Interesting problem related to modulo arithmetic

Revision en3, by code_warrior, 2020-11-17 11:09:47

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English code_warrior 2020-11-17 11:09:47 1 Tiny change: '(1<k<=p-1)find the m' -> '(1<k<=p-1) find the m'
en2 English code_warrior 2020-11-17 10:58:21 6
en1 English code_warrior 2020-11-17 10:57:53 539 Initial revision (published)