Блог пользователя code_warrior

Автор code_warrior, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Although it now seems to me that it has to don something with euler tuoteint function but couldn't figure it out! xD.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    iterate over divisors of phi(p).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I tried it over few samples and found it correct. Will you please explain the logic behind it?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

claim: $$$m=p-1$$$. If possible let there exist smallest $$$r<p-1$$$ s.t. $$$k^r \equiv 1\,mod\,p.$$$ Since $$$p>r$$$ so $$$p=rq+r_1 \,\, ,r_1<r$$$ for some integer $$$q$$$. Now $$$k^{p-1} \equiv k^{rq+r_1-1} \equiv k^{r_1-1} \equiv 1\, mod\, p. (k^{p-1} \equiv 1\,mod\,p)$$$(by LFT) so we got a contradiction that r was smallest since we found $$$r_1-1<r$$$. Hence $$$m=p-1$$$

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.