20090201, 20:11  #1 
Aug 2006
3^{2}·5·7·19 Posts 
Pseudoprimes
These are my semicoherent ramblings about various types of pseudoprimes. Feel free to post ideas, computational results, graphs, jeers, taunts, or whatever strikes your fancy.
Lehmer (1936) showed that there are Ω (log x) 2pseudoprimes up to x. (Rotkiewicz (1965) has a weaker but effective version showing that there is a 2pseudoprime between n and n^2 for n > 19.) Pomerance (1982) improved Lehmer's result to Ω(exp((log x)^{α})) for α = 5/14 = 0.35.... This result holds for any base, and even for strong pseudoprimes. Pomerance (1989) later improved this to α = 85/207 = 0.41...; I haven't looked over the proof carefully enough to determine if it also holds for strong pseudoprimes. The conjectured density of pseudoprimes is x^(1  log log log x/log log x), while x^(1  log log log x/2 log log x) is an upper bound due to Pomerance (according to A12 in Guy's UPNT). Has anyone made (or seen) a chart comparing these results to the distribution for small numbers? Sloane's A055550/A001567 (2Fermat pseudoprimes) and A001262/A055552 (2strong pseudoprimes) may help, as may http://oldweb.cecm.sfu.ca/pseudoprime/ . Lehmer, D. H., "On the converse of Fermat's theorem", American Mathematical Monthly 43 (1936), pp. 347354. Pomerance. C., "A new lower bound for the pseudoprime counting function", Illinois Journal of Mathematics 26:1 (1982), pp. 49. Pomerance. C., "Two methods in elementary analytic number theory", pp. 135161 in Number Theory and Applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989. Rotkiewicz A., "Sur les nombres pseudopremiers carrés." Elemente der Mathematik 20 (1965), pp. 3940. 
20090203, 17:21  #2 
Jun 2008
2^{3}×3^{2} Posts 
For the past 1.5 years, I've been working on and off to extend William Galway's work towards enumerating all 64bit pseudoprimes. The source of my interest in this is Jaeschke's paper (1993) on finding spsp limits and efficient bases. I figured it would be easier to generate a superset of weak Fermat pseudoprimes and thus filter the strong pseudoprimes afterwards, looking for the good bases for 64bit primality tests.
Status of this 'little' project: lots of work is already done, most notably:  calculated rho(q) for all 32 bit odd q, where rho(q) is least r such that q  2^r1  enumerated all sqrtn smooth pseudoprimes n (except a few nonsquarefree ones, which is a minor issue) The remaining work is mainly located in looking for small (~1e15) factors of small Mersennes (upto M(1e5)), which probably won't even reveal many new ones that are not already in Edgingtons data... I also want to put all of this in a nice clear web page, including a retrieval database. The project currently is in yet another deep winter sleep... If you/anyone else are interested however, perhaps even wanna help, we might pick it up again. 
20090203, 21:07  #3  
Aug 2006
5985_{10} Posts 
Quote:
I'm interested, and can probably help as well. 

20090204, 18:02  #4 
∂^{2}ω=0
Sep 2002
República de California
11627_{10} Posts 
For the benefit of readers who may be more familiar with the alternate definition (which lumps together true and false primes), what is meant by pseudoprime to base a here is a composite number n for which Fermat`s criterion a^{n1} == 1 (mod n) is satisfied.
 Interesting that you should (re)raise this subject just now, Charles  we would appear to have a convergence of common interests here. As it happens I've also been playing with pseudoprimes  so far mainly the base2 Fermat variety  for the past few months, in an attempt to replicate and (eventually) extend the work of Pomerance et al and Pinch. J.F., how deep have your enumerations of the various kinds of psp's you are studying gone to? Being recent to this area of inquiry, I was unaware of Galway's work  got a link to a pdf or webpage describing it? Cheers, Ernst 
20090204, 23:19  #5 
Jun 2008
110_{8} Posts 
@Ernst:
I have been restricting myself to base 2 Fermat, 64 bit (~1.84e19). Galway enumerated these ones upto 1e15, link: http://oldweb.cecm.sfu.ca/pseudoprime/ I've made some improvements on his algorithms, but the 64 bit psp enumeration is not quite finished. Now that Charles and you have shown interest, I'm more motivated to pick up the project once again :). When there's news, I'll post it here! 
20090205, 00:38  #6 
Aug 2006
3^{2}×5×7×19 Posts 
OK, so time for another dumb question. It's easy, with Jaeschke's paper and 64bit doubles, to implement a routine that decides if a 64bit number is prime or not. (Just check bases 2, 7, and 61.) The square of a 32bit number fits neatly inside 64 bits, so there's no problem.
But even given data on the 64bit pseudoprimes, how do you implement a fast primality test? Bignum libraries are usually fairly slow when working with only two (or four) limbs. Is there efficient 64 x 64 > 128 bit multiplication code 'out there', or do we roll our own? Or is there a better way to calculate a 64bit square than direct multiplication and reduction? Also, can we take advantage of extended precision (96bit?)? 
20090205, 00:44  #7 
∂^{2}ω=0
Sep 2002
República de California
7×11×151 Posts 
Many thanks for the link to Galway's page.
You say you're not up to 2^64 yet, but do you have psp(2) counts to 10^16 and 10^17, perchance? (And perhaps 10^18?) I'd be very interested in those numbers. @Charles: For products of lengths which are small multiples of the machine wordsize e.g. 64x64>128bit, 96x96>192bit I've found it pays to "roll one's own" widemul macros  I use such extensively in my Mersenne trialfactoring code. On 64bit hardware the 128product is just one (x86_64) or two (most 64bit RISCs) machine instructions  main thing is to try to schedule them in batches of 4 or more to hide the latency and to interleave them with other ops such as add/sub/shift/mask to keep as many of the hardware's functionality units busy as possible. Last fiddled with by ewmayer on 20090205 at 00:50 
20090205, 03:41  #8  
Aug 2006
1761_{16} Posts 
Quote:
I hope that once the counts are out the appropriate OEIS entries are updated. Quote:
Quote:
The importance of 64bit computing just doubled for me. 

20090205, 04:51  #9 
∂^{2}ω=0
Sep 2002
República de California
7·11·151 Posts 
Use the tarball posted in this thread  the 128bit mul macros are in imul_macro0.h .

20090205, 13:01  #10 
(loop (#_fork))
Feb 2006
Cambridge, England
6383_{10} Posts 
CRGreathouse wrote "It's easy, with Jaeschke's paper and 64bit doubles, to implement a routine that decides if a 64bit number is prime or not. (Just check bases 2, 7, and 61.) The square of a 32bit number fits neatly inside 64 bits, so there's no problem."
I assume you mean "if a 32bit number" there. Is it really quicker to check more than one base than to do a binary search against the 10403 ( http://www.research.att.com/~njas/sequences/b001567.txt ) 2pseudoprimes less than 2^32? 
20090205, 16:58  #11  
∂^{2}ω=0
Sep 2002
República de California
11627_{10} Posts 
Quote:
Aside: Note 10403 is an easy pseudoprime count to remember, via the "factorization mnemonic" 10403 = 101*103. Last fiddled with by ewmayer on 20090205 at 16:59 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pseudoprimes in special fields  devarajkandadai  Number Theory Discussion Group  7  20171206 01:46 
On generating Strong PseudoPrimes DataBase?  TheoryQuest1  Factoring  10  20160919 16:08 
Odd Fibonacci pseudoprimes  efeuvete  Math  7  20130526 11:24 