In spread spectrum based watermarking schemes, it is a challenging task to embed multiple bits of information into the host signal. M-ary modulation has been proposed as an effective approach to multibit watermarking. It has been proved that an M-ary modulation based watermarking system outperforms significantly a binary modulation based watermarking system. However, in the existing M-ary modulation based algorithms, the value of M is restricted to be less than 256, because as M increases, the computation workload for data extraction advances exponentially. In this paper, we propose an efficient M-ary modulation scheme, i.e., M-ary phase modulation, which reduces the computation in data extraction to a very low level. With this scheme, it is practical to implement an M-ary modulation based algorithm with a high value of M, e.g., M = 220. This is significant for a watermarking system, because it can either greatly increase the data capacity of a watermark given the necessary watermark robustness, or considerably improve the watermark robustness given the amount of information of the watermark. The superiority of the proposed scheme is verified by simulation results.