Efficient recovering of operation tables of black box groups and rings
Jens Zumbrägel, Gerard Maze, Joachim Rosenthal · 2008
People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation * : S times S rarr 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) isin S2you 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 isin S? This problem can trivially be solved by using |S|2queries 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 und upper bounds for the number of queries needed to solve product recovering in this case.