Abstract A new algorithm for generating k-ary M sequences is given. Not the classical method that the main cycle is extended by joining to it one cycle but a new method that the main cycle is exended by joining to it a subset of cycles is used in the algorithm. The algorithm reduces the time of choosing bridging states, and accelerates the speed of joining cycles.