Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Semiprime test

  1. Oct 18, 2007 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  2. jcsd
  3. Dec 27, 2007 #2
    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:

    [tex] pq = (\frac{pq+1}{2})^2 - (\frac{pq-1}{2})^2 = (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2 [/tex]

    ex: [tex]13*11 = 143 = 72^2 - 71^2 = 12^2 - 1^2[/tex]

    application:

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

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

    writting [tex] x^2 - n = y^2 , 1562^2 - n = 39^2 indeed[/tex]

    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
     
  4. Dec 27, 2007 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    That method takes [tex]\mathcal{O}(\sqrt n)[/tex] 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 [tex]\mathcal{O}(\sqrt[3]n)[/tex].

    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.
     
  5. Dec 27, 2007 #4
    I think what you want is too much specific, some programmer should help!

    ps: what [tex]\mathcal{O}[/tex] means?
     
  6. Dec 28, 2007 #5

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

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

    Or a number theorist :smile:

    It's notation borrowed from mathematics (where it has a rigorous meaning), in this case "the problem is [itex]\mathcal{O}(\sqrt{n})[/itex]" means that in the worst case you have to check [itex]\sqrt{n}[/itex] 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 [itex]\mathcal{O}(n)[/itex]. A small optimization would be to restrict yourself to numbers [itex]\ge \sqrt{n}[/itex] and then the algorithm would become [itex]\mathcal{O}(\sqrt{n})[/itex]. For large numbers (starting at 100 digits but possibly even [itex]10^{23}[/itex] 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.
     
  7. Dec 28, 2007 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Actually, it means the amount of work you have to do is no worse than proportional to [itex]\sqrt{n}[/itex]. (for some fixed, but unspecified, constant of proportionality)
     
  8. Dec 28, 2007 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Quite right. I might have written [tex]\Theta(\sqrt n)[/tex] 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?
     
  9. Dec 28, 2007 #8
    It is possible know the factors of a number (or at least the number of factors) without factoring the number?
     
  10. Dec 28, 2007 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  11. Feb 3, 2008 #10
    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)
     
  12. Feb 4, 2008 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The nth prime is about [itex]n\log n[/itex], and the nth semiprime is about [itex]n\log n /\log\log n[/itex]. I'd expect [itex]2n\log n /\log\log n[/itex] to be an upper bound for the nth semiprime for n > 2.
     
  13. Feb 4, 2008 #12
    semiprime Nth formula

    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
    =================================================
     
    Last edited: Feb 4, 2008
  14. Feb 5, 2008 #13

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Squarefree semiprimes exclude only squares of primes. Up to n, one expects about [itex]2\sqrt n/\log n[/itex] squares of primes. But the error in the estimate [itex]n\log n/\log\log n[/itex] is around [itex]\sqrt n[/itex] 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:

    Code (Text):
    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
    Code (Text):
    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
     
  15. Feb 5, 2008 #14
    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.
     
  16. Feb 5, 2008 #15

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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...
     
  17. Feb 9, 2008 #16
    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.)
     
    Last edited: Feb 10, 2008
  18. Feb 10, 2008 #17

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  19. Feb 11, 2008 #18
    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.
    Code (Text):
     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

     
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Semiprime test
  1. Question in test (Replies: 4)

  2. Independence test (Replies: 4)

  3. Semiprime ring (Replies: 3)

  4. Test for Primes (Replies: 5)

  5. Subring Test (Replies: 4)

Loading...