Maximal number of bases for which composite number is Fermat pseudoprime

In summary, composite numbers that are strong pseudoprimes to at most one quarter of all bases below n are discussed in the Wikipedia article. It is questioned whether Fermat pseudoprimes have a similar property and if it is known what the largest number of bases is for a composite n that is not a Carmichael number and is a Fermat pseudoprime. The number 2701 is mentioned as having about 48% pseudoprime bases and it is noted that for non-Carmichael numbers, the percentage of pseudoprime bases stays under 50%. It is also mentioned that for numbers close to 50%, there is typically another root of 1 (other than -1) that takes almost half of the results, and
  • #1
pedja
15
0
According to the Wikipedia article a composite number n is a strong pseudoprime to at most one quarter of all bases below n .

Do Fermat pseudoprimes have some similar property ? Is it known what is the largest number of bases for which composite n , that is not Carmichael number is Fermat pseudoprime ?
 
Physics news on Phys.org
  • #2
2701 does pretty well, at about 48% bases.
 
  • #3
Looks like it stays under 50% pseudoprime bases for non-Carmichaels. Typically for the close approaches to 50% there's another root of 1 (other than -1) which also takes almost half of the results. The multiples of the factors take a different value from the Fermat test of course.
 

1. What is a Fermat pseudoprime?

A Fermat pseudoprime is a composite number that passes the Fermat primality test, which states that if a^(n-1) ≡ 1 (mod n), then n is likely to be prime. However, not all Fermat pseudoprimes are actually prime numbers.

2. How is the maximal number of bases for which a composite number is a Fermat pseudoprime determined?

The maximal number of bases for which a composite number is a Fermat pseudoprime is determined by using the Miller-Rabin primality test. This test uses multiple bases to check if a number is a pseudoprime, making it more reliable than the Fermat test.

3. What is the significance of knowing the maximal number of bases for a Fermat pseudoprime?

Knowing the maximal number of bases for a Fermat pseudoprime allows us to have a better understanding of the probability that a composite number will pass the Fermat primality test. This information can be used in cryptographic algorithms to ensure the security of data.

4. Can a composite number be a Fermat pseudoprime for all bases?

No, a composite number cannot be a Fermat pseudoprime for all bases. The Miller-Rabin primality test has been proven to be correct for all bases, meaning that if a number passes this test for all bases, it is guaranteed to be a prime number.

5. Are there any known examples of composite numbers that are Fermat pseudoprimes for a large number of bases?

Yes, there are known examples of composite numbers that are Fermat pseudoprimes for a large number of bases. These numbers are known as strong pseudoprimes and they can pass the Fermat primality test for a large number of bases, making them more difficult to identify as composite numbers.

Similar threads

Replies
5
Views
2K
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
2K
Replies
1
Views
706
  • Linear and Abstract Algebra
Replies
1
Views
862
  • Quantum Interpretations and Foundations
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
7
Views
2K
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Back
Top