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).
-
2$\begingroup$ If $k$ is small enough, you can simply take the gcd of your number and the product of the primes $< k$. $\endgroup$– Robert IsraelOct 1, 2017 at 21:45
-
$\begingroup$ Thanks Robert, I added a clarification that I'm looking for methods that have better big-O than factoring. $\endgroup$– JeremyOct 1, 2017 at 21:55
-
3$\begingroup$ Robert's remark still stands, if $k$ is small enough. At the other extreme, if $k$ exceeds the square root of the number in question, then determining $k$-roughness is the same as determining primality. So the question really depends on what kind of $k$ you have in mind. $\endgroup$– Gerry MyersonOct 1, 2017 at 22:06
-
1$\begingroup$ Once I was told that the opposite of "smooth" was "chunky" (cf. peanut butter)... $\endgroup$– post.as.a.guestOct 1, 2017 at 22:49
-
1$\begingroup$ As far as the statistical side goes, Tenenbaum's book has an entire chapter (III.6) on the distribution of rough numbers-you should definitely check it out. $\endgroup$– user41593Oct 2, 2017 at 10:14
2 Answers
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) 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 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, 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.
-
$\begingroup$ The link for GNFS isn't working right. Anyone know what's the problem? $\endgroup$ Oct 2, 2017 at 13:11
For a given specific composite, I do not know what can be said. For locating such numbers inside intervals of various lengths, some of what I know follows.
Let p be the product of all the primes which are at most k. The k-rough numbers are those coprime to p, and one can calculate their frequency (over large intervals) precisely: there are close to $\phi(p)/p$ fraction of these rough numbers in a large interval. Large interval has length a sizeable fraction of p. For smaller lengths, more uncertainty develops. It is conjectured that there is a rough number inside every interval of size $j\log^\alpha(j)$ where $j=\pi(k)$ and $\alpha$ is a fixed real number greater than 2. Bounds by Iwaniec put an upper bound on interval length of $O((j\log j)^2))$, and for large $j$ one has an explicit upper bound of $j^{3.81\log \log j}$.
There are at most $j!$ of these rough-free intervals of exceptional largest length inside an interval of length p, while on average one expects a rough number occurring out of every log(k) numbers otherwise.
Gerhard "See Question 37679 For More" Paseman, 2017.10.01
