1
$\begingroup$

Is there a C/C++ library for Number Theory that helps generate a Strong PseudoPrimes w.r.t. an Input base.

I intend to test a Primality Testing Algorithm's performace stastically but I am struggling with a dataset of Strong PseudoPrimes and was unable to find one of Random Strong PseudoPrimes large enough.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I'm guessing you will want to be working with numbers larger than 64-bits, and so you probably want GMP (see this page). This library is used by much of the software that number theorists use. (Magma uses parts of it, and PARI/GP uses it too.)

Note that GMP has a built-in function that tests primality by running several Miller-Rabin tests. It doesn't have a function that allows you to specify the input base, but that could be easily created by copying part of the source code.

Finally, note that the website factordb.com maintains a list of numbers that pass a surprisingly large number of iterations of the Miller-Rabin test before failing one. This list might be useful to you, and Arnault (in "Constructing Carmichael Numbers Which are Strong Pseudoprimes to Several Bases") gave an example of a 397-digit composite number for which the smallest strong liar is is $307$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Prof. I am still struggling with the approach to generate large Strong Pseudoprimes. The way I am doing is: 1. Generate a random odd number 2. Test if its a strong Pseudoprime wrt. input base 3. If not keep incrementing it by 2 till we get a Strong PseudoPrime. 4. Repeat the process to get another Strong PseudoPrime. This is highly impractical to say the least as the numbers can be far apart. Is there a short cut I am missing ? $\endgroup$
    – TheoryQuest1
    Sep 16, 2016 at 15:47
  • 1
    $\begingroup$ It is quite likely that there is a short cut. If you only want spsp's for one base $a$, you could look for composite factors of $\Phi_{n}(a)$ that are relatively prime to $n$ (where $n$ is odd and $\Phi_{n}(x)$ is the $n$th cyclotomic polynomial). For example, $N = 407613774637837876811$ is an spsp to base 3 because it is a composite factor of $\Phi_{65}(3)$. $\endgroup$
    – Jeremy Rouse
    Sep 16, 2016 at 17:26
  • 1
    $\begingroup$ If you want multiple bases, you could search for $n = p(2p-1)$ where $p \equiv 3 \pmod{4}$ is prime and $2p-1$ is also prime. For such an $n$, one quarter of the bases $a$ will be strong liars, so your chances are good. $\endgroup$
    – Jeremy Rouse
    Sep 16, 2016 at 17:28
  • $\begingroup$ much thanks Prof. I got the second one. The first i have to get some background (my major is CS). $\endgroup$
    – TheoryQuest1
    Sep 16, 2016 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.