Probabilistic solutions of equations in the braid group.

DOI10.1016/J.AAM.2005.03.002zbMATH Open1109.20029arXivmath/0404076OpenAlexW2051740264MaRDI QIDQ817243FDOQ817243

Authors: David Garber, Shmuel Kaplan, Mina Teicher, Boaz Tsaban, Uzi Vishne 

Publication date: 8 March 2006

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: Given a system of equations in a "random" finitely generated subgroup of the braid group, we show how to find a small ordered list of elements in the subgroup, which contains a solution to the equations with a significant probability. Moreover, with a significant probability, the solution will be the first in the list. This gives a probabilistic solution to: The conjugacy problem, the group membership problem, the shortest representation of an element, and other combinatorial group-theoretic problems in random subgroups of the braid group. We use a memory-based extension of the standard length-based approach, which in principle can be applied to any group admitting an efficient, reasonably behaving length function.

Full work available at URL: https://arxiv.org/abs/math/0404076

Recommendations

• Solving random equations in Garside groups using length functions.
• scientific article; zbMATH DE number 4006530
• A fast algorithm to the conjugacy problem on generic braids.
• A new algorithm for solving the word problem in braid groups
• Computer aided discovery of a fast algorithm for testing conjugacy in braid groups

zbMATH Keywords

length functionsconjugacy problemprobabilistic solutionssystems of equationsmembership problemrandom subgroupsfinitely generated subgroups of braid groupsshortest presentations of elements

Mathematics Subject Classification ID

Combinatorial probability (60C05) Generators, relations, and presentations of groups (20F05) Braid groups; Artin groups (20F36) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Probabilistic methods in group theory (20P05)

Cites Work

• An algebraic method for public-key cryptography
• A Practical Attack on Some Braid Group Based Cryptographic Primitives
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE BRAID GROUP AND OTHER GROUPS

Cited In (15)

• Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography
• New public key cryptosystems from combinatorial group theory
• An application of braid group theory to the finite time dead-core rate
• Affine braid groups: a better platform than braid groups for cryptology?
• Length-based cryptanalysis: the case of Thompson's group
• A note on the shifted conjugacy problem in braid groups.
• Groups with two generators having unsolvable word problem and presentations of Mihailova subgroups of braid groups
• Non-associative public-key cryptography
• Generalized learning problems and applications to non-commutative cryptography. (Extended abstract)
• A parallel evolutionary approach to solving systems of equations in polycyclic groups
• A nonlinear decomposition attack
• Solving random equations in Garside groups using length functions.
• Title not available (Why is that?)
• Evolution of group-theoretic cryptology attacks using hyper-heuristics
• The conjugacy search problem in public key cryptography: unnecessary and insufficient

This page was built for publication: Probabilistic solutions of equations in the braid group.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817243)