A=x^b mod p, solvable?

  • Thread starter Chu
  • Start date
  • #1
Chu
10
0
Say you are given a=x^b mod p, where p, a, and b are known. Is there a way to solve this? I am pretty sure there is . . . but it is driving me nuts.

-Chu
 

Answers and Replies

  • #2
695
0
Try solving x^2 = 2 (mod 3).
 
  • #3
Chu
10
0
Muzza said:
Try solving x^2 = 2 (mod 3).

Sorry, I'll rephrase. I know a solution must exist from the choices of p,b,and a (this is part of a crypto algorithm where they know x, I do not, and I am wondering if I have sufficent info to solve for it).
 
  • #4
matt grime
Science Advisor
Homework Helper
9,420
4
You can of course solve it - all one needs is to raise every remainder to the b'th power. However, I don't think there is a better solution except in certain circumstances.

obviously b must divide [tex]\varphi(x)[/tex], but that doesn't give a sufficient condition for a solution, or even tell you what it is.

The reason for my scepticism is that it is a well known and difficult problem to find generators of the group of units mod a prime (which is a cyclic group).
 

Related Threads on A=x^b mod p, solvable?

  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
7
Views
8K
  • Last Post
Replies
8
Views
4K
  • Last Post
Replies
1
Views
2K
Replies
12
Views
7K
Replies
5
Views
7K
  • Last Post
Replies
3
Views
6K
Replies
5
Views
4K
  • Last Post
Replies
4
Views
7K
Replies
2
Views
266
Top