  Rabi and Sherman [RS97,RS93] proved that the hardness of factoring is a
sufficient condition for there to exist one-way functions (i.e., p-time
computable, honest, p-time noninvertible functions; this paper is in the
worst-case model, not the average-case model) that are total, commutative, and
associative but not strongly noninvertible. In this paper we improve the
sufficient condition to ``P does not equal NP.''
  More generally, in this paper we completely characterize which types of
one-way functions stand or fall together with (plain) one-way
functions--equivalently, stand or fall together with P not equaling NP. We look
at the four attributes used in Rabi and Sherman's seminal work on algebraic
properties of one-way functions (see [RS97,RS93]) and subsequent
papers--strongness (of noninvertibility), totality, commutativity, and
associativity--and for each attribute, we allow it to be required to hold,
required to fail, or ``don't care.'' In this categorization there are 3^4 = 81
potential types of one-way functions. We prove that each of these 81
feature-laden types stand or fall together with the existence of (plain)
one-way functions.
