Home » 2018 » October

Monthly Archives: October 2018

Algorithms for black box groups

CoDiMa partially supported the visit of Prof. Alexandre Borovik (University of Manchester) to Dr Sukru Yalcinkaya (Istanbul University) on 8-21 September 2018. They reported the following:

In this short period of very intensive work in a small group (A. Borovik, S. Yalcinkaya (Istanbul University), and M. Lavrauw (Sabanci University)) we achieved a significant further progress towards efficient algorithms for analysis of black box groups representing classical linear groups over finite fields of odd characteristic. These results are highly significant for probabilistic methods of computational group theory. Unlike much of the previously existed methods which were conditional on the existence of Discrete Logarithm Oracles, our algorithms run in time polynomial in input length, work for very large sizes of fields without use of oracles of any kind and have been successfully tested for prime fields of order about 10^70.