Many future electronic identity cards will be equipped with a contact-less interface. Analysts expect that a significant proportion of future mobile phones support Near Field Communication (NFC) technology. Thus, it is a reasonable approach to use the cell phone as mobile smart card terminal, which in particular supports the Password Authenticated Connection Establishment (PACE) protocol to ensure user consent and to protect the wireless interface between the mobile phone and the smart card. While there are efficient PACE implementations for smart cards, there does not seem to be an efficient and platform independent solution for mobile terminals. Therefore we provide a new implementation using the Java Micro Edition (Java ME), which is supported by almost all modern mobile phones. However, the benchmarks of our first, straightforward PACE implementation on an NFC-enabled mobile phone have shown that improvement is needed. In order to reach a user friendly performance we implemented an optimized version, which, as of now, is restricted to optimizations which can be realized using features of existing Java ME libraries. In the work at hand we present a review of the relevant algorithms and provide benchmarks of the corresponding arithmetic functions in different Java ME libraries. We discuss the different optimization approaches, introduce our optimized PACE implementation, and provide timings for a desktop PC and a mobile phone in comparison to the straightforward version. Finally, we investigate potential side channel attacks on the optimized implementation.