Computer-based verification of modular corrections of multiple linear operations in parallel

A computer system for generating test data for verifying a modular correction of a modular multiplication, comprising:

• one or more processors, one or more computer-readable memories, one or more computer-readable tangible storage devices, and program instructions stored on at least one of the one or more storage devices for execution by at least one of the one or more processors via at least one of the one or more memories, wherein the computer system is capable of performing a method comprising:
• selecting, by the one or more processors, two adjacent intervals of an intermediate result obtained from a coarse-grained modular correction on a binary multiplication of two operands A, B and defining a sub-interval closely around a boundary between the selected adjacent intervals, wherein the intermediate result is within a range CR smaller than P{circumflex over ( )}2, with P being a prime number used as modulus for the modular multiplication;
• selecting, by the one or more processors, a value V in the sub-interval;
• using, by the one or more processors, a first factorization algorithm for the value V for determining operands A′, B′, wherein the modular multiplication result R′ of the operands A′ and B′ corrected by the coarse-grained correction is in the sub-interval;
• repeatedly determining, by the one or more processors, A′ plus varying ε-values as A″ values;
• and
• determining, by the one or more processors, B″ values so that the modular multiplication corrected by the coarse-grained correction is in the sub-interval, thereby generating a test operand data A″ and B″.

A computer program product for generating test data for verifying a modular correction of a modular multiplication, comprising:

• one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising:
• program instructions to select, by the one or more processors, two adjacent intervals of an intermediate result obtained from a coarse-grained modular correction on a binary multiplication of two operands A, B and defining a sub-interval closely around a boundary between the selected adjacent intervals, wherein the intermediate result is within a range CR smaller than P{circumflex over ( )}2, with P being a prime number used as modulus for the modular multiplication;
• program instructions to select, by the one or more processors, a value V in the sub-interval;
• program instructions to use, by the one or more processors, a first factorization algorithm for the value V for determining operands A′, B′, wherein the modular multiplication result R′ of the operands A′ and B′ corrected by the coarse-grained correction is in the sub-interval;
• program instructions to repeatedly determine, by the one or more processors, A′ plus varying ε-values as A″ values;
• and
• program instructions to determine, by the one or more processors, B″ values so that the modular multiplication corrected by the coarse-grained correction is in the sub-interval, thereby generating a test operand data A″ and B″.