4
$\begingroup$

Let $N < 2^a$ be a positive integer chosen uniformly at random. Let $\tilde{N}$ be the result of removing from $N$ all its prime factors less than $2^b$. What is the probability that $\tilde{N}$ is composite and $\tilde{N} > 2^c$?

The problem is similar to Integers with a large smooth divisor with "smooth divisor" replaced by "rough composite divisor".

Motivation

I want to build the smallest-possible safe RSA modulus without a trusted party. A positive integer is a safe RSA modulus if, after removing all its prime factors less than 512 bits, it is composite and has size at least 2048 bits.

(That is we set $b=512$ and $c=2048$ in the above problem. The parameter $b=512$ protects against the ECM which has found primes of size up to 273 bits. The parameter $c=2048$ protects against the GNSF which factored numbers up to 768 bits.)

The strategy is to randomly sample several random numbers $N_1, ..., N_k$ and multiply them together. Each $N_i$ has some probability $p$ of being a safe RSA modulus so the product $N_1...N_k$ has probability $1 - (1-p)^k$ of being safe.

To choose $k$ appropriately I need a reasonably tight lower bound for $p$. (The above strategy of multiplying randomly chosen integers was pioneered by Thomas Sanders but he used a different—unnecessarily strict—definition of a safe RSA modulus.)

$\endgroup$
  • 3
    $\begingroup$ I'm trying to decide whether the smallest possible safe RSA modulus isn't, by definition, unsafe. $\endgroup$ – Gerry Myerson Jul 31 '18 at 23:35
  • $\begingroup$ Good question :) I've asked the crypto.stackexchange community and it seems I just need to increase the parameter sizes crypto.stackexchange.com/questions/61223/… $\endgroup$ – Randomblue Aug 1 '18 at 7:17
  • 2
    $\begingroup$ I meant, in the same way that the smallest uninteresting positive integer is pretty interesting.... $\endgroup$ – Gerry Myerson Aug 1 '18 at 7:25
  • 3
    $\begingroup$ (This should be a comment but I don't have 50 rep) For $p_1,\dots,p_k | n$, the quantities $\log \log p_1 < \dots < \log \log p_k$ behave like a poisson process with intensity 1 up until $\log \log n$. This heuristic might be too rough to give an accurate answer for $c = 2048$, but asymptotically, it should happen with probability $1$ if $\log a - \max \{ \log b, \log c \} \to +\infty$. $\endgroup$ – Phillip Harris Aug 2 '18 at 7:48
  • $\begingroup$ Would you mind fleshing out the calculations for a = 4096, b = 512, c = 2048? :) $\endgroup$ – Randomblue Aug 2 '18 at 10:00
2
+50
$\begingroup$

If $a/b$ is not too large, you can compute the probability using arguments as in the computation leading to the asymptotics for smooth numbers. In theory, you can compute for all $\beta, \gamma$ a real number $\rho$, such that $$ \#\{n\leq x: \tilde{n}>x^\gamma\} \sim \rho x, $$ where $\tilde{n}$ is $n$ divided by all prime divisors $p$ of $n$ satisfying $p\leq x^\beta$. Unless $(\beta, \gamma)$ are in some stupid range, e.g. $\gamma>1$, $\rho$ will be positive. Your range $a=4096, b=512, c=2048$ should be manageable, but might take days to weeks of work.

Let me explain the computations at the easier example $\beta=0.3$, $\gamma=0.7$.

All prime divisors of $\tilde{n}$ are larger than $x^{0.3}$, thus there are at most 3 of them. As you require that $\tilde{n}$ is composite, there are 2 or 3 prime factors. Suppose first there are exactly 2 of them. The number of integers $n<x$, such that $\tilde{n}=pq$ equals $\Psi(x/pq, x^{0.3})$, where $\Psi(x,y)$ is the number of integers $n\leq x$ with all prime factors $\leq y$. Thus, the total number of integers, such that $\tilde{n}>x^\gamma$ and $\tilde{n}$ has exactly 2 prime divisors is $$ \underset{x^{0.7}<pq}{\sum_{p, q>x^{0.3}}} \Psi\left(\frac{x}{pq}, x^{0.3}\right)\sim \underset{x^{0.7}<pq<x}{\sum_{p, q>x^{0.3}}}\rho\left(\frac{\log(x/pq)}{0.3\log x}\right)\frac{x}{pq}\sim\underset{s, t\geq 0.3}\int\limits_{0.7\leq t+s\leq 1}\rho\left(\frac{1-t-s}{0.3}\right)\frac{ds\;dt}{st}, $$ where $\rho$ is the Dickman function. The Dickman function is continuous and diferentiable at all places different from 1 with rather small derivative, thus the right hand side can be computed numerically without much pain.

Similarly, the case of 3 prime factors leads to the integral $$ \underset{0.7\leq s+t+u\leq 1}{\int\limits_{s, t, u>0.3}}\rho\left(\frac{1-t-s-u}{0.3}\right)\frac{ds\;dt\;du}{stu}. $$ In the range of integration $1-s-t-u<0.3$, thus the argument of the Dickman function is $<1$, and the value of the function is constant 1. Similarly, the lower bound $s+t+u\geq 0.7$ is trivially satisfied. Thus we get $$ \underset{s+t+u\leq 1}{\int\limits_{s, t, u>0.3}}\frac{ds\;dt\;du}{stu}, $$ which is even easier.

As $\beta$ gets smaller, the dimension of the range of integration increases, but something like $\beta=\frac{1}{6}$ or $\frac{1}{8}$ should still be doable. The problem is that for higher dimension the polyhedron over which integration takes place is pretty complicated, so Monte-Carlo methods will probably not help too much either.

In general convergence to the asymptotics is rather slow, but for $x=2^{4096}$ the error should already be pretty small.

$\endgroup$
  • 1
    $\begingroup$ Maybe I am dense but $\beta$ doesn't appear in the equation defining $\gamma.$ Is the upper bound $n \leq x^{\beta}$? $\endgroup$ – kodlu Aug 9 '18 at 13:30
  • 1
    $\begingroup$ @kodlu: $\beta$ appears implicitly in the definition of $\tilde{n}$. Edited the answer to make this clear. $\endgroup$ – Jan-Christoph Schlage-Puchta Aug 9 '18 at 14:20
  • $\begingroup$ "might take days to weeks of work" => Is that days of analytical work on paper, or numerical work with a computer? $\endgroup$ – Randomblue Aug 9 '18 at 17:47
  • $\begingroup$ @Randomblue: One should be able to generate the ranges of integration automatically. Then it would be days of programming and probably quite fast numerical integration afterwards. Or one computes the polyhedra by hand, which would be days to weeks of paperwork, followed by equally fast numerical integration. But for really high dimensions (may be 10-12?) the computer will not be able to deal with the integration any more. $\endgroup$ – Jan-Christoph Schlage-Puchta Aug 9 '18 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.