Number squaring computer-implemented method and apparatus

A system comprising:

• a processor;
• a communications channel coupled to the processor;
• a cryptographic module configured to be operated by the processor to encrypt messages for transmission on the channel and/or decrypt messages received on the channel, wherein the cryptographic module is configured to square a number x, represented as a t-digit vector, as part of an encryption or decryption, wherein to square a number x, the cryptographic module is configured to:
• store x in t b-bit registers of the processor;
• generate and store a 2t-digit intermediate vector in 2t b-bit registers of the processor, using x stored in said t b-bit registers;
• and
• shift a value stored in at least one of the t b-bit or 2t b-bit registers to the left by n, where n is an integer at least equal to 1;
• wherein w, square of the number x, is represented by the 2t-digit result vector stored in the 2t b-bit registers after the shift operation, and t and b are integers.

A non-transitory computer-readable medium having computer-readable code embodied therein, the computer-readable code comprising instructions configured to enable an apparatus, in response to execution of the instructions, to:

• receive input of a number x to be squared, wherein x is stored in t b-bit memory locations, x=x[0]+x[1]+x[2] . . . +x[t−1], wherein t is an integer;
• allocate 2t b-bit memory locations, w=w[0]+w[1]+w[2] . . . +w[2t−1], to store x squared, wherein b is an integer;
• for each integer i with 0≦i≦(t−2), perform the following operations:
• for each integer j with (i+1)≦j≦(t−1) perform the following operations:
• set w[i+j]=w[i+j]+(x[j]×x[i])low+u;
• set u=(x[j]×x[i])high+carry;
• set w[i+t]=u;
• set w=w<<1;
• wherein carry is a carry bit from a most recent add operation performed, and u is a register.

A non-transitory computer-readable medium having computer-readable code embodied therein, the computer-readable code comprising instructions configured to enable an apparatus, in response to execution of the instructions, to:

• receive input of a number x to be squared store a t-digit vector representation of x in t b-bit registers of a processor;
• generate and storing a 2t-digit intermediate vector in 2t b-bit registers of the processor, using x stored in said t b-bit registers;
• and
• shift a value stored in at least one of the t b-bit or 2t b-bit registers to the left by n, where n is an integer at least equal to 1;
• wherein w, square of the number x, is represented by the 2t-digit result vector stored in the 2t b-bit registers after said shifting, and t and b are integers.