Abstract: First, we introduced the concept of the nondeterministic public key cryptography (PKC) and decryption success rate (DSR),
 and gave its implementation scheme NHFMS based on the difficulty of the multivariate problem over finite field
. Then， we analyzed the number of nonsingular matrices in F_q［M］ and deduced the accurate counting formula of nonsingular matrices in F_q［M］ by using Euler-φ_q function. The results show that the method can not only accurately estimate the DSR of any specific instance of NHFSM, but also deduce the the lower limit of DSR of NHFSM scheme, which theoretically proves the feasibility of NHFMS. By using NHFSM scheme, the session key can be agreed, thus secure communication can be realized.

Key words: nondeterministic PKC(NPKC), deterministic PKC(DPKC), decryption success rate(DSR), Euler-φ_q function, N-HFMS