Patent ID: 9148282
Filing Date: 2015-09-29
Classification: G06F,H04L

Abstract:
1. A method of computing a square root of an element q of a prime finite field, the method comprising: determining a value of a finite field element t yielding an initial value P=q*t*t−2 such that P−2 is not a quadratic residue, wherein P is an initial parameter of a Lucas function; calculating a factored representation of (p−1)/4, the factored representation consisting of a set of factors that, when multiplied together, yield (p−1)/4, wherein p is a characteristic of the prime finite field on which coordinates of an elliptic curve are defined; calculating a value of the Lucas function of P for one of the factors of the set of factors; setting P to the computed Lucas function value; computing a Lucas function value of P for another factor of the set of factors; repeating the setting and computing steps for all remaining factors of the set of factors in the factored representation of (p−1)/4 to generate a final Lucas function value; outputting the square root of the finite field element q, the square root being calculated as the final Lucas function value divided by the element t; and using the square root of the finite field element q in at least one digital signature cryptographic application.