Strong pseudoprime - Revision history

Vipul: /* Definition */

2021-06-15T22:44:02Z

Definition

← Older revision		Revision as of 22:44, 15 June 2021
Line 6:		Line 6:
	Suppose <math>n</math> is an odd composite natural number and <math>a</math> is an integer relatively prime to <math>n</math>. We say that <math>n</math> is a '''strong pseudoprime''' (also called '''Miller-Rabin pseudoprime''', '''Rabin-Miller pseudoprime''', '''Miller-Rabin strong pseudoprime''', '''Rabin-Miller strong pseudoprime''') to base <math>a</math> if the following holds.		Suppose <math>n</math> is an odd composite natural number and <math>a</math> is an integer relatively prime to <math>n</math>. We say that <math>n</math> is a '''strong pseudoprime''' (also called '''Miller-Rabin pseudoprime''', '''Rabin-Miller pseudoprime''', '''Miller-Rabin strong pseudoprime''', '''Rabin-Miller strong pseudoprime''') to base <math>a</math> if the following holds.

	Write </math>n-1 = 2^k s</math> where <math>s</math> is odd and <math>k</math> is a nonnegative integer. Then, either one of these conditions should hold:		Write <math>n-1 = 2^k s</math> where <math>s</math> is odd and <math>k</math> is a nonnegative integer. Then, either one of these conditions should hold:

	* <math>a^s \equiv 1 \pmod n</math>.		* <math>a^s \equiv 1 \pmod n</math>.

Vipul at 23:46, 19 April 2009

2009-04-19T23:46:47Z

← Older revision		Revision as of 23:46, 19 April 2009
Line 1:		Line 1:
	{{base-relative pseudoprimality property\|		{{base-relative pseudoprimality property\|
	test fooled = Rabin-Miller ~~pseudoprimality~~ test}}		test fooled = Rabin-Miller primality test}}

	==Definition==		==Definition==

	Suppose <math>n</math> is an odd composite natural number and <math>a</math> is an integer relatively prime to <math>n</math>. We say that <math>n</math> is a '''strong pseudoprime''' to base <math>a</math> if the following holds.		Suppose <math>n</math> is an odd composite natural number and <math>a</math> is an integer relatively prime to <math>n</math>. We say that <math>n</math> is a '''strong pseudoprime''' (also called '''Miller-Rabin pseudoprime''', '''Rabin-Miller pseudoprime''', '''Miller-Rabin strong pseudoprime''', '''Rabin-Miller strong pseudoprime''') to base <math>a</math> if the following holds.

	Write </math>n-1 = 2^k s</math> where <math>s</math> is odd and <math>k</math> is a nonnegative integer. Then, either one of these conditions should hold:		Write </math>n-1 = 2^k s</math> where <math>s</math> is odd and <math>k</math> is a nonnegative integer. Then, either one of these conditions should hold:

Vipul: Created page with '{{base-relative pseudoprimality property| test fooled = Rabin-Miller pseudoprimality test}} ==Definition== Suppose $n$ is an odd composite natural number and $a...'$

2009-04-19T23:45:33Z

Created page with '{{base-relative pseudoprimality property| test fooled = Rabin-Miller pseudoprimality test}} ==Definition== Suppose <math>n</math> is an odd composite natural number and <math>a...'

New page

{{base-relative pseudoprimality property|
test fooled = Rabin-Miller pseudoprimality test}}

==Definition==

Suppose <math>n</math> is an odd composite natural number and <math>a</math> is an integer relatively prime to <math>n</math>. We say that <math>n</math> is a '''strong pseudoprime''' to base <math>a</math> if the following holds.

Write </math>n-1 = 2^k s</math> where <math>s</math> is odd and <math>k</math> is a nonnegative integer. Then, either one of these conditions should hold:

* <math>a^s \equiv 1 \pmod n</math>.
* <math>a^{n-1} \equiv 1 \pmod n</math>. Further, consider the smallest <math>l</math> for which <math>a^{2^ls} \equiv 1 \pmod n</math>. Then, <math>a^{2^{l-1}s} \equiv -1 \pmod n</math>. In other words, the last value before becoming <math>1</math> should be <math>-1</math>.

The name ''strong pseudoprime'' is because the above condition is satisfied for all primes, and is a particularly strong condition for which finding composite numbers is hard.

==Relation with other properties==

===Weaker properties===

* [[Stronger than::Euler pseudoprime]]
* [[Stronger than::Fermat pseudoprime]]

Strong pseudoprime - Revision history

Vipul: /* Definition */

Vipul at 23:46, 19 April 2009

Vipul: Created page with '{{base-relative pseudoprimality property| test fooled = Rabin-Miller pseudoprimality test}} ==Definition== Suppose n is an odd composite natural number and a...'

Vipul: Created page with '{{base-relative pseudoprimality property| test fooled = Rabin-Miller pseudoprimality test}} ==Definition== Suppose $n$ is an odd composite natural number and $a...'$