1

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.

seVenVo1d
  • 452
  • Can you please put your pseudocode show that I could look up for the mistake? – Kumar Jul 03 '19 at 06:55
  • 1
    Can I just post the code..? – seVenVo1d Jul 03 '19 at 06:59
  • Can you compute $\phi(M)$? If yes, you could try to increase $B$. – Dirk Jul 03 '19 at 07:04
  • I edited my post. Actually my point is reducing B. How can I increase it ? – seVenVo1d Jul 03 '19 at 07:17
  • No, there isn't a way to reduce the modulus in this way. (You could replace $M$ by a divisor of $M$ to get a valid congruence, but the result would not answer the original question.) The fast method of evaluation you are looking for is repeated modular squaring. – Greg Martin Jul 03 '19 at 07:32
  • @GregMartin If factoring M solves the problem I can try it. I am not trying to find some algorithm to reduce the M values. I am looking for some mathematical equation such as. $A^B mod(M) = A^B mod(p1) \times A^B mod(p2)$ where $p1 \times p2 = M$ ? – seVenVo1d Jul 03 '19 at 08:43
  • If the initially $B < \phi(M)$ then Euler's theorem is of no help reducing $B$ further. Are you asking what to do in this case? – Bill Dubuque Jul 03 '19 at 15:07

2 Answers2

1

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!

Culver Kwan
  • 2,785
0

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.