# Questions tagged [hard-problem]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
59 views

### How to prove which complexity class a problem belongs?

How to prove that a problem is computationally hard? For example, how to proved that the problem of integer factoring into two prime numbers is difficult? How to prove that the decoding problem of a ...
68 views

### Is permutation conjugate search problem many answer? Are there many answer equal?

If conjugate search problem of permutation is difficult , then there are next cryptosystem will appear. A=XYX−1,B=XZX−1,Y and Z are public key.And X is secret permutation. then encryption is C=...
91 views

### From the product of two permutation matrices raised to the same power, is it easy to find the power?

Let $A$ and $B$ be two public permutation matrices. If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?
Let $x$,$y$,$z$ be permutations. Then public key is $z=xyx^{−1}$ and $y$. Is permutation conjugate search problem easy? if yes, how to find $x$ from $z$ and $y$? Let be a is Alice's secret key as ...