Strong pseudoprime

From Citizendium, the Citizens' Compendium

Jump to: navigation, search


This article is developing and not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
 
http://en.citizendium.org/wiki?title=Strong_pseudoprime&printable=yes
This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

A strong pseudoprime is an Euler pseudoprime with a special property:

A composite number \scriptstyle q = d\cdot 2^s + 1 (where \scriptstyle d\ is odd) is a strong pseudoprime to a base \scriptstyle a\ if:

  • a^d \equiv 1 \pmod{q}
or
  • a^{d\cdot 2^r} \equiv -1 \pmod{q} if 0\le r < s-1

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 \scriptstyle q\ is pseudoprime to a base \scriptstyle a\ in \scriptstyle a^d \equiv 1 \pmod{q}, than \scriptstyle q\ is pseudoprime to a base \scriptstyle a' = q-a\ in \scriptstyle a'^d \equiv -1 \pmod{q} and vice versa.
  • There exist Carmichael numbers that are also strong pseudoprimes.

Further reading

Links

Retrieved from "http://en.citizendium.org/wiki/Strong_pseudoprime"
Views
Personal tools