Presentation	2002/11/8 A Conjecture on the Trial Number of the Miller-Rabin Probabilistic Primality Test Kyoki IMAMURA,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	The Miller-Rabin probabilistic primality test is useful for finding large primes necessary for public key cryptography. For an odd composite n, an integer b in (1, n-1) is called a witness of n if b is coprime to n and n is a strong pseudoprime to the base b. It is known that at least three fourths of integers in (1, n-1) are witnesses of n. We will present a following conjecture on the upper bound of the minimum witness of n: Let k be the least integer greater than or equal to log n/log 4. Let PRIME(k) be the set of the smallest k primes. If n is composite, then there exists a witness of n in the set PRIME(k).
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Miller-Rabin probabilistic primality test / witness of an odd composite / a conjecture on the upper bound of the minimum witness
Paper #	ISEC2002-88
Date of Issue

Conference Information
Committee	ISEC
Conference Date	2002/11/8(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Information Security (ISEC)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	A Conjecture on the Trial Number of the Miller-Rabin Probabilistic Primality Test
Sub Title (in English)
Keyword(1)	Miller-Rabin probabilistic primality test
Keyword(2)	witness of an odd composite
Keyword(3)	a conjecture on the upper bound of the minimum witness
1st Author's Name	Kyoki IMAMURA
1st Author's Affiliation	Faculty of Computer Science & Systems Engineering, Kyushu Institute of Technology()
Date	2002/11/8
Paper #	ISEC2002-88
Volume (vol)	vol.102
Number (no)	437
Page	pp.pp.-
#Pages	4
Date of Issue