4
$\begingroup$

Suppose, we have a $k$-digit number $n$. Suppose, $n$ is composite and has no prime factor below $10^{29}$.

What is the expected number of digits of the smallest prime factor of $n$ ?

In the concrete casse, I am interested in the composite number $$77^{77}+416$$ having $146$ digits and after I searched a factor via ECM for some hours, It seems to have no prime factor with less than $30$ digits. I know the asymptotic formula $$\prod_{p\le x,p\ prime} (1-\frac{1}{p})\approx \frac{e^{-\gamma}}{\ln(x)}$$ but I am not sure whether this approximation is good enough for $x=10^{29}$ because $n$ is very small compared to $p$#. Who can help ?

$\endgroup$
7
  • 1
    $\begingroup$ This seems closely related (perhaps more tractable) than your previous Question. I say tractable because it looks like the number of prime factors in the current problem is at most four. $\endgroup$
    – hardmath
    Commented Oct 1, 2017 at 16:12
  • $\begingroup$ For $10^{29}$ I got $0.0084$ in the asymptotic formula. What does it mean? $\endgroup$
    – Raffaele
    Commented Oct 1, 2017 at 17:17
  • $\begingroup$ @Raffaele For very large numbers, it is the "probability" that a random number has no prime factor below $10^{29}$. If we have a sufficiently large number $N$ (no idea what "sufficiently large" exactly means), then $0.84$% of the numbers in the interval , lets say $[N,N+10^9]$ , will have no prime factor below $10^{29}$. $\endgroup$
    – Peter
    Commented Oct 2, 2017 at 10:56
  • 1
    $\begingroup$ I downloaded a fantastic program which is called CADO-NFS and let it run with your number (BTW where does it come from?) for about two hours with no results apart the temperature of the notebook you could fry an egg on... so I quitted. Do you know somebody who has access to a supercomputer? :) (just kidding...) $\endgroup$
    – Raffaele
    Commented Oct 2, 2017 at 11:08
  • $\begingroup$ @Raffaele Do you mean the number-field-sieve (NFS) ? It is the fastest known algorithm to factor general numbers, if the smallest prime factor is "large". Prime factors with , lets say , $10$ to $40$ digits , can be most efficiently found by the elliptic curve method (ECM). $\endgroup$
    – Peter
    Commented Oct 2, 2017 at 11:24

1 Answer 1

2
$\begingroup$

As a rough estimate the expected number of digits for the smallest prime factor is $50$.

Update(02/02/18): After running about $6400$ curves through GMP-ECM with parameter B1=11e7:

Using B1=110000000, B2=776278396540, polynomial Dickson(30), sigma=1:810921926  
Step 1 took 228799ms  
Step 2 took 89654ms  
********** Factor found in step 2:  
 53589746607540242261214306067426138960848650157001  
Found prime factor of 50 digits:  
 53589746607540242261214306067426138960848650157001  
Prime cofactor  
 (77^77+416)/53589746607540242261214306067426138960848650157001 has 96 digits  

More details toward the end of post.


Rough estimate

We assume a $146$-digit composite number $N$ without prime factors below $10^{30}$.

As earlier commented such $N$ must be the product of at least two and not more than four prime factors (possibly repeated). In this first "crude" pass I've only considered the case of two prime factors. Intuitively if more prime factors exist, that would tend to lower the expected size of the smallest prime factor. But I intend to make more elaborate calculations to support this.

In this simple model of "expected size of prime factors" we approximate that the product of a $k$-digit prime and an $m$-digit prime will be a $(k+m)$-digit product. Again I intend to refine this approximation by using a smaller radix than ten to pigeonhole the available prime factors, but it makes for a clear exposition of the method.

With the smaller prime factor in this approximation having between $31$ and $73$ digits (since the product of both factors has $146$ digits), we can turn to the Prime Number Theorem to approximate the count of primes having respectively $k$ and $m$ digits such that $k+m = 146$.

The first bucket of such products would then be with $k=31$ and $m=115$. We would continue with $k=32$ and $m=114$, and so on up to $k=m=73$. This last case requires a little special treatment in order to avoid double counting the product being taken in both orders (since the number of digits of the two factors are equal).

At first glance we proceed by counting all such possible products of two primes giving $146$-digit products, and the universe of these gives a probability distribution for the number of digits in the smaller factor. That is, appealing to the Prime Number Theorem for an approximate count of primes between $10^{k-1}$ and $10^k$, i.e. the $k$-digit primes, we have the following breakdown:

$$ \frac{9\times 10^{30}}{\ln 10^{31}} \times \frac{9\times 10^{114}}{\ln 10^{115}} = \frac{8.1 \times 10^{145}}{31\cdot 115 (\ln 10)^2} $$

