mersenneforum.org Pseudoprimes
 Register FAQ Search Today's Posts Mark Forums Read

 2009-02-01, 20:11 #1 CRGreathouse     Aug 2006 32·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) 2-pseudoprimes up to x. (Rotkiewicz (1965) has a weaker but effective version showing that there is a 2-pseudoprime 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 (2-Fermat pseudoprimes) and A001262/A055552 (2-strong 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. 347-354. Pomerance. C., "A new lower bound for the pseudoprime counting function", Illinois Journal of Mathematics 26:1 (1982), pp. 4-9. Pomerance. C., "Two methods in elementary analytic number theory", pp. 135-161 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. 39-40.
 2009-02-03, 17:21 #2 J.F.     Jun 2008 23×32 Posts For the past 1.5 years, I've been working on and off to extend William Galway's work towards enumerating all 64-bit 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 64-bit 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^r-1 - enumerated all sqrt-n smooth pseudoprimes n (except a few non-squarefree 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.
2009-02-03, 21:07   #3
CRGreathouse

Aug 2006

598510 Posts

Quote:
 Originally Posted by J.F. For the past 1.5 years, I've been working on and off to extend William Galway's work towards enumerating all 64-bit pseudoprimes. The source of my interest in this is Jaeschke's paper (1993) on finding spsp limits and efficient bases.
Good for you! I've always been interested in the process, but never got around to learning fast techniques for enumeration. (There are naive methods... but those are Not To Be Mentioned.) I have tried searching the Bleichenbacher and Galway lists for good bases to test, but unfortunately my program had a bug that undermined the results, and I never recoded to fix it.

Quote:
 Originally Posted by J.F. 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.
I'm interested, and can probably help as well.

 2009-02-04, 18:02 #4 ewmayer ∂2ω=0     Sep 2002 República de California 1162710 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 an-1 == 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 base-2 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
 2009-02-04, 23:19 #5 J.F.     Jun 2008 1108 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!
 2009-02-05, 00:38 #6 CRGreathouse     Aug 2006 32×5×7×19 Posts OK, so time for another dumb question. It's easy, with Jaeschke's paper and 64-bit doubles, to implement a routine that decides if a 64-bit number is prime or not. (Just check bases 2, 7, and 61.) The square of a 32-bit number fits neatly inside 64 bits, so there's no problem. But even given data on the 64-bit 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 64-bit square than direct multiplication and reduction? Also, can we take advantage of extended precision (96-bit?)?
 2009-02-05, 00:44 #7 ewmayer ∂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->128-bit, 96x96->192-bit I've found it pays to "roll one's own" wide-mul macros - I use such extensively in my Mersenne trial-factoring code. On 64-bit hardware the 128-product is just one (x86_64) or two (most 64-bit 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 2009-02-05 at 00:50
2009-02-05, 03:41   #8
CRGreathouse

Aug 2006

176116 Posts

Quote:
 Originally Posted by ewmayer 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.
I don't think he has those counts. He's enumerating them by type not size, so he'll have all the sqrt(n)-smooth ones to 2^64 before he has any of the sqrt(n)-rough ones, and so on.

I hope that once the counts are out the appropriate OEIS entries are updated.

Quote:
 Originally Posted by ewmayer @Charles: For products of lengths which are small multiples of the machine wordsize e.g. 64x64->128-bit, 96x96->192-bit I've found it pays to "roll one's own" wide-mul macros - I use such extensively in my Mersenne trial-factoring code.
That's in the Mlucas source? Let me look that up.

Quote:
 Originally Posted by ewmayer On 64-bit hardware the 128-product is just one (x86_64) or two (most 64-bit RISCs) machine instructions
Really? That's great! I'll have to look that up.

The importance of 64-bit computing just doubled for me.

2009-02-05, 04:51   #9
ewmayer
2ω=0

Sep 2002
República de California

7·11·151 Posts

Quote:
 Originally Posted by CRGreathouse That's in the Mlucas source? Let me look that up.
Use the tarball posted in this thread - the 128-bit mul macros are in imul_macro0.h .

 2009-02-05, 13:01 #10 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 638310 Posts CRGreathouse wrote "It's easy, with Jaeschke's paper and 64-bit doubles, to implement a routine that decides if a 64-bit number is prime or not. (Just check bases 2, 7, and 61.) The square of a 32-bit number fits neatly inside 64 bits, so there's no problem." I assume you mean "if a 32-bit 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 ) 2-pseudoprimes less than 2^32?
2009-02-05, 16:58   #11
ewmayer
2ω=0

Sep 2002
República de California

1162710 Posts

Quote:
 Originally Posted by fivemack I assume you mean "if a 32-bit 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 ) 2-pseudoprimes less than 2^32?
The latter method is what I use for my 32-bit-prime generating routine - the large table is perhaps offensive to the über-aesthetes out there, but having to do just a single base-2 PRP test is very quick.

Aside: Note 10403 is an easy pseudoprime count to remember, via the "factorization mnemonic" 10403 = 101*103.

Last fiddled with by ewmayer on 2009-02-05 at 16:59

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 7 2017-12-06 01:46 TheoryQuest1 Factoring 10 2016-09-19 16:08 efeuvete Math 7 2013-05-26 11:24

All times are UTC. The time now is 07:50.

Thu May 6 07:50:56 UTC 2021 up 28 days, 2:31, 0 users, load averages: 2.01, 1.76, 1.81