Efficient recovering of operation tables of black box groups and rings

Details Efficient recovering of operation tables of black box groups and rings Efficient recovering of operation tables of black box groups and rings

2008-05-05

arxiv.org/abs/0805.0514v1

Computer Science

Information Theory

5 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Efficient recovering of operation tables of black box groups and rings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient recovering of operation tables of black box groups and rings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient recovering of operation tables of black box groups and rings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-208816