arvind@utcsri.UUCP (09/16/87)
Date: Mon, 14 Sep 87 11:48:03 +0200
From: brassard@cwi.nl (Gilles Brassard)
Subject: Fermat vs Rabin false witnesses
I need the following result in a paper that I am
currently revising. Although I have a proof (largely due
to an anonymous referee), it would save me substantial
typesetting effort if I could simply quote a reference
where this has already been proved (if this is so).
My question is: Is the following already known and,
if so, what is the best reference to it ?
Theorem: Consider any odd composite integer which is not
a prime power. It has at least twice as many
Fermat false witnesses of primality than it
has Rabin (i.e.: strong) false witnesses.
Thank you in advance.
- Gilles Brassard