$$ \frac{9\times 10^{31}}{\ln 10^{32}} \times \frac{9\times 10^{113}}{\ln 10^{114}} = \frac{8.1 \times 10^{145}}{32\cdot 114 (\ln 10)^2} $$

$$ \cdots $$

$$ \frac{9\times 10^{71}}{\ln 10^{72}} \times \frac{9\times 10^{73}}{\ln 10^{74}} = \frac{8.1 \times 10^{145}}{72\cdot 74 (\ln 10)^2} $$

$$ 0.5 \times \frac{9\times 10^{72}}{\ln 10^{73}} \times \frac{9\times 10^{72}}{\ln 10^{73}} = 0.5 \times \frac{8.1 \times 10^{145}}{73\cdot 73 (\ln 10)^2} $$

For the purpose of constructing a probability distribution from these counts (because the universal sample space is formed by totaling them), the common factor $8.1 \times 10^{145}\over {(\ln 10)^2}$ can be removed from all of them. Then the "expected number of digits" for the smallest prime factor would be approximately the weighted average:

$$ \frac{\frac{31}{31\cdot 115} + \cdots + \frac{72}{72\cdot 74} + \frac{0.5 \cdot 73}{73\cdot 73}}{\frac{1}{31\cdot 115} + \cdots + \frac{1}{72\cdot 74} + \frac{0.5}{73\cdot 73}} \approx 50.31 $$

If we use the median case, rather than the weighted average, to signify our "expected number of digits", that would give a slightly smaller figure. So at a first cut I'm going with $50$ digits, pending more detailed calculations.


How the ECM factorization was found

After carrying the Alpertron ECM calculations (see Comment below) well beyond the expected number needed to find a factor of $45$ digits, I switched to using the command line program GMP-ECM.

In the first instance I used the optimal parameters to revisit the possibility of a $45$ digit factor. This proceeded rapidly (about $33$ seconds per curve) through the recommended $~5000$ curves with negative results. I then ran with parameters for a $50$ digit factor ($~8800$ curves, about $2$ minutes per curve) and no factor was found.

Finally I started a run with B1 = 11e7, the recommendation for factors up to $55$ digits. This factorization succeeded after about $6400$ curves (a little more than $5$ minutes per curve) in finding a $50$ digit prime factor and its $96$ digit prime cofactor:

$$ 77^{77}+416 = 53589746607540242261214306067426138960848650157001 (50 \text{ digits})\\ \cdot 339393 979990 326835 173961 336712 422753 831537 767975 982133 569460 681025 969329 465741 754938 257755 556213 (96 \text{ digits}) $$

As a check I confirmed the product of the last six digits of each factor agrees with the target number's last six digits.

Update(09/15/19):

I came across a thread at mersenneforum.org that announces an online calculator for the sort of problem asked here.

One enters the "work" already done by ECM in trying to find factors in terms of parameter B1 and number of curves, information I don't have for your particular case. However the statement, "It seems to have no prime factor with less than 30 digits," might be roughly modelled by entering B1 = 250000 and a generous number of curves (relative to recommendations here), say five thousand such curves.

With that input the calculator says the expected factor size is $35.7$ digits. However in this phase one does not provide the size of the number to be factored (146 digits, which I took into account along with compositeness), although that information is used in a second computation underneath the top portion of the screen. In any case the top graph produced is this:

Chance to find or miss factor of size x

$\endgroup$
3
  • $\begingroup$ @Peter: I've finished 24,000 elliptic curves in Dario Alpern's Alpertron, and without success in finding a factor of 77^77+416. The first two thousand curves use smallish parameters for ECM, but the remaining twenty odd thousand curves are twice the expected number needed to find a factor of 45 digits or less. $\endgroup$
    – hardmath
    Commented Nov 23, 2017 at 5:17
  • 1
    $\begingroup$ The ECM calculator doesn't answer "the sort of problem asked here." Note that it makes all these calculations, including an "expected factor size," without your ever telling it how large the number to be factored is! So it clearly doesn't tell us "the expected number of digits of the smallest prime factor of a k-digit number given that it has no factors of fewer than m digits." Instead, the "expected factor size" tells us something about the ECM process (if doing this much work found no factor but the very next curve does, how large would we expect that factor to be?) $\endgroup$
    – Prodicus
    Commented Sep 22, 2019 at 1:30
  • $\begingroup$ Your original answer seems a more promising idea, but I tried to derive something a little more formally using this idea- the density of primes is 1/log m, use the density at the quotient as well and integrate- and wasn't getting sensible answers out of it. I'm missing something. $\endgroup$
    – Prodicus
    Commented Sep 22, 2019 at 1:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .