Simple Remarks on Carmichael Numbers

Shigenori UCHIYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.1   pp.326-328
Publication Date: 2009/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.326
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Cryptography and Information Security
Keyword: 
Carmichael numbers,  primality test,  integer factoring,  Extended Riemann Hypothesis,  

Full Text: PDF(71.3KB)>>
Buy this Article




Summary: 
An odd composite number n for which an-1 ≡ 1 (mod n) for all integers a coprime to n is called a Carmichael number. This paper shows that some class of Carmichael numbers which have relatively large prime factors can be recognized in deterministic polynomial time under the assumption of the Extended Riemann Hypothesis (ERH). Also some related problems are discussed.