Efficient prime-number check

A non-transitory computer-readable medium having instructions stored thereon, which, when implemented on a processing unit, cause the processing unit to perform a method for effectively checking within a data carrier whether a candidate value represents a prime number, for a cryptographic application performed on the data carrier, the data carrier being portable data carrier with limited computing power, the method comprising:

• generating the candidate value by a processor of the data carrier;
• storing the candidate value in a memory unit of the data carrier;
• carrying out a Fermat test by the processor of the data carrier, wherein the Fermat test includes a modular exponentiation of a base with an exponent (e) and a module (m), wherein the exponent (e) and the module (m) respectively depend on the candidate value to be checked, and wherein the modular exponentiation is executed by a coprocessor of the data carrier by employing Montgomery operations, a result of the Montgomery operations being output to the processor,
• wherein the modular exponentiation is expressible as a modular exponentiation with a positive and integer exponent and a base which is a fractional value with a power of two in the denominator,
• wherein the module (m) is identical with the candidate value to be checked, and
• wherein the exponent of the modular exponentiation is recoded, the recoded exponent (f) being the difference of a value dependent on a Montgomery parameter (R) and of the exponent (e) of the modular exponentiation.

A data carrier having at least one processor and at least one memory, wherein data carrier is configured to efficiently check whether a candidate value represents a prime number, for a cryptographic application performed on the data carrier, the data carrier being portable data carrier with limited computing power, wherein

• the processor of the data carrier is configured to generate the candidate;
• the memory stores the candidate value in a memory unit of the data carrier;
• the processor is configured to carry out a Fermat test, wherein the Fermat test includes a modular exponentiation of a base with an exponent (e) and a module (m), wherein the exponent (e) and the module (m) respectively depend on the candidate value to be checked,
• wherein the modular exponentiation is executed by a coprocessor of the data carrier by employing Montgomery operations, a result of the Montgomery operations being output to the processor,
• wherein the modular exponentiation is expressible as a modular exponentiation with a positive and integer exponent and a base which is a fractional value with a power of two in the denominator,
• wherein the module (m) is identical with the candidate value to be checked, and
• wherein the exponent of the modular exponentiation is recoded, the recoded exponent (f) being the difference of a value dependent on a Montgomery parameter (R) and of the exponent (e) of the modular exponentiation.