Find b from a=b^x mod x^2 given a,x,p,q

  • Thread starter vanvincent
  • Start date
In summary, to find b from a = b^x mod x^2, where a and x are known and prime factors p and q of x are also known, you can use an n-th root extraction algorithm and compute a unique solution by finding k such that a-kn^2 = b^n. However, this method may not take into account the known factors of x and a more efficient solution may need to be used.
  • #1
vanvincent
6
0
How to find b from a = b^x mod x^2, where a and x are known? prime factors p and q of x are also known.
 
Last edited:
Physics news on Phys.org
  • #2

 
  • #3
in modular arithmetic please!
 
  • #4
Use Euler's theorem.
 
  • #5
thanks dragonfall, i looked up the euler's theorem but i don't see how to apply it to my problem. could you please elaborate how? thanks!
 
  • #6
I'm sorry, I think I'm mistaken with Euler's theorem.

If then for some k which can be computed easily. Then you can use an n-th root extraction algorithm, without modular arithmetic.

But then I'm not using the fact that the factors of n are known, so maybe this isn't a good solution. Maybe I missed something.
 
  • #7
What I said above is an exponential algorithm, so please ignore it.
 
  • #8
Is there necessarily a unique solution, e.g. 0^6 = 6^6 mod 36
 

FAQ: Find b from a=b^x mod x^2 given a,x,p,q

What is the purpose of finding b from a=b^x mod x^2 given a,x,p,q?

The purpose of finding b from a=b^x mod x^2 given a,x,p,q is to solve for the unknown variable b in a congruence equation. This type of equation is commonly used in cryptography and number theory, and finding b allows for the solution of other related equations.

What is the equation for finding b from a=b^x mod x^2 given a,x,p,q?

The equation for finding b from a=b^x mod x^2 given a,x,p,q is b = a^((p-1)(q-1)/x) mod x^2. This equation is derived from Euler's theorem and the Chinese remainder theorem.

What is the significance of the variables p and q in the equation for finding b?

The variables p and q in the equation for finding b represent two distinct prime numbers that are used as the base for the modulus x^2. These numbers are typically large and randomly chosen to increase the security of the equation.

What is the role of x in the equation for finding b?

The variable x in the equation for finding b represents the exponent of the base b. It is an unknown value that must be determined in order to solve for b. This value is typically chosen to be a large prime number to increase the security of the equation.

How is this equation used in cryptography?

This equation is used in cryptography to generate public and private keys for secure communication. The value of b is used as the public key, while the values of p and q are kept secret as the private key. The recipient of the message can then use the equation to decrypt the message using the public key.

Similar threads

I Proof for subgroup -- How prove it is a subgroup of Z^m?
Replies
11
Views
2K
I via Wilson's theorem
Replies
2
Views
1K
I Question on Primitive Roots and GCDs
Replies
2
Views
2K
MHB Prove the polynomial f(x)=x^2-q is irreducible in F_p[x]?
Replies
1
Views
1K
I Understanding the Results of gcd(x,n)
Replies
8
Views
1K
I Show
Replies
4
Views
1K
MHB Show that the groups are abelian
Replies
1
Views
1K
I Generators of Galois group of
Replies
3
Views
2K
I Why prove Taylor's theorem with p(x)=q(x)−((b−a)^n/(b−x)^n)q(a)?
Replies
9
Views
2K
I Determining elements of Markov matrix from a known stationary vector
Replies
24
Views
2K

Hot Threads

Recent Insights

Back
Top