PURPOSE: To provide the system for calculating square root over a finite field and the application device for the same for unnecessitating inverse calculation, reducing the amount of calculation and considerably shortening calculation time by deforming a calculation expression and performing a little preprocessing.
CONSTITUTION: When an odd prime number (p) and an integer (y) are given, this is a system for calculating the square root over a finite field having an odd prime number as a modules in which an integer (x) satisfying y=x2 (mod p) is determined. First, in preprocessing P11 and P12, a square non-remainder (g) on the finite field having (p) as the modules is calculated and held. In main processing S11, an odd number (a) and a positive integer (k) satisfying p=a.2k+1 concerning (p) are calculated and in main processing S12, an integer (t) satisfying (y.gt)a≡1 (mod p) is calculated. When (t) is an odd number, exceptional processing is performed by judging that there is no solution to the problem, and when (t) is an even number, the integer (x) calculated by x=±y(a+1)/2.gat/2 (mod p) is outputted in main processing S15.
JP5959661 | Numeric algorithm for nth root |
JPS6258333 | ARITHMETIC UNIT |
JP2792803 | [Title of Invention] Square Root Calculator Circuit |