Fast Test for Semiprimes: Deterministic or Probabilistic?

[CRGreathouse]

Does anyone know of a fast test to see if an arbitrary number is a semiprime -- deterministic or probabilistic? A test that returned "at least three prime factors" or "at most two prime factors" as output would suffice, if that's easier. In fact the algorithm could even output "unknown" as long as that only happened on a small fraction of inputs.

Sieving up to the cube root takes exponential time. Factoring the number takes superpolynomial time. Is there something better?

 

[al-mahed]

semiprime = not more than 2 factors?

you can use this:

if n is odd there are different decompositions n = x^2 - y^2 in the same number of the different multiplications n = rs it admits

in general, for p and q prime numbers, such that p>=q:

$$pq = (\frac{pq+1}{2})^2 - (\frac{pq-1}{2})^2 = (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$$

ex: $$13*11 = 143 = 72^2 - 71^2 = 12^2 - 1^2$$

application:

we want to know if n = 2438323 is prime or not:

sqrt(n) = 1561,51... ==> we should start with x = 1562

writting $$x^2 - n = y^2 , 1562^2 - n = 39^2 indeed$$

so, n = (1562+39)(1562-39) = 1601*1523 both prime numbers

this seems to be faster than divide n for primes <= 1561 when we know that n is semiprime

 

[CRGreathouse]

That method takes $$\mathcal{O}(\sqrt n)$$ time in the worst case, which isn't useful -- I want an algorithm that's faster than factoring, and subexponential factoring algorithms are already known. Even with optimizations it's no better than $$\mathcal{O}(\sqrt[3]n)$$.

The method you mention (Fermat's algorithm) factors numbers, though, and I don't need that. I just need to know if a given number n has more than 2 factors or not.

Desired output:
7: At most two prime factors
8: At least three prime factors
9: At most two prime factors
10: At most two prime factors
11: At most two prime factors
12: At least three prime factors
13: At most two prime factors
14: At most two prime factors
15: At most two prime factors
16: At least three prime factors
17: At most two prime factors
18: At least three prime factors
19: At most two prime factors

I'm interested in numbers with between 30 and 300 bits.

 

[al-mahed]

I think what you want is too much specific, some programmer should help!

ps: what $$\mathcal{O}$$ means?

 

[CompuChip]

Sorry, not an answer to the original poster, but some explanation to al-mahed:

I think what you want is too much specific, some programmer should help!

Or a number theorist

ps: what $$\mathcal{O}$$ means?

It's notation borrowed from mathematics (where it has a rigorous meaning), in this case "the problem is $\mathcal{O}(\sqrt{n})$" means that in the worst case you have to check $\sqrt{n}$ numbers to complete the algorithm. For example, a naive prime factoring algorithm that say "try to divide n by every number < n until you've tried them all (prime) or one of them divides n" is $\mathcal{O}(n)$. A small optimization would be to restrict yourself to numbers $\ge \sqrt{n}$ and then the algorithm would become $\mathcal{O}(\sqrt{n})$. For large numbers (starting at 100 digits but possibly even $10^{23}$ digits) order n^1, n^(1/2) or n^(1/3) are much too slow, as it would take a computer very long to finish the calculation.

 

[Hurkyl]

It's notation borrowed from mathematics (where it has a rigorous meaning), in this case "the problem is $\mathcal{O}(\sqrt{n})$" means that in the worst case you have to check $\sqrt{n}$ numbers to complete the algorithm.

Actually, it means the amount of work you have to do is no worse than proportional to $\sqrt{n}$. (for some fixed, but unspecified, constant of proportionality)

 

[CRGreathouse]

Actually, it means the amount of work you have to do is no worse than proportional to $\sqrt{n}$. (for some fixed, but unspecified, constant of proportionality)

Quite right. I might have written $$\Theta(\sqrt n)$$ but some would find that pedantic. Generally I use the big omicron/O except when I'm making a special point.

I might have said that the functions I gave were simply upper bounds, and that I didn't know of strict lower bounds for those functions -- though I was actually referring to particular algorithms, for which the lower bounds were fairly clear in this case.
So no one knows of an algorithm for this faster than factoring?

 

[al-mahed]

So no one knows of an algorithm for this faster than factoring?

It is possible know the factors of a number (or at least the number of factors) without factoring the number?

 

[CRGreathouse]

It is possible know the factors of a number (or at least the number of factors) without factoring the number?

Sure. I mentioned an algorithm for this in my first post:

Take a large number and do a primality test. If the number is prime, it has exactly 1 prime factor. Otherwise, test successive primes 2, 3, 5, ... until you get to the cube root of the number. If you don't find any factors, then you have a number with exactly two prime factors, but you don't know what they are.

 

[alphachapmtl]

Nth semiprime UpperBound ?

Semiprime: does anyone knows of an upper-bound on the Nth semiprime? that is a function upperbound(N) such that:
(Nth semiprime) <= upperbound(N)

 

[CRGreathouse]

The nth prime is about $n\log n$, and the nth semiprime is about $n\log n /\log\log n$. I'd expect $2n\log n /\log\log n$ to be an upper bound for the nth semiprime for n > 2.

 

[alphachapmtl]

semiprime Nth formula

The nth prime is about $n\log n$, and the nth semiprime is about $n\log n /\log\log n$. I'd expect $2n\log n /\log\log n$ to be an upper bound for the nth semiprime for n > 2.

Thanks,
I did some computations for semiprime (of the form pq with p,q primes).
According to the results, your formula for the Nth semiprime (n log n/log log n) is about right.
I wonder if the formula would be a closer fit for the Nth squarefree semiprime...
Later I will try to extend those results.

=================================================
upto 10^1 #4=10 #log(#)/loglog(#)=16.976717 Diff = 6 = 60 %
upto 10^2 #34=95 #log(#)/loglog(#)=95.13565 Diff = 0 = 0.0 %
upto 10^3 #299=998 #log(#)/loglog(#)=979.25287 Diff = -19 = -1.9 %
upto 10^4 #2625=9998 #log(#)/loglog(#)=10015.514 Diff = 17 = 0.17 %
upto 10^5 #23378=99998 #log(#)/loglog(#)=101871.3 Diff = 1873 = 1.87 %
upto 10^6 #210035=999997 #log(#)/loglog(#)=1027155.06 Diff = 27158 = 2.71 %
upto 10^7 #1904324=9999998 #log(#)/loglog(#)=1.0307791E7 Diff = 307793 = 3.08 %
=================================================
#N = Nth semiprime = Nth squarefree semiprime
#10 = 26 = 35
#25 = 74 = 86
#50 = 146 = 166
#75 = 221 = 253
#100 = 314 = 334
#200 = 669 = 695
#300 = 1003 = 1047
#400 = 1355 = 1391
#500 = 1735 = 1779
#600 = 2098 = 2155
#700 = 2474 = 2517
#800 = 2866 = 2923
#900 = 3202 = 3254
#1000 = 3595 = 3662
#2000 = 7453 = 7586
#3000 = 11465 = 11569
#4000 = 15591 = 15713
#5000 = 19643 = 19781
#6000 = 23921 = 24086
#7000 = 28073 = 28239
#8000 = 32243 = 32462
#9000 = 36591 = 36769
#10000 = 40882 = 41073
#20000 = 84829 = 85079
#30000 = 129907 = 130222
#40000 = 175579 = 175957
#50000 = 222257 = 222665
#100000 = 459577 = 460121
#150000 = 702957 = 703633
#200000 = 950413 = 951247
#250000 = 1200671 = 1201603
=================================================

 

[CRGreathouse]

Squarefree semiprimes exclude only squares of primes. Up to n, one expects about $2\sqrt n/\log n$ squares of primes. But the error in the estimate $n\log n/\log\log n$ is around $\sqrt n$ already, so I don't think that's anything more than the law of small numbers.

Even by 10^7 in your numbers you can see that there's not much difference between the semiprimes and the squarefree semiprimes -- both have an error of around 3%. The pattern continues up to 10^14:

n	semi(n)			sfsemi(n)
10^7	1,904,324		1,903,878
10^8	17,427,258		17,426,029
10^9	160,788,536		160,785,135
10^10	1,493,776,443		1,493,766,851
10^11	13,959,990,342		13,959,963,049
10^12	131,126,017,178		131,125,938,680
10^13	1,237,088,048,653	1,237,087,821,006
10^14	11,715,902,308,080	11,715,901,643,501

n	est(semi(n))		est(sfsemi(n))
10^7	10,307,792		10,305,273
10^8	103,266,676		103,259,112
10^9	1,033,776,533		1,033,753,903
10^10	10,344,547,423		10,344,478,884
10^11	103,490,205,200		103,489,996,955
10^12	1,035,213,033,216	1,035,212,396,748
10^13	10,354,448,759,071	10,354,446,805,801
10^14	103,562,811,274,636	103,562,805,262,210

 

[alphachapmtl]

Wow, Thanks for the numbers,
my small Processing-Java program gets java.lang.OutOfMemoryError for 10^8.
Cause I generate a prime list by Eratosthenes Sieve method.
If I go to 10^8, I need a prime list up to (10^8)/2, of length 3001134, which is too big for memory.
I may try to write these to a file instead, but the sieve itself would have to be in memory.

 

[CRGreathouse]

Wow, Thanks for the numbers,
my small Processing-Java program gets java.lang.OutOfMemoryError for 10^8.
Cause I generate a prime list by Eratosthenes Sieve method.
If I go to 10^8, I need a prime list up to (10^8)/2, of length 3001134, which is too big for memory.
I may try to write these to a file instead, but the sieve itself would have to be in memory.

Well Java's not good at this stuff -- I'd recommend almost any other language* for this task -- but my trick was using a precalculated table of semiprime counts by powers of 10 (up to 10^14) and just computing the primes up to the square root.

A sieve up to (10^8)/2 = 5e7 should take 2.5e7 bits, or about 3 MB, if you store only the odd numbers. An int array of the primes up to 5e7 takes 11.5 MB if you have 32-bit words.

* C, C++, Ruby, Pari, GAP, even C# would be better...

 

[alphachapmtl]

Let p==prime, p2==semiprime==p*q with p,q primes.

Approximately (nth p = n logn) and (#p<x = x/logx).

Also (nth p2 = n logn/loglogn) from CRGreathouse's post.

Is there a known formula for (#p2<x) ? (x/(2*loglogx)) seems to be close.

Are similar formula known for the pk? (where pk=product of k primes.)

 

[CRGreathouse]

Let p==prime, p2==semiprime==p*q with p,q primes.

Approximately (nth p = n logn) and (#p<x = x/logx).

Also (nth p2 = n logn/loglogn) from CRGreathouse's post.

Is there a known formula for (#p2<x) ? (x/(2*loglogx)) seems to be close.

Are similar formula known for the pk? (where pk=product of k primes.)

The nth prime is about n log n, the nth semiprime is about n log n / log log n.

There are about n / log n primes up to n, and about n log log n / log n semiprimes up to n.


For P_3, numbers with exactly 3 prime factors, the density is 2n log n / (log log n)^2. I can't remember off the top of my head (!) how that generalizes. It's not too tough, I just can't think of it.

 

[alphachapmtl]

There are about (n / log n) primes up to n, and about (n loglog n / log n) semiprimes up to n.

I had found n/(2*loglog n) to be a quite good approximation for #semiprime<N.
It seems to be asymptotically converging to the correct value,
but further numerical verifications shows it overshoot and diverge for still higher values,
while (n loglog n / log n) keeps on track.

 A = x/(2*loglogx) ,  B = (x*loglogx)/logx
              x              N              A              B            N-A            N-B  %(N-A) %(N-B)
              5              1              5              1             -4              0   -400      0
             10              4              5              3             -1              1    -25     25
             50             17             18             17             -1              0     -5      0
            100             34             32             33              2              1      5      2
            500            153            136            146             17              7     11      4
           1000            299            258            279             41             20     13      6
           5000           1365           1167           1257            198            108     14      7
          10000           2625           2251           2410            374            215     14      8
          50000          12110          10498          11004           1612           1106     13      9
         100000          23378          20462          21223           2916           2155     12      9
         500000         108326          97113          98088          11213          10238     10      9
        1000000         210035         190418         190061          19617          19974      9      9
        5000000         979274         913747         886870          65527          92404      6      9
       10000000        1904324        1798598        1724733         105726         179591      5      9
       50000000        8940570        8695292        8109190         245278         831380      2      9
      100000000       17427258       17161642       15816320         265616        1610938      1      9
      500000000       82302116       83410152       74818255       -1108036        7483861     -1      9
     1000000000      160788536      164948071      146273133       -4159535       14515403     -2      9
    10000000000     1493776443     1594073851     1362215688     -100297408      131560755     -6      8
   100000000000    13959990342    15470643022    12760076125    -1510652680     1199914217    -10      8
  1000000000000   131126017178   150650549974   120116411228   -19524532796    11009605950    -14      8
 10000000000000  1237088048653  1471028763971  1135506954620  -233940715318   101581094033    -18      8
100000000000000 11715902308080 14396402984420 10773883745555 -2680500676340   942018562525    -22      8