Lucas Pseudoprime Tests in Quadratic Fields

ISEF Category: Mathematics

Subcategory: Number Theory  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

Some prime tests can be fooled by composite numbers that act prime-like. That means a number can pass the test and still be fake. Your project asks when those false positives appear, and how a new sequence-based test catches them. That is a real number theory puzzle with clear data to collect.

What Is It?

A pseudoprime is a composite number that passes a test built to detect primes. Think of it like a fake ID that fools a scanner. In this project, the scanner is not the usual one. It uses Lucas-like sequences, which are number patterns built from a recurrence rule, like a chain where each term depends on earlier terms.

The twist is that the sequences live over quadratic fields, which are number systems made by adding square roots to the integers. That gives you extra structure to test. Composite-discriminant means the key parameter that shapes the sequence is itself composite, not prime-shaped. The project studies which composite numbers still slip through, then classifies the ones that behave like strong pseudoprimes under these tests.

Why This Is a Good Topic

This is a strong science fair topic because it is precise, testable, and tied to a real problem in computational number theory. You can generate candidate numbers, run the test rule, and compare which composites pass or fail. You also get a clean research question about patterns, not just one-off examples. A student can learn modular arithmetic, recurrence sequences, data analysis, and how mathematicians search for counterexamples.

Research Questions

• How does changing the composite discriminant affect the set of composite numbers that pass the Lucas-like test?
• What is the effect of the sequence parameters on the frequency of strong pseudoprimes?
• Does restricting to certain residue classes reduce the number of false positives?
• To what extent do pseudoprime counts follow a predictable pattern across increasing number ranges?
• Which families of composites are most likely to survive multiple sequence-based tests?
• How does the quadratic field choice change the strength of the test?

Basic Materials

• Laptop or desktop computer with internet access.
• Spreadsheet software such as Google Sheets or LibreOffice Calc.
• Python with a basic math library, or SageMath if available.
• List of candidate integers to test, generated from online tables or your own script.
• Notebook for tracking definitions, test rules, and counterexamples.
• Access to a number theory text or lecture notes for Lucas sequences and modular arithmetic.

Advanced Materials

• Computer with SageMath, PARI/GP, or Mathematica.
• Python with SymPy and NumPy.
• Access to published tables of pseudoprimes and Lucas pseudoprimes.
• Research articles on Lucas sequences over quadratic fields.
• Optional access to a university math library for peer-reviewed number theory sources.

Software & Tools

• Python: Runs scripts that generate candidates, apply the test, and count false positives.
• SageMath: Handles modular arithmetic, recurrence sequences, and symbolic number theory calculations.
• PARI/GP: Speeds up integer and algebraic number theory computations for large search ranges.
• Google Sheets: Organizes data and helps you sort, filter, and graph pseudoprime results.
• Overleaf: Lets you write your report in clean LaTeX if you want a math-heavy final paper.

Experiment Steps

1. Define the exact Lucas-like test you will study and write down the parameters you will vary.
2. Choose a search range for candidate integers and decide how you will label primes, composites, and pseudoprimes.
3. Build a computation plan that can apply the test to many numbers and store the outcomes in a table.
4. Select controls that compare your new test against a standard primality test or a simpler Lucas test.
5. Plan how you will summarize results by discriminant, residue class, or parameter family.
6. Decide which patterns count as a meaningful finding, such as a lower false-positive rate or a repeated counterexample family.

Common Pitfalls

• Using a small search range, which can make a pattern look real when it is only a fluke.
• Mixing up the sequence definition across different discriminants, which changes the test without warning.
• Labeling every composite that passes one check as a strong pseudoprime, which ignores the exact test conditions.
• Forgetting to separate prime inputs from composite inputs before counting false positives.
• Comparing result tables without normalizing by range size, which makes one family look better just because you tested more numbers.

What Makes This Competitive

A strong version of this project would not just list examples. It would compare whole families of discriminants, explain why some families produce more false positives, and back that up with clean computation. You would also improve the analysis with a careful count, a density estimate, or a search for a boundary where the pattern changes. That turns the project from a small demo into real exploratory number theory.

Project Variations

• Compare false-positive rates for different composite discriminants and test whether some families are much weaker than others.
• Focus on one residue class of integers and ask whether that class produces more strong pseudoprimes than random inputs.
• Replace the Lucas-like test with a related recurrence test and compare which one catches composites more reliably.

Learn More

• MIT OpenCourseWare: Search for number theory and abstract algebra course notes to review modular arithmetic, recurrences, and algebraic number fields.
• NIST Digital Library of Mathematical Functions: Use the site’s sequence and special function references for background on recurrence behavior.
• arXiv: Search for preprints on Lucas pseudoprimes, probable prime tests, and quadratic fields.
• MathWorld: Read concise entries on Lucas sequences, pseudoprimes, and quadratic fields for quick definitions.
• PubMed: Not relevant for the math itself, but useful only if you are also studying how people present computational reproducibility in research methods papers.