Presentation	1997/9/12 Factoring problem in bounded arithmetic Mitsuru Tada,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	It is well-known that the set of all functions which are Σ^b_1-definable in S^1_2 is just equal to PF, the set of all functions which are polynomial-time computable. Any polynomial-time algorithms to find the primes p and q from the product pq are still unknown, that is, it is finitely difficult (perhaps impossible) for the theory S^1_2 to Σ^b_1-define that operation. But the theory S^1_2 with some axiom can Σ^b_1-define it. Although if the theory S^1_2 itself could prove the axiom, then RSA system would not be secure any longer, it is (fortunately or unfortunately) unlikely that S^1_2 can prove the axiom.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	bounded arithmetic / Σ^b_1-definable in S^1_2 / Pratt's definition of primality
Paper #	ISEC97-31
Date of Issue

Conference Information
Committee	ISEC
Conference Date	1997/9/12(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	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Factoring problem in bounded arithmetic
Sub Title (in English)
Keyword(1)	bounded arithmetic
Keyword(2)	Σ^b_1-definable in S^1_2
Keyword(3)	Pratt's definition of primality
1st Author's Name	Mitsuru Tada
1st Author's Affiliation	Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University()
Date	1997/9/12
Paper #	ISEC97-31
Volume (vol)	vol.97
Number (no)	252
Page	pp.pp.-
#Pages	12
Date of Issue