mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-01-02, 03:09   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default 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
a1call is offline   Reply With Quote
Old 2018-01-02, 03:52   #2
axn
 
axn's Avatar
 
Jun 2003

23×607 Posts
Default

Quote:
Originally Posted by a1call View Post
Does such a base exist for any given composite?
Excluding even numbers and powers of 3, the answer seem to be yes.
axn is offline   Reply With Quote
Old 2018-01-02, 04:15   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

111110000002 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-01-02, 06:03   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×1,493 Posts
Default

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

Quote:
Originally Posted by a1call View Post
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 View Post
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(Pseudo)-Mathematics in Economics clowns789 Miscellaneous Math 3 2016-06-07 04:01
Pseudo-mathematical gibberings (volume 9a) storflyt32 storflyt32 81 2015-04-22 16:06
Pseudo-random maps over an elliptic curve ColdFury Math 4 2007-05-29 21:30
"Prime in all bases"? Uncwilly Math 10 2006-11-22 18:27
pseudo reservation of a k ... 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.