Computation method, computing device and computer program
AssigneeFujitsu Limited
InventorsKouichi Itoh, Kenji Mukaida
Life of this patent
Estimating the term…
Abstract
The computing device calculates an equivalence H0≡2m*k+1 (mod n) relating to a divisor n of 2m*k+1 (step A), computes an equivalence H≡2E(p, m, k) (mod n) of 2E(p, m, k) (mod n) from H0 by an REDC operation (step B), and performs a correction operation by H=REDC (H, G)n for g=2k*G(p, m, k) when 2p>m×k (step C).
Claims14
A computation method for computing a value relating to a Montgomery conversion parameter, which is used in a Montgomery multiplication remainder operation and is a remainder value relating to a divisor n of a remainder, using a register, which has at least m words that have a bit length k per 1 word, comprising the steps of:
- obtaining a negative number of n as an equivalence relating to a divisor n of 2m*k and storing the negative number in the register;
- repeating a process of performing one-bit shift of a value stored in the register in a carry direction and discarding a most significant bit which overflows the register until a most significant bit to be discarded becomes 0 to obtain an equivalence relating to a divisor n of 2m*k+1 and storing the equivalence in the register;
- and
- computing an equivalence which gives the same remainder value relating to a divisor n as a Montgomery conversion parameter by a Montgomery multiplication remainder operation based on a value stored in the register.
A computation method for computing a value relating to a Montgomery conversion parameter, which is used in a Montgomery multiplication remainder operation and is a remainder value relating to a divisor n of a remainder, using a register, which has at least m words that have a bit length k per 1 word and an operation unit for executing a Montgomery multiplication remainder operation REDC (A, B)n, which is defined as 2−m*k×A×B (mod n), for values A and B and a divisor n of a remainder having a significant word length m, comprising the steps of:
- storing a negative number of a divisor n of a remainder in the register;
- repeating a shift process of performing one-bit shift of a value stored in the register in a carry direction until a most significant bit which overflows the register becomes 0;
- repeating a process of executing a Montgomery multiplication remainder operation REDC (REG, REG)n for a value REG stored in the register by the operation unit and storing a result thereof in the register, p times which p is an integer that satisfies 2p−1<m×k≦2p;
- executing a Montgomery multiplication remainder operation REDC (REG, g)n for a value REG stored in the register by the operation unit and storing a result thereof in the register when 2p>m×k (here, g=2k*G(p, m, k) and G(p, m, k)=2×m−2p/k);
- and
- outputting a value stored in the register as an equivalence which gives the same remainder value relating to a divisor n as a Montgomery conversion parameter.
A computing device for computing a value relating to a Montgomery conversion parameter, which is used in a Montgomery multiplication remainder operation and is a remainder value relating to a divisor n of a remainder, comprising:
- a register;
- and
- a controller capable of performing operations of:
- storing a negative number of a divisor n of a remainder in the register;
- repeating a process of performing one-bit shift of a value stored in the register in a carry direction until a most significant bit which overflows the register becomes 0;
- and
- computing an equivalence which gives the same remainder value relating to a divisor n as a Montgomery conversion parameter by a Montgomery multiplication remainder operation based on a value stored in the register.
A computing device for computing a value relating to a Montgomery conversion parameter, which is used in a Montgomery multiplication remainder operation and is a remainder value relating to a divisor n of a remainder, comprising:
- a register which has at least m words that have a bit length k per 1 word;
- an operation unit for executing a Montgomery multiplication remainder operation REDC (A, B)n, which is defined as 2−m*k×A×B (mod n), for values A and B and a divisor n of a remainder having a significant word length m;
- and
- a controller capable of performing operations of:
- storing a negative number of a divisor n of a remainder in the register;
- repeating a shift process of performing one-bit shift of a value stored in the register in a carry direction until a most significant bit which overflows the register becomes 0;
- repeating a process of executing a Montgomery multiplication remainder operation REDC (REG, REG)n for a value REG stored in the register by the operation unit and storing a result thereof in the register, p times which p is an integer that satisfies 2p−1<m×k≦2p;
- executing a Montgomery multiplication remainder operation REDC (REG, g)n for a value REG stored in the register by the operation unit and storing a result thereof in the register when 2p>m×k (here, g=2k*G(p, m, k) and G(p, m, k)=2×m−2p/k);
- and
- outputting a value stored in the register as an equivalence which gives the same remainder value relating to a divisor n as a Montgomery conversion parameter.
A record medium for recording a computer program for causing a computer, which comprises a register that has at least m words having a bit length k per 1 word, to compute a value relating to a Montgomery conversion parameter, which is used in a Montgomery multiplication remainder operation and is a remainder value relating to a divisor n of a remainder, said computer program comprising the steps of:
- causing the computer to obtain a negative number of n as an equivalence relating to a divisor n of 2m*k and store the negative number in the register;
- causing the computer to repeat a process of performing one-bit shift of a value stored in the register in a carry direction and discarding a most significant bit which overflows the register until a most significant bit to be discarded becomes 0 to obtain an equivalence relating to a divisor n of 2m*k+1 and store the equivalence in the register;
- and
- causing the computer to compute an equivalence which gives the same remainder value relating to a divisor n as a Montgomery conversion parameter by a Montgomery multiplication remainder operation based on a value stored in the register.
A record medium for recording a computer program for causing a computer, which comprises a register that has at least m words having a bit length k per 1 word and an operation unit for executing a Montgomery multiplication remainder operation REDC (A, B)n that is defined as 2−m*k×A×B (mod n) for values A and B and a divisor n of a remainder having a significant word length m, to compute a value relating to a Montgomery conversion parameter, which is used in a Montgomery multiplication remainder operation and is a remainder value relating to a divisor n of a remainder, said computer program comprising the steps of:
- causing the computer to store a negative number of a divisor n of a remainder in the register;
- causing the computer to repeat a shift process of performing one-bit shift of a value stored in the register in a carry direction until a most significant bit which overflows the register becomes 0;
- causing the computer to repeat a process of executing a Montgomery multiplication remainder operation REDC (REG, REG)N for a value REG stored in the register by the operation unit and storing a result thereof in the register, p times which p is an integer that satisfies 2p−1<m×k≦2p;
- causing the computer to execute a Montgomery multiplication remainder operation REDC (REG, g)n for a value REG stored in the register by the operation unit and store a result thereof in the register when 2p>m×k (here, g=2k*G(p, m, k) and G(p, m, k)=2×m−2p/k);
- and
- causing the computer to output a value stored in the register as an equivalence which gives the same remainder value relating to a divisor n as a Montgomery conversion parameter.
Dependencies are inferred from the claim text.