Tag: pseudoprimes

On Baillie-PSW pseudoprimes following Chen and Greene

Recently, I’ve been studying the 2003 paper of Chen and Greene “Some Comments on Baillie-PSW Pseudoprimes” published in the Fibonnacci Quarterly in 2003. I wish to make a record of my thinking about this problem, which is occasionally discussed online, for instance in this Mathematics Stack Exchange discssion thread: https://math.stackexchange.com/questions/2902592/isnt-the-estimate-for-the-smallest-counterexample-of-the-bpsw-test-far-too-opti . The problem studied by… Continue reading On Baillie-PSW pseudoprimes following Chen and Greene

Empirical Results on a Randomized Cubic Primality Test

In 1980, Baillie and Wagstaff proposed a novel primality test consisting of a strong Fermat base $2$ test and a standard or strong Lucas test (Baillie and Wagstaff, 1980). This test has come to be known as the Baillie-PSW test after the names of its creators, and is now commonly included in software for mathematics,… Continue reading Empirical Results on a Randomized Cubic Primality Test

Implementation of the Randomized Cubic Primality Test in Python

This post provides a complete, runnable Python implementation of the randomized cubic primality test using explicit Frobenius computation in a cubic ring, as described in my article “A Randomized Cubic Primality Test Using Explicit Frobenius Computation”. The test operates in the ring $$R_N = (\mathbb{Z}/N\mathbb{Z})[x]/(f(x)),\qquad f(x)=x^3-qx-q,$$ where $N$ is the integer under test and $q$… Continue reading Implementation of the Randomized Cubic Primality Test in Python

Cubic Frobenius test statistics from 1.0e13 to 2.0e13

For composites in the range 1.0e13 to 2.0e13, there are two instances of type 2 (passing Congruence 1 only) and no instances showing they passed either Congruence 2 or Congruence 3. For the primes in the range, they all pass congruences 1 to 5. Processing block 1000: 10999000000000 to 11000000000000Type 0: 233313317052Type 1: 0Type 2:… Continue reading Cubic Frobenius test statistics from 1.0e13 to 2.0e13

When might one expect a Fermat-Lucas pseudoprime?

The Baillie-PSW primality test consists of a strong Fermat base $2$ test and a standard or strong Lucas sequences test. For an odd number $n$, the Fermat base $2$ test consists in checking whether the congruence $2^{n-1} \equiv 1 \pmod n$. A composite $n$ that passes the Fermat base $2$ test is known as a… Continue reading When might one expect a Fermat-Lucas pseudoprime?

A naive implementation of Erdos’ Carmichael number construction

I’ve been reading some about the Erdos heuristic to construct Carmichael numbers, first described by Erdos in 1956. It is based on Korselt’s criterion, that N is a Carmichael number if N is composite, squarefree and such that if p|N, then (p-1)|(N-1). The best reference I’ve found to understand the basics of Erdos’s heuristic is… Continue reading A naive implementation of Erdos’ Carmichael number construction

Cubic Frobenius test statistics to $10^{11}$

I ran my latest prime-testing program, based on a cubic Frobenius test, on the numbers from 1 to $10^{11}$. Numbers in that range coprime to 30 are considered for testing. Given the input $n$, the program looks for the first polynomial $f_{i}$ such that $f_{i}$ is irreducible over $F_{n}$ , where $f_{i}$ is one of… Continue reading Cubic Frobenius test statistics to $10^{11}$

Sample output from my latest prime-testing program

Types 1, 2 and 4 each correspond to one of three conditions being met. Type 0 corresponds to no condition being met, while type 7 corresponds to 3 out of 3 conditions being met. Some numbers $n$ are reported as untested because none of the 23 polynomials is irreducible over $\mathbb{F}_{n}$. The data on numbers… Continue reading Sample output from my latest prime-testing program

A Perrin-like Primality Test with Five Congruences

The Perrin sequence is defined by $P(0)=3$, $P(1)=0$, $P(2)=2$ and the recurrence relation $P(n) = P(n-2) + P(n-3)$ for $n\gt 2$. The Perrin sequence has the property that, if $n$ is prime then $n|P(n)$. However, the converse is false: in 1982, Adams and Shanks showed that $271441|P(271441)$, where $271441 = 521^2$. In contrast to the… Continue reading A Perrin-like Primality Test with Five Congruences

Pseudoprimes from iterating f(x)=4x+1 starting with x=3

? count=0;for(W=1,5555130,for(Z=W,W, par=W;new=3;  for(X=1,par,new=4*new+1);if( ispseudoprime(new,1)  ,count=count+1;  print(W,” “,count,” “,round(log(new)/log(10)) ) )) )1 1 12 2 24 3 35 4 48 5 510 6 711 7 720 8 1332 9 2040 10 25131 11 79257 12 155263 13 159350 14 211448 15 270634 16 382725 17 437803 18 484832 19 5011769 20 10662363 21 14232548 22… Continue reading Pseudoprimes from iterating f(x)=4x+1 starting with x=3

Some Rabin-Miller pseudoprime primality tests (updated)

? m=55;s=m;for(X=1,6,s=s^4-s^2+1);print(m,” “,round(log(s)/log(10)))55 7128 ? ispseudoprime(s,30)%39 = 1 ? m=1948;s=m;for(X=1,6,s=s^4-s^2+1);print(m,” “,round(log(s)/log(10)))1948 13474 ? ispseudoprime(s,30)%40 = 1 ? m=3269;s=m;for(X=1,6,s=s^4-s^2+1);print(m,” “,round(log(s)/log(10)))3269 14395 ? ispseudoprime(s,30)%41 = 1 ? m=3981;s=m;for(X=1,6,s=s^4-s^2+1);print(m,” “,round(log(s)/log(10)))3981 14746 ? ispseudoprime(s,30)%42 = 1

Some Rabin-Miller pseudoprime primality tests

? m=55;s=m;for(X=1,6,s=s^4-s^2+1);print(m,” “,round(log(s)/log(10)))55 7128 ? ispseudoprime(s,30)%39 = 1 ? m=1948;s=m;for(X=1,6,s=s^4-s^2+1);print(m,” “,round(log(s)/log(10)))1948 13474 ? ispseudoprime(s,30)%40 = 1 ? m=3269;s=m;for(X=1,6,s=s^4-s^2+1);print(m,” “,round(log(s)/log(10)))3269 14395 ? ispseudoprime(s,30)…