POWOFPOW - Help

general
, ,
1

I know that A^phi(n) mod n = 1, when gcd(A, n)=1.
But i cannot understand how to apply this concept to solve this problem. I am not able to reduce the formula so that i can code

Can someone explain how to reduce the formula.
I am referring this code to understand the logic.

can some explain how to handle the case when n and n1 are no coprime. What is the idea to solve it when this is the case. If some can explain the code linked above will also be helpful.

2

I put some notes in this discussion (link)

3

That discussion does not contain full information regarding the number theory concept needed to solve. The exponent can be reduced to (k1*n2k^2) modϕ(n) only when we have n and n1 coprime. How to handle the case when there are not?

4

It’s still true, if a little more complicated, for the case when n and n_1 have common factors.

Maybe if it gets upvoted, I will expand it. You say “any help will be appreciated”, but apparently there is some threshold to “any”.

1 Like
5

I have read this blog https://cp-algorithms.com/algebra/phi-function.html. I tried coding the same, gave me WA. I have seen other people’s code, which i cannot understand.

6

If the problem is coding \phi(n), essentially you need to find the prime factors of n, possibly including multiplicity. The formula for \phi(n) builds on those. If you are at all concerned that you have not found \phi(n) correctly, I’d recommend writing a program just to test this. You can make a test set by checking Wolfram Alpha for example. One useful test value to include is the square (or cube etc) of some other test value. You should see that \phi(n^2) = n\phi(n) (but don’t code for this directly - it’s not a useful shortcut, just a useful test). There are a variety of ways of getting \phi(n), some easier to understand than others.

If the problem is using the exponent E \bmod \phi(n) when g:=\gcd(n,n_1)>1, you need to be a little cautious of the multiplicity of the prime factors of g relative to the same factors in n. There are two aspects of a single issue here; the low powers of n_1 may not be included in the cycle that develops later. So the two possible errors that can arise are:

  • treating high powers of n_1 as very low powers because E \bmod \phi(n) is very small although E is large, and
  • when avoiding the above, accidentally treating small values of E as though they are large.

You can avoid the first error by taking the exponent as (E\bmod \phi(n)) + \phi(n) instead of just E\bmod \phi(n), but that exposes you to the second error. You can test for this carefully in integers or just use logarithms to see whether E is above or below \phi(n).