mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2009-02-01, 20:11   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default 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.
CRGreathouse is offline   Reply With Quote
Old 2009-02-03, 17:21   #2
J.F.
 
J.F.'s Avatar
 
Jun 2008

23×32 Posts
Default

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.
J.F. is offline   Reply With Quote
Old 2009-02-03, 21:07   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

598510 Posts
Default

Quote:
Originally Posted by J.F. View Post
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. View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2009-02-04, 18:02   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1162710 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2009-02-04, 23:19   #5
J.F.
 
J.F.'s Avatar
 
Jun 2008

1108 Posts
Default

@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!
J.F. is offline   Reply With Quote
Old 2009-02-05, 00:38   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

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?)?
CRGreathouse is offline   Reply With Quote
Old 2009-02-05, 00:44   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

7×11×151 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2009-02-05, 03:41   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176116 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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 View Post
@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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2009-02-05, 04:51   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

7·11·151 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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 .
ewmayer is offline   Reply With Quote
Old 2009-02-05, 13:01   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

638310 Posts
Default

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?
fivemack is offline   Reply With Quote
Old 2009-02-05, 16:58   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1162710 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pseudoprimes in special fields devarajkandadai Number Theory Discussion Group 7 2017-12-06 01:46
On generating Strong PseudoPrimes DataBase? TheoryQuest1 Factoring 10 2016-09-19 16:08
Odd Fibonacci pseudoprimes 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.