1
$\begingroup$

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?

  • 1
    [Hmm...](http://portal.acm.org/citation.cfm?id=315094)2010-12-16
  • 0
    @J.M:I don't have ACM access yet! :(2010-12-16
  • 1
    The paper (A Generalized q-th Root Algorithm)) suggested above can be found at the author's publication page http://www.computing.dcu.ie/~ajohnston/pub.htm2010-12-16

2 Answers 2

1

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.

0

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.

  • 0
    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.2010-12-16
  • 0
    It will be an easy question if we know the primitive root to it, according to André Weil.2011-04-02
  • 0
    Or any book on elementary number theory.2011-04-02