2

Can someone tell me the efficient way to solve this problem ?

abc mod m

a, b, c, and m are 32 bit int

where m is not a prime number and a is not coprime to m?I've looking for the answer, but haven't found it There are some answered questions that familiar with this question, but none of them can explain my problem. Remember if

abc mod m != abc mod m

mfrazi
  • 31
  • 4
  • 2
    http://cs.stackexchange.com/ is probably a better place for this question. – R Sahu Nov 12 '14 at 16:42
  • This question appears to be off-topic because http://cs.stackexchange.com/ is a better place for this question. – R Sahu Nov 12 '14 at 16:44
  • 5
    It's not really a duplicate of the pow question. The common problem is computing this without overflow. – hatchet - done with SOverflow Nov 12 '14 at 16:46
  • Thanks hatchet for spotting the main issue. +1 – fjardon Nov 12 '14 at 16:47
  • @anatolyg this question is about [modular exponentiation](http://en.wikipedia.org/wiki/Modular_exponentiation) so it's not a duplicate of the other question – phuclv Nov 12 '14 at 16:50
  • 1
    So what you want is not just a ModPow function, but a ModPowPow function. – hatchet - done with SOverflow Nov 12 '14 at 16:52
  • some other duplicates http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n http://stackoverflow.com/questions/8287144/modulus-power-of-big-numbers http://stackoverflow.com/questions/11448658/modular-exponentiation http://stackoverflow.com/questions/23935862/modular-exponentiation – phuclv Nov 12 '14 at 16:53
  • Sorry - missed the part about `b^c` being too big! – anatolyg Nov 12 '14 at 16:54
  • thanks for the comment, but most of the questions ask a^b mod n instead of a^b^c mod n. Those are two different things. I think, we have to calculate b^c, but in what way? There must be some way to simplify it. If n is a prime number and a is coprime to n, we can use Euler's totient function. But if n is not prime, this is my problem which i ask to you :) – mfrazi Nov 13 '14 at 01:26
  • @mfrazi I voted-up, I really like part `a is not coprime to m`. All other questions (or just answers) quietly assumed relatively prime of numbers. However, I describe solution to this problem in other question (in which it fits). Look at [this answer](http://stackoverflow.com/a/27465498/2349936). I hope it will be helpful and I was understandable. – Tacet Dec 14 '14 at 03:57
  • Generally I don't understand, why it was closed. I agree [finding a^b^c^… mod m](http://stackoverflow.com/questions/4223313/finding-abc-mod-m) is same question, but without (a moment ago) any answer, if a,b aren't co-prime! And other answer seems reasonable, if there was no answer to this question. All repeat schematic solution to case `gcd(a,m)=1`. Even here can be seen this case without any tips to solve this problem. It is so unusual that it seems even merit a separate thread. – Tacet Dec 14 '14 at 04:06

0 Answers0