Probabilistic solutions of equations in the braid group.

DOI10.1016/J.AAM.2005.03.002MaRDI QIDQ817243zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5380256 (Why is no real title available?)
• scientific article; zbMATH DE number 1759777 (Why is no real title available?)
• A Practical Attack on Some Braid Group Based Cryptographic Primitives
• An algebraic method for public-key cryptography
• THE BRAID GROUP AND OTHER GROUPS

Cited in

(15)

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

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)