O desenvolvimento da criptografia, em especial a criptografia de chave assimétrica, foi fator determinante para o crescimento e popularização das redes de computadores. Foi responsável pela viabilização de demandas como comércio e correio eletrônicos, assinaturas e certificações digitais. O uso adequado de técnicas criptográficas requer o desenvolvimento de implementações eficientes que sejam capazes de serem executadas em diversos tipos de dispositivos, que cada vez mais se incorporam à vida das pessoas. A geração de chaves criptográficas, por exemplo, é uma operação não só crítica quanto à segurança, mas também de alto custo computacional no algoritmo RSA. Este trabalho tem como objetivo estudar técnicas para teste de primalidade, elemento que compõe o núcleo do processo de geração de chaves nesse algoritmo. É dado enfoque na implementação, otimização e análise de desempenho do Teste de Frobenius Quadrático Simplificado, um teste de primalidade de 2005 e pouco explorado. Os resultados atingidos são positivos quanto à viabilidade da redução do custo computacional da geração de números primos.