mersenneforum.org Pseudo-Prime Bases
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-02, 03:09 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 26·31 Posts Pseudo-Prime Bases Hi all, Is there a systematic method (other than brute force) to find a base whereby a given composite n will yield a false positive in FLT testing, other than n+1 and n-1 ? Does such a base exist for any given composite? Are such Bases finite in number? Thank you in advance. Last fiddled with by a1call on 2018-01-02 at 03:11
2018-01-02, 03:52   #2
axn

Jun 2003

23×607 Posts

Quote:
 Originally Posted by a1call Does such a base exist for any given composite?
Excluding even numbers and powers of 3, the answer seem to be yes.

 2018-01-02, 04:15 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 111110000002 Posts Thank you for the insight axn. Re: My 2nd question, well it certainly can't be infinite unless bases greater than n are considered. So a mute question I can see.
2018-01-02, 06:03   #4
CRGreathouse

Aug 2006

22×1,493 Posts

Does "FLT testing" mean the Fermat probable-prime test? I'll assume this below, otherwise please clarify the term.

Quote:
 Originally Posted by a1call Is there a systematic method (other than brute force) to find a base whereby a given composite n will yield a false positive in FLT testing, other than n+1 and n-1 ?
I don't know of one offhand, but I expect there is a method, at least if you have the factorization of n.

Quote:
 Originally Posted by a1call Does such a base exist for any given composite?
If
$n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$
(with p1 < p2 < ... < pk and all exponents positive integers) then there are
$\prod_{i=1}^k \gcd(p_i-1, n-1)$
bases to which n is a pseudoprime. This fits axn's comment pretty well: it's easy to see that only prime powers could have the minimum 2 bases, and p - 1 divides p^e - 1 so only powers of 3 work.

Quote:
 Originally Posted by a1call Are such Bases finite in number?
As you pointed out, this question is moot -- there are only finitely many choices unless you count integers rather than integers mod n.

 Similar Threads Thread Thread Starter Forum Replies Last Post clowns789 Miscellaneous Math 3 2016-06-07 04:01 storflyt32 storflyt32 81 2015-04-22 16:06 ColdFury Math 4 2007-05-29 21:30 Uncwilly Math 10 2006-11-22 18:27 tnerual Sierpinski/Riesel Base 5 14 2006-11-04 08:00

All times are UTC. The time now is 01:58.

Mon Mar 1 01:58:20 UTC 2021 up 87 days, 22:09, 0 users, load averages: 1.87, 2.02, 2.34