2
$\begingroup$

Suppose we know the greatest common divisor, $\gcd(A,B)$, of two numbers $A$ and $B$.

Is there a way that we can find the maximum value of $a^b \bmod N$ where $N$ is any number?

We have a finite range in which both $a$ and $b$ belong so we can just check for all values of $a$ and $b$ that satisfy the given gcd and get the maximum value of $a^b \bmod N$.

But I do feel there might be a better approach to approach this problem.So please guide me.

Also is there a way around this problem if we only know $\gcd(a,b) \bmod N$ for $a$ and $b$ instead of \gcd(a,b).

Can we still come up with something to determine the maximum value of a^b \bmod N$.

  • 0
    Thanks for clearing things up. I doubt there's any way to do what you want. To begin with, the concept of maximizing a modular value is unnatural, e.g., if you add 1 to 16 you get something bigger, but if you add 1 to 16 mod 17, you get something "smaller", namely, zero. But I hope someone proves me wrong.2012-06-11

0 Answers 0