A Method for Distinguishing the Two Candidate Elliptic Curves in CM Method

摘要

In this paper, we first introduce a shift product-based polynomial transformation. Then, we show that the parities of (#.E - 1)/2 and (#E′ - 1)/2 are reciprocal to each other, where #E and #E′ are the orders of the two candidate curves obtained at the last step of CM method algorithm. Based on this property, we propose a method to check the parity by using the shift product-based polynomial transformation. For a 160-bits prime number as the characteristic, the proposed method carries out the parity check about 20 times faster than the conventional method when 4 divides the characteristic minus 1.