#cryptography

A one-way function is a function $f$ that can be computed in polynomial time, but such that every probabilistic polynomial-time algorithm, given $f(x)$ for a uniformly random $x$, finds some preimage of $f(x)$ only with negligible probability. Prove or disprove that one-way functions exist.

Given an integer $N$ with $b$ bits, find its prime factorization. Is there a classical (non-quantum) algorithm that does this in time polynomial in $b$?