Strong pseudoprime: Difference between revisions
Jump to navigation
Jump to search
imported>Karsten Meyer m (→Properties) |
imported>Karsten Meyer |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | |||
A '''strong pseudoprime''' is an [[Euler pseudoprime]] with a special property: | |||
A composite number <math>\scriptstyle q = d\cdot 2^s + 1</math> (where <math>\scriptstyle d\ </math> is odd) is a strong pseudoprime to a base <math>\scriptstyle a\ </math> if: | |||
*<math>a^d \equiv 1 \pmod{q}</math> | *<math>a^d \equiv 1 \pmod{q}</math> | ||
| Line 7: | Line 9: | ||
*<math>a^{d\cdot 2^r} \equiv -1 \pmod{q}</math> if <math>0\le r < s-1</math> | *<math>a^{d\cdot 2^r} \equiv -1 \pmod{q}</math> if <math>0\le r < s-1</math> | ||
The first condition is stronger | The first condition is stronger. | ||
== Properties == | == Properties == | ||
*Every strong pseudoprime is also an Euler pseudoprime | *Every strong pseudoprime is also an Euler pseudoprime. | ||
*Every strong pseudoprime is odd, because every Euler pseudoprime is odd. | *Every strong pseudoprime is odd, because every Euler pseudoprime is odd. | ||
*If a strong pseudoprime <math>\scriptstyle q\ </math> is pseudoprime to a base <math>\scriptstyle a\ </math> in <math>\scriptstyle a^d \equiv 1 \pmod{q}</math>, than <math>\scriptstyle q\ </math> is pseudoprime to a base <math>\scriptstyle a' = q-a\ </math> in <math>\scriptstyle a'^d \equiv -1 \pmod{q}</math> and versa | *If a strong pseudoprime <math>\scriptstyle q\ </math> is pseudoprime to a base <math>\scriptstyle a\ </math> in <math>\scriptstyle a^d \equiv 1 \pmod{q}</math>, than <math>\scriptstyle q\ </math> is pseudoprime to a base <math>\scriptstyle a' = q-a\ </math> in <math>\scriptstyle a'^d \equiv -1 \pmod{q}</math> and vice versa. | ||
* | *There exist [[Carmichael number]]s that are also strong pseudoprimes. | ||
== Further reading == | == Further reading == | ||
* [[Richard E. Crandall]] and [[Carl Pomerance]]. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7 | * [[Richard E. Crandall]] and [[Carl Pomerance]]. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7 | ||
* [[ | * [[Paulo Ribenboim]]. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5 | ||
== Links == | == Links == | ||
* [http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_starke_Pseudoprimzahlen_(49_-_9999) Table of strong pseudoprimes between 49 and 1393] | * [http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_starke_Pseudoprimzahlen_(49_-_9999) Table of strong pseudoprimes between 49 and 1393] | ||
Latest revision as of 07:58, 15 June 2009
A strong pseudoprime is an Euler pseudoprime with a special property:
A composite number (where is odd) is a strong pseudoprime to a base if:
- or
- if
The first condition is stronger.
Properties
- Every strong pseudoprime is also an Euler pseudoprime.
- Every strong pseudoprime is odd, because every Euler pseudoprime is odd.
- If a strong pseudoprime is pseudoprime to a base in , than is pseudoprime to a base in and vice versa.
- There exist Carmichael numbers that are also strong pseudoprimes.
Further reading
- Richard E. Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7
- Paulo Ribenboim. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5