There are disclosed systems and methods for reducing the number of computations performed by a computing device constructing a public key from an implicit certificate associated with a certificate authority in an implicit certificate scheme. In one embodiment, the device first operates on the implicit certificate to derive an integer e. The device then derives a pair of integers (e1, e2) from the integer e, such that each of the pair of integers (e1, e2) has a bit length less than the bit length of the integer e, and such that the ratio of the pair of integers (e1, e2) corresponds to the integer e. The device then computes the public key by combining the integers e1 and e2 with public key contribution data derived from the implicit certificate and a public key of the certificate authority.