Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Hmm... –  J. M. Dec 16 '10 at 11:53
    
@J.M:I don't have ACM access yet! :( –  Quixotic Dec 16 '10 at 11:55
1  
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.