2
$\begingroup$

Recently I studied the braid group and conjugacy problem. It is believed that conjugacy problem is hard on braid group. My friend gave me an EXE file, and I use it for solving conjugacy problem, as an oracle. I dont know about braid group, very much. But, I want to test that file. I generated several random $z,x$ and computed $y=zxz^{-1}$. The answers of that oracle was correct for all of my inputs. I checked it for $n=5,10,20,30,...$. Elements of these groups are so large that I cant show them here. So I show an example for small value of $n$. For example: for $n=6$, I generated bellow values: $x= ( 5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 4, 3, 4, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5, 5, 4, 3, 2, 5, 4, 3, 5, 2, 5, 4, 2, 2, 1, 3, 3, 2, 1, 4, 3, 5, 3, 2, 1, 4, 3, 5, 5, 4, 3, 2, 1, 4, 3, 2, 3, 5, 3, 2, 1, 4, 3, 5, 4 )$

$y=(-5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, -1, -2, -3, -4, -5, -5, -4, -5, -3, -4, -5, -2, -3, -4, -5, 4, 3, 2, 4, 3, 4, 4, 3, 2, 1, 5, 4, 3, 2, 4, 3, 4, 3, 2, 1, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 4, 3, 1, 3, 3, 2, 1, 4, 3, 2, 5, 4, 4, 3, 2, 1, 3, 2, 5, 4, 3, 5, 4, 4, 3, 2, 1, 2, 5, 4, 3, 5, 4, 5, 4, 3, 2, 1, 2, 4, 3, 4, 5, 5, 4, 3, 2, 1, 4, 3, 2, 3, 5, 4, 5, 5, 4, 3, 2, 1, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 2, 3, 4, 4, 3, 2, 1, 2, 3, 5, 5, 4, 3, 2, 1, 4, 3, 5, 5, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 4, 3, 5, 3, 2, 1, 4, 3, 2, 3, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 4, 3, 2, 5, 4, 3, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 4, 1, 4, 3, 4, 4, 3, 5, 5, 4, 3, 2, 1, 4, 3, 5, 5, 4, 3, 2, 1, 2, 2, 1, 2, 3, 4, 1, 2, 4, 4, 3, 5, 3, 2, 1, 4, 3, 5, 3, 2, 1, 4, 3, 5, 3, 2, 1, 2, 5, 4, 3, 5, 4, 5, 4, 3, 2, 1, 4, 3, 2, 3, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 2, 3, 4, 1, 4, 3, 2, 3, 5, 4, 5, 2, 1, 3, 3, 2, 1, 2, 4, 4, 3, 2, 1, 3, 2, 4, 1, 4, 3, 2, 3, 5, 4, 5, 4, 3, 2, 1, 3, 2, 4, 4, 3, 2, 1, 5, 4, 3, 4, 1, 4, 3, 2, 4, 3, 4, 4, 3, 2, 3, 5, 3, 2, 4, 4, 3, 2, 1, 3, 4, 4, 3, 2, 5, 2, 1, 3, 5, 3, 2, 1, 2, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 4, 3, 5, 4, 4, 3, 2, 1, 3, 2, 3, 4, 4, 3, 2, 1, 2, 5, 1, 2, 3, 5, 5, 4, 3, 2 )$ and founded value for $z$ is: $z=(-5, -4, -5, -3, -4, -5, -2, -3, -4, -5, 4, 3, 2, 4, 3, 4, 4, 3, 2, 1, 5, 4, 3, 2, 4, 3, 4, 3, 2, 1, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 4, 3, 1, 3, 3, 2, 1, 4, 3, 2, 5, 4, 4, 3, 2, 1, 3, 2, 5, 4, 3, 5, 4, 4, 3, 2, 1, 2, 5, 4, 3, 5, 4, 5, 4, 3, 2, 1, 2, 4, 3, 4, 5, 5, 4, 3, 2, 1, 4, 3, 2, 3, 5, 4, 5, 5, 4, 3, 2, 1, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 2, 3, 4, 4, 3, 2, 1, 2, 3, 5, 5, 4, 3, 2, 1, 4, 3, 5, 5, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 1, 4, 3, 5, 3, 2, 1, 4, 3, 2, 3, 5, 4, 5, 5, 4, 3, 2, 1, 5, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 4, 3, 5, 5, 4, 3, 2, 3, 3, 2, 3, 3, 2, 4 )$

In this example, $(i,j)$ means $\sigma_i \sigma_j$. So, for example, $(1,1,2,-3,1)=\sigma_1^2 \sigma_2 \sigma_3^{-1} \sigma_1$.

Can you give me a $x,y$, where finding the $z$ be hard? I know that this problem is hard, but that oracle was able to answer all of my questions.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ It would appear quite likely that the conjugacy problem can be solved rather quickly -- perhaps polynomial time. For example, the paper arxiv.org/pdf/1112.0165.pdf describes a quadratic-time algorithm to determine if a braid is pseudo-anosov, periodic or reducible. That gets you much of the way to the result. $\endgroup$
    – Ryan Budney
    Commented Mar 14, 2017 at 4:19
  • $\begingroup$ @RyanBudney, That paper is very interesting for me. Is this means that cryptographic schemes which are based on conjugacy problem in braid groups are not reliable? $\endgroup$
    – Meysam Ghahramani
    Commented Mar 14, 2017 at 7:01
  • 5
    $\begingroup$ I was under the impression that, due to progress in theoretical results, the conjugacy problem in braid groups was abandoned several years ago as a serious candidate for cryptographic protocols. $\endgroup$
    – Derek Holt
    Commented Mar 14, 2017 at 11:14
  • $\begingroup$ @RyanBudney Is it accurate to call Calvez's algorithm quadratic? Is anything known about the effectiveness of the constant in the Masur-Minsky linear-conjugator bound? Otherwise it seems like the algorithm is quadratic in word-length for a fixed number of strands, but could blow up very quickly as the number of strands increases. $\endgroup$
    – dvitek
    Commented May 16, 2020 at 1:38

0

Reset to default

You must log in to answer this question.