Patent ID: 8903083

Claim:
A method for evaluating at a point r a plurality of polynomials p 1 (x), . . . , p i (x) of maximum degree up to n−1, where for every i the polynomial p i (x) has a degree of exactly t i −1, the method comprising: executing, by one or more processor devices in a computer system, program code stored in a memory of the computer system to cause the computer system to perform operations, the operations comprising: partitioning each polynomial p i (x) into a bottom half p i bot (x) consisting of bottom terms with lowest s i coefficients and a top half p i top (x) consisting of top terms with remaining t i −s i coefficients, where n and i are integers greater than zero, where for every i, t i and s i are integers greater than zero, where the partitioning is performed so that the top terms in the top half p i top (x) have degrees that are less than original degrees of original top terms by s i ; recursively partitioning the bottom half p i bot (x) and the top half p i top (x) of each polynomial p i (x) to obtain further terms having a lower degree than previous terms, where the recursive partitioning is performed until at least one condition is met at which point the recursive partitioning yields a plurality of partitioned terms, wherein recursively partitioning further comprises taking an available amount of memory into account, and stopping the recursive partitioning prior to completing the recursive partitioning to preserve memory space, wherein stopping recursion causes one or more partially partitioned terms; evaluating the bottom half p i bot (x) and the top half p i top (x) at the point r for each polynomial p i (x) by evaluating the plurality of partitioned terms at the point r and iteratively combining the evaluated partitioned terms, wherein evaluating further comprises, in response to p i (x) being stopped in the recursive partitioning, evaluating any partitioned terms and any partially partitioned terms at the point r and iteratively combining the evaluated partitioned terms and the evaluated partially partitioned terms; and evaluating each polynomial p i (x) at the point r by setting p i (r)=r s i p i top (r)+p i bot (r), wherein at least one bit of the evaluated polynomial p i (x) is used for encryption.