Efficient recovering of operation tables of black box groups and rings
| dc.creator | Zumbragel, Jens | |
| dc.creator | Maze, Gerard | |
| dc.creator | Rosenthal, Joachim | |
| dc.date | 2008-05-05 | |
| dc.date.accessioned | 2026-07-07T09:37:03Z | |
| dc.date.available | 2026-07-07T09:37:03Z | |
| dc.description | People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation * on S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x*y of single pairs (x,y) you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x*y for all x,y in S? This problem can trivially be solved by using |S|^2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that * is an abelian group operation. We also investigate black box rings and give lower and upper bounds for the number of queries needed to solve product recovering in this case. | |
| dc.description | 5 pages | |
| dc.identifier | https://arxiv.org/abs/0805.0514 | |
| dc.identifier | http://arxiv.org/abs/0805.0514 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160325 | |
| dc.subject | Information Theory | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Group Theory | |
| dc.title | Efficient recovering of operation tables of black box groups and rings | |
| dc.type | text |