Reducing the mod value itself (modular calculus)

Question

I wrote an algorithm by combining Fermat's Little Theorem and Euler's Method. However, I am experiencing a problem in Euler's method.

For instance, If I take $(A, B, M)$ such that $A^B mod(M)$.

When the initial values are $(12341, 123141, 12313)$ they reduce to $(12341, 7113, 12313)$ However after this the program won't go further. The reason I believe is that when $$B < \phi(M)$$ the algorithm stops working. So simply to algorithm work properly we need larger $B$ but small $M$.

At this point, my question is there a way to reduce M to small numbers by some mathematical operations ?

def eulers_theorem(A, B, M):
    totient = M
    factors_of_M = [(i-1) / i for i in factorint(M).keys()]
    for i in factors_of_M:
        totient *= i
    new_B = int(B % totient)
    return (A, new_B, M)

So I am factorizing the M values and then calculating the totient of it( $\phi(M)$ ) and then My new B becomes

$B_{new} = B~mod (\phi(M))$

For instance, if (A, B, M) = (123, 562, 100)

$\phi(100) = 40$ so

$$B_{new} = 562~mod (40) = 2$$

So (123, 562, 100) reduces to (123, 2, 100)

In the Above example when $(12341, 123141, 12313)$ it reduces to $(12341, 7113, 12313)$. In this case the algorithm enters a loop since,

$$B_{new} = 7113~mod (\phi(12313)) = 7113~mod(10548) = 7113$$ so $B_{new}$ is always the same.

Answer 1

Apply Fermat's little theorem and extentions, for both of $p_1,p_2$, then apply Chinese remainder theorem ( with LCM extension if needed) to the exponents for each to find the intersection. Apply to B Solve mod M.

Answer 2

First, using modular arithmetic, we can reduce $12341$ to $12341-12313=28$.

As $12313=7\times1759$, we can first find the remainder of $28^{7113}$ divided by $7$ and $1759$. As $28$ is divisible by $7$,$28^{7113}\equiv0$ (mod $7$)

Then, we can use Euler's theorem and other theorems to find the remainder of $28^{7113}$ divided by 1759. Note that $\phi(1759)=1758$

$28^{7113}\equiv28^{1758\times4+81}\equiv28^{81}\equiv267$ (mod $1759$)

Then by Chinese Remainder theorem, the remainder of $12341^{123141}$ divided by $12313$ is $5544$.

Hope that it helps!