A problem on Number theory

You are given three non-negative integers $A$, $B$ and $C$, find a number $X$ (say) satisfy $X^A \equiv B\pmod{2C + 1}$ and $0 \le X \le 2C$.

I am inquisitive about how to approach this one?

-
Hmm... –  Guess who it is. Dec 16 '10 at 11:53
@J.M:I don't have ACM access yet! :( –  VelvetThunder Dec 16 '10 at 11:55
The paper (A Generalized q-th Root Algorithm)) suggested above can be found at the author's publication page computing.dcu.ie/~ajohnston/pub.htm –  Weaam Dec 16 '10 at 12:36

Assuming X coprime to 2C+1. Then Euler totient theorem gives $X^{\varphi(2C+1)} \equiv 1 \mod 2C+1$.

Assuming further that A coprime to $\varphi(2C+1)$. Then (By Bezout's identity) there's a D such that $AD \equiv 1 \mod \varphi(2C+1)$. In which case $(X^A)^D \equiv X^{(AD)} \equiv X \equiv B^D \mod 2C+1$

In steps:

1- Compute $\varphi(2C+1)$ (Which should be very time consuming if it's a product of large primes).

2- Obtain D (through extended euclidean algorithm!)

3- Compute $B^D \mod 2C+1$.

Note, if a fast solution to your problem exists, then RSA cryptography would be insecure.

-

Generally it's difficult to compute such $\rm\:A$'th roots in $\rm \mathbb Z/m\$ except for simple special cases, e.g. when $\rm\ gcd(A,\phi(m)) = 1\:.\$ Otherwise one generally has to resort to factoring $\rm\:m\:$ to get $\rm\: \phi(m)\:$ and hence the factorization of $\rm\ Z/m^*\$ into a product of cyclic groups. Then one may apply generalizations of Shanks's square-root algorithm. See for example Section 3.2: Extensions of Shanks's algorithm to r'th roots in cyclic groups in Lindhurst: Computing roots in finite fields and groups, with a jaunt through sums of digits. One can also generalize the Euler criterion for square-roots - see my post here and Chapter 4 of Ireland and Rosen, A Classical Introduction to Modern Number Theory.

-
If I may add, to avoid misinterpreting what you wrote, that $gcd(A, \varphi(m))=1$ is a "simple special case" in a very strict sense. It is a basic assumption in RSA cryptography, and is still computationally difficult, one usually has to factor m to solve it. The assumption $gcd(A, \varphi(m))=1$ ensures that the solution X is unique. –  Weaam Dec 16 '10 at 18:50
It will be an easy question if we know the primitive root to it, according to André Weil. –  awllower Apr 2 '11 at 7:29
Or any book on elementary number theory. –  awllower Apr 2 '11 at 7:29