  Recently, there have been several progresses for the conjugacy search problem
(CSP) in Garside groups, especially in braid groups. All known algorithms for
solving this problem use a sort of exhaustive search in a particular finite set
such as the super summit set and the ultra summit set. Their complexities are
proportional to the size of the finite set, even when there exist very short
conjugating elements. However, ultra summit sets are very large in some cases
especially for reducible braids and periodic braids. Some possible approaches
to resolve this difficulty would be either to use different Garside structures
and Garside groups in order to get a sufficiently small ultra summit set, or to
develop an algorithm for finding a conjugating element faster than exhaustive
search. Using the former method, Birman, Gonz\'alez-Meneses and Gebhardt have
proposed a polynomial-time algorithm for the CSP for periodic braids.
  In this paper we study the conjugacy classes of periodic braids under the BKL
Garside structure, and show that we can solve the CSP for periodic braids in
polynomial time although their ultra summit sets are exponentially large. Our
algorithm describes how to connect two periodic braids in the (possibly
exponentially large) ultra summit set by applying partial cycling polynomially
many times.
