Cryptology ePrint Archive: Report 2008/124

A Simple Derivation for the Frobenius Pseudoprime Test

Daniel Loebenberger

Abstract: Probabilistic compositeness tests are of great practical importance in cryptography. Besides prominent tests (like the well-known Miller-Rabin test) there are tests that use Lucas-sequences for testing compositeness. One example is the so-called Frobenius test that has a very low error probability. Using a slight modification of the above mentioned Lucas sequences we present a simple derivation for the Frobenius pseudoprime test in the version proposed by Crandall and Pommerance.

Category / Keywords: foundations / primality testing

Date: received 17 Mar 2008

Contact author: daniel at bit uni-bonn de

Available formats: PDF | BibTeX Citation

Version: 20080317:212920 (All versions of this report)

Discussion forum: Show discussion | Start new discussion