Sorry, an error occurred while loading the content.

## Pseudoprimes

Expand Messages
• How can the expected probability of primality for a pseudoprime of a specific base b in Fermat s Little Theorem be calculated? Julian Arni
Message 1 of 8 , Jul 29 11:22 AM
• 0 Attachment
How can the expected probability of primality for a pseudoprime of a
specific base b in Fermat's Little Theorem be calculated?
Julian Arni
• ... There are two ways that I can think of, neither is particularly satisfying. One is to simply look at example data, and use that as something upon which to
Message 2 of 8 , Jul 29 4:09 PM
• 0 Attachment
--- jka_br <jka_br@...> wrote:
> How can the expected probability of primality for a pseudoprime of
> a
> specific base b in Fermat's Little Theorem be calculated?

There are two ways that I can think of, neither is particularly
satisfying.

One is to simply look at example data, and use that as something upon
which to base heuristics.

Secondly, you could (maybe, I've not followed this train of thought
through) model PSPs of 2, 3, 4, etc factors, and work out the
probability of all of the individual residues for the factors being
correct. This path may lead to madness.

The third method is to follow all the references in the literature.
Probably papers by Jaeschke (that surely can't be the right spelling)
and Miller on this matter probably have some interesting leads.
References are available on Professor Caldwell's prime pages
http://primepages.org/ , under a section titled something along the
lines of 'how probable' in the context of probable/pseudo-primes.

Phil (thus proving 2=3)

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com
• Consider the possible values for smallest pseudoprime ( n ) to base n. ? foo(500) = [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 66,
Message 3 of 8 , Dec 17, 2002
• 0 Attachment
Consider the possible values for smallest pseudoprime
( > n ) to base n.

? foo(500)
= [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51,
55, 57, 63, 65, 66, 69, 75, 76, 77, 81, 85, 87, 91, 93,
95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124,
125, 129, 133, 135, 141, 143, 145, 147, 148, 153, 155,
159, 161, 165, 169,171, 172, 175, 177, 183, 185, 186,
187, 189, 190, 195, 196, 201, 203, 205, 207,
[snip]
339, 341, 343, 345, 351, 355, 357, etc. etc..
[snip]

How do I know if I've missed any values?
• ... Instant tangent, just add Phil: Noticable members of that list are 4, 9, 25, 49, 121, 169, ... and 27, 81 125, 343 ... Given that perfect-power testing can
Message 4 of 8 , Dec 17, 2002
• 0 Attachment
--- Max B <zen_ghost_floating@...> wrote:
>
> Consider the possible values for smallest pseudoprime
> ( > n ) to base n.
>
> ? foo(500)
> = [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51,
> 55, 57, 63, 65, 66, 69, 75, 76, 77, 81, 85, 87, 91, 93,
> 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124,
> 125, 129, 133, 135, 141, 143, 145, 147, 148, 153, 155,
> 159, 161, 165, 169,171, 172, 175, 177, 183, 185, 186,
> 187, 189, 190, 195, 196, 201, 203, 205, 207,
> [snip]
> 339, 341, 343, 345, 351, 355, 357, etc. etc..
> [snip]
>
> How do I know if I've missed any values?

Instant tangent, just add Phil:

Noticable members of that list are
4, 9, 25, 49, 121, 169, ...
and
27, 81 125, 343 ...

Given that perfect-power testing can be done in Bernsteinian linear time,
there are some who would say that they shouldn't even be passed to a
probable primality test.

However, it can't be denied that if you do pass them to such a PRP test
they do occasionally come out as pseudoprimes as indicated.

As you were,
Phil

=====
I Pledge Allegiance to the flag
That appears on my Desktop Startup Screen.
And to the Monopoly for which it Stands:
One Operating System over all, inescapable,
With Freedom and Privacy for none. -- Telecommando on /.

__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com
• ... Phil, that is very interesting, as is Bernstein s home/web/page http://cr.yp.to/djb.html which I had fun tripping out on for a couple of hours today. but
Message 5 of 8 , Dec 18, 2002
• 0 Attachment
>Noticable members of that list are
> 4, 9, 25, 49, 121, 169, ...
>and
> 27, 81 125, 343 ...
>
>Given that perfect-power testing can be done in
>Bernsteinian linear time, there are some who would say
>that they shouldn't even be passed to a probable
>primality test.

Phil, that is very interesting, as is Bernstein's home/web/page
http://cr.yp.to/djb.html
which I had fun tripping out on for a couple of hours
today. but what I am trying to find out is the limit I have
to compute up to before i know with certainty that all the
values below another lower limit are all included in the
aforementioned sequence, without excluding any possible
values. For example, would I have to compute up
to 10^6 to get the first 100 terms of the sequence correct
I wonder? Anyone know the theoretical/analytical
phantasmagoria behind this?

----- Original Message -----
From: Phil Carmody
Sent: Tuesday, December 17, 2002 10:37 AM
Subject: Re: [PrimeNumbers] Pseudoprimes

--- Max B <zen_ghost_floating@...> wrote:
>
> Consider the possible values for smallest pseudoprime
> ( > n ) to base n.
>
> ? foo(500)
> = [4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51,
> 55, 57, 63, 65, 66, 69, 75, 76, 77, 81, 85, 87, 91, 93,
> 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124,
> 125, 129, 133, 135, 141, 143, 145, 147, 148, 153, 155,
> 159, 161, 165, 169,171, 172, 175, 177, 183, 185, 186,
> 187, 189, 190, 195, 196, 201, 203, 205, 207,
> [snip]
> 339, 341, 343, 345, 351, 355, 357, etc. etc..
> [snip]
>
> How do I know if I've missed any values?

Instant tangent, just add Phil:

Noticable members of that list are
4, 9, 25, 49, 121, 169, ...
and
27, 81 125, 343 ...

Given that perfect-power testing can be done in Bernsteinian linear time,
there are some who would say that they shouldn't even be passed to a
probable primality test.

However, it can't be denied that if you do pass them to such a PRP test
they do occasionally come out as pseudoprimes as indicated.

As you were,
Phil

=====
I Pledge Allegiance to the flag
That appears on my Desktop Startup Screen.
And to the Monopoly for which it Stands:
One Operating System over all, inescapable,
With Freedom and Privacy for none. -- Telecommando on /.
• Hi folks, What should be done to a number to make sure the chance of it being pseudoprime or a Carmichael number is below the human scale of reasonable things
Message 6 of 8 , Apr 30, 2003
• 0 Attachment
Hi folks,

What should be done to a number to make sure the chance of it being
pseudoprime or a Carmichael number is below the human scale of reasonable
things to worry about?

In particular, are there any forms that are likely to be pseudoprime to
more than one base?

Thanks

Nathan
• ... reasonable ... pseudoprime to ... Maybe I can answer the first question. If the number is small and you have the time you could use Primo to prove the
Message 7 of 8 , Apr 30, 2003
• 0 Attachment
--- Nathan wrote:
> Hi folks,
>
> What should be done to a number to make sure the chance of it being
> pseudoprime or a Carmichael number is below the human scale of
reasonable
> things to worry about?
>
> In particular, are there any forms that are likely to be
pseudoprime to
> more than one base?
>

Maybe I can answer the first question.

If the number is small and you have the time you could use Primo to
prove the number prime thereby eliminate any doubt. If the number is
small (say less than 2000 bits) you could use the Miller-Rabin test
repeadedly -- decreasing the chance of it being a pseudoprime. PFGW
reports a Lucas test as well as a PRP if it can not prove the prime.
I would like to see a FFT-based Perrin composite test ;-)

Paul

> Thanks
>
> Nathan
• ... If you choose your numbers uniformly and at random from all integers of size N bits, then a single Miller-Rabin pseudoprimality test to a randomly chosen
Message 8 of 8 , May 1, 2003
• 0 Attachment
> From: Nathan Russell [mailto:nrussell@...]

> What should be done to a number to make sure the chance of it being
> pseudoprime or a Carmichael number is below the human scale
> of reasonable things to worry about?

If you choose your numbers uniformly and at random from all integers of size N bits, then a single Miller-Rabin pseudoprimality test to a randomly chosen base is sufficient. Only a very tiny fraction of integers have the property that a M-R test has a probability close to 1/4 of failing.

If you are allowed to chose your numbers in such a way that you guarantee it has close to a 1/4 chance of failing a test, pick a power of four sufficiently large that you find it comfortable. I personally don't worry much about things which occur with probability less than 4^(-20) in my expected lifetime.

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.