A k-rough number is a natural number whose *smallest* prime factor is >= k, basically in opposition to the notion of a smooth number. Clearly, it's trivially easy to generate a k-rough composite number: pick two large primes >= k and multiply them. However, given a specific large composite, short finding the smallest factor of it (or performing an operation with equivalent or worse big-O), can *anything* be said about it's roughness (even statistically?). I've been trying to find any literature examining such questions, and have come up short. Anyone know of any results or references? There is a great deal of literature regarding smoothness, but a number that is not smooth is not necessarily rough (i.e. a number may have many small factors and one large factor, making it neither smooth nor rough).



Determining if a number is k-rough without factoring
First of all, I don't think you should dismiss searching for a prime factor as a method for determining whether a number is $k$-rough. The [Elliptic Curve Method (ECM)](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization) is a prime factorization algorithm which is faster for finding small prime factors than large prime factors. According to a heuristic analysis it can find a prime factor $p$ in time $\exp (O (\sqrt {\log p \log \log p}))$. Therefore if it doesn't find a prime factor in time $\exp (O (\sqrt {\log k \log \log k}))$ then you can be reasonably certain the number is $k$-rough. I'm not sure what's the best you can do if you want rigorous results; the best I'm aware of is Strassen's deterministic factorization algorithm (described in [this paper](https://specfun.inria.fr/bostan//publications/BoGaSc07.pdf) after the heading "Main algorithmic ideas") which could show the number is $k$-rough in time $\tilde {O} (k^{1/2})$, but there might be better algorithms that are randomized but with a rigorous analysis.


Going the other direction, if you want to determine whether a specific number $n$ is $k$-rough (rather than just getting probabilistic information for $n$ sampled from some distribution) I highly doubt there are any algorithms to determine that which are more efficient than trying to factor $n$, precisely because such an algorithm would be useful for finding prime factorizations. If such an algorithm gave sharp answers for all $k$ then it could quickly reveal the smallest prime factor of $n$ through a divide-and-conquer algorithm. Even if it gave more rough information (for example, if its answers were not reliable whenever there is a prime between $k/2$ and $2k$) such an algorithm would still give order-of-magnitude information on the size of the smallest prime factor of $n$, which is still useful for factoring in the following ways:


* It could tell whether to try to factor $n$ with ECM or with the [General Number Field Sieve](https://en.wikipedia.org/wiki/General_number_field_sieve), whose runtime is independent of the size of the prime factors of $n$. It could also guide your choice of parameters for ECM.
* If you have multiple composite numbers $n\_0, \dots, n\_{i-1}$ that you would like to factor, it could tell you for which one you can find a prime factor most quickly.
* Although I'm not aware of any specific examples, it could reveal sensitive information about how $n$ was generated in a cryptographic protocol. Certainly I never heard anyone warning about such a method for people designing cryptographic protocols.


As far as I'm aware, the only things it is possible to determine about the prime factorization of a large number $n$ without using a factorization algorithm to find prime factors of $n$ is whether $n$ is prime and whether $n$ is a perfect power.


