Algorithm 7: Generating Algorithm for Public Key without Noises
· Let
d i ( x ) = ∏ j = 1 j ≠ i m ( x n − 1 + q j ) , 1 ≤ i ≤ m .
Since polynomial x n − 1 + q i and x n − 1 + q j ( j ≠ i ) are relatively prime in ℤ [ x ] / 〈 ϕ ( x ) 〉 , it follows that ( x n − 1 + q i , d i ( x ) ) = 1 . Therefore, there is a polynomial D i ( x ) such that
d i ( x ) D i ( x ) ≡ 1 ( mod ( x n − 1 + q i ) ) .
We obtain D i = τ ( D i ( x ) ) under the mapping τ given in section 2.