Do one-way functions have to be polynomial in input bit length, or is the relative difficulty of an inverse more important?

49 Views Asked by At

Wikipedia defines it as being a polynomial function, but I'm looking for a clarification.

Specifically, there was a candidate for a OWF I was thinking about, but it relies heavily on taking the greatest prime factor of numbers around size $2^n$, if $n$ is the number of bits in an input bitstring. Since factorization is not a polynomial-time operation, I would guess this is disqualifying.

However, it seems likely that it would still be one-way in the sense that any inverse algorithm would generally have no other choice but to brute-force it, meaning it would ostensibly take $2^t$ time to "undo", if it takes $t$ time to run once. So, relatively speaking, it would arguably accomplish the goal of a one-way function, and thus my question.