small_doubt's blog

Calculating big powers modulo a prime number
By small_doubt, history, 6 years ago, In English

I have a number A and a number B(which is very large calculated by NcR or C(N,R) modulo 10e9+7) and i want to find A^B(A raise to the power B) but by fast exponentation i get wrong answer. Like for example A=2 and B=6 and mod=5 then actual answer is(2^6)%5=4 but since i have to use mod at every step my answer is (2^(6%5))%5=2. I can't store B in a number because it's too large.How should i go about it?Thanks in advance.

  • Vote: I like it
  • -26
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This is a problem from an ongoing contest.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it -52 Vote: I do not like it

    Did i ask a solution to the problem or just a small part (that too computational) of it? Moreover these contest are to learn a new thing and so i wanted to learn this thing.You also know this is just the last part of the problem and to reach here you've to use your brain and from here it's just some technique which someone knows and some don't.Therefore i want to know the technique.If you don't want to help then it's Okay.Maybe you find it asking the solution.I searched google for the answer but couldn't get it therefore i asked it here.You mean i should sit idle without looking to learn this technique.I know i'll learn faster if i get to know this now.Please brother don't think otherwise for me.

    → Reply
»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

How big can B be?

→ Reply
»
6 years ago, # |
  Vote: I like it -22 Vote: I do not like it

It can be computed using ((A%mod)^(B%(mod-1)))%mod

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    hey don't give spoilers for ongoing contests..

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

      I just want to know that did you invent this technique?You also got to know from somewhere only so what's the point when i am just learning a technique and NOT AT ALL asking for solution.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        I don't know which contest specifically where you need this technique for a problem, but in general, contests are meant for competition so it's not fair that you get outside help while the other contestants don't. If you wanted to learn, you could do problems from online judges where it (probably) wouldn't be against any rules to help on them.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    After calculating B normally ? I mean by using mod at every step to calculate B?

    → Reply