12
$\begingroup$

There are many fast algorithms (deterministic and probabilistic) for detecting primality. Are there any fast algorithms (probabilistic ones allowed) known for detecting whether a number is the product of at most two primes?

In this context, can anybody think of a property fulfilled by all or most products of two primes, but by few other numbers? (You can't explicitly use divisor sums or the Moebius function, obviously, as then the game becomes (a) trivial (b) of doubtful computational utility.)

$\endgroup$
3
  • 2
    $\begingroup$ A similar question has already been asked on MathOverflow, with several useful answers: mathoverflow.net/questions/3820/… $\endgroup$
    – TonyK
    Aug 26, 2010 at 12:19
  • $\begingroup$ All we have there is comments stating that related questions are likely to be very hard. I partially agree; at the same time, what I have asked may in some sense be the minimal question of that kind. Note, in particular, that answering my question would not solve the fast factorisation problem (whereas, say, computing Euler's phi function rapidly would). It would be especially nice to have an answer to the second half of my question - that half is not explicitly computational. $\endgroup$ Aug 27, 2010 at 1:59
  • $\begingroup$ This sounds like a generalization project. It might be a useful endeavour to (start with k=2 and) analyze/extend some of the elementary tests for numbers with at most k prime factors (kprimes). Sieveing by nontrivial multiples of kprimes, looking at Fermat, Euler, Carmichael tests and how kprimes respond, and looking at kprime counting functions come to mind. Gerhard "Ask Me About System Design" Paseman, 2010.08.28 $\endgroup$ Aug 28, 2010 at 7:31

2 Answers 2

2
$\begingroup$

There is a survey of open problems related to factoring algorithms, Open problems in number theoretic complexity, II, by Adleman and McCurley. It lists so many questions related to distinguishing almost primes from other composite numbers that it seems safe to infer that it is an open problem to do it quickly, and that you would either use a factoring algorithm or a related method. For instance, computing the Mobius function as you say is a known open problem, and detecting an almost prime can be viewed as a special case of computing the Mobius function. Because, of course, it is easy to distinguish a prime from an almost prime.

As for relevant properties, the most important relevant property of a prime $p$ is that its multiplicative group $(\mathbb{Z}/p)^\times$ is cyclic of order $p-1$. The Miller-Rabin primality test is based on that fact. Now, if $n = pq$ is an odd almost prime, then the multiplicative group $(\mathbb{Z}/n)^\times$ is a product of two cyclic groups. Conversely, if $(\mathbb{Z}/n)^\times$ is a product of two cyclic groups and $n$ is odd, then $n$ is a product of two prime powers. But, there is too little control over the cardinality of this group. In the almost prime case, it has $(p-1)(q-1)$ elements. Even if you found the 2-torsion elements, in other words all solutions to $x^2 \equiv 1 \bmod n$, you would be able to factor $n$.

The set of almost prime numbers is an important statistical ersatz for the set of prime numbers in analytic number theory. However, in computational number theory, no particular reason leaps out that identifying almost primes is easier than other factoring-related questions that are accepted as hard.

$\endgroup$
-1
$\begingroup$

this is my answer, I don't know if this can complete your answer or not:

(similar to falagar's answer )

Let $w_i$ be the product $p_{2i}p_{2i+1}$, where $p_{i}$ is ${i}$th prime, each $w_i$ is product of two distinct primes and also $w_k$ and $w_t$ are coprime, now take $t^2$ such that $t^{2}\equiv- k\pmod{w_i}$for $k=-N\cdots 0,1,2\cdots N$,and $i=1,2,\cdots ,2N+1$ such that for $k=-N$,$i=1$ and,...,by chinese remainder theorem, we have such $t^2$.

Now $t^{2}+i$ has at least two primes because $t^{2}+i$ is multiple of $w_i$,since there are a prime between $t$ and $2t$ and also $t$ and $t/2$,so $t+h_1$ and $t-h_2$ are primes,so at least one of the numbers $t^{2}-N,\cdots t^{2}+1,t^{2}+2\cdots ,t^{2}+N$ is exactly product of two distinct primes.

$\endgroup$
5
  • $\begingroup$ I think you need $w_i=p_{2i}p_{2i+1}$ to ensure that they are coprime. Also, I don't follow why one of $t^2+j$ is the product of exactly two primes. $\endgroup$ Aug 28, 2010 at 9:42
  • $\begingroup$ thank you for notice: $t^{2}\equiv{t(h_2-h_1)+h_1h_2}\pmod{w_i}$ in which $t(h_2-h_1)+h_1h_2$ is positive or negative,so $(t-h_2)(t-h_1)\equiv 0\pmod{w_i}$ $\endgroup$ Aug 28, 2010 at 11:34
  • $\begingroup$ it should be $(t-h_2)(t+h_1)\equiv 0\pmod{w_i}$ $\endgroup$ Aug 28, 2010 at 11:39
  • $\begingroup$ I think what you're using is that $t(h_2-h_1)+h_1h_2\in[-N,N]$, which isn't necessarily true (the smallest possible t may be much larger than N - it just needs to be smaller than $\prod_{i\leq 2N+1}p_i$). $\endgroup$ Aug 28, 2010 at 15:50
  • $\begingroup$ of course this is depend to $h_1$ and $h_2$,if $t(h_2-h_1)+h_1h_2$ is not in $[-N,N]$,we can choose arbitraries numbers to form$-m,-m+1,...,0,KN-t,kN-t+1,...,kN$,such tht the numbers of these to be $2N+1$ ,and$t(h_2-h_1)+h_1h_2$ be in this intervals $\endgroup$ Aug 29, 2010 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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