An efficient probabilistic algorithm for solving quadratic equation over finite fields
Toshiya Itoh · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1989
Abstract The probabilistic algorithm has a random procedure, which may or may not produce the solution, due to its randomness. By iterating the application, the desired solution can be produced with a high probability (unless the probability that the probabilistic algorithm produces the solution is very low). In 1980, Rabin proposed a probabilistic algorithm to solve a higher‐order equation over a finite field. When his algorithm is applied to the quadratic equation on a finite field, the probability that the desired solution is obtained by one application is 1/2, and the root can be determined by two times applications on the average. This paper proposes a probabilistic algorithm in which the probability that the desired solution is obtained by one application is kept as one‐half, and the quadratic equation over the finite field GF(p) (where p is an odd prime number) or GF(2m) is solved more efficiently than by Rabin's method. the proposed algorithm calculates the solution more efficiently than Rabin's method by determining the random parameter to be set in finding the solution, using a procedure which can efficiently be executed before calculation.