Deciding almost prime numbers

Question

We also know that following AKS given $N$ it is easy to decide the number of prime factors of $N$ is $>1$.

On other hand the problem of counting number of prime factors is considered here How hard is it to count the number of factors of an integer? and we think there is not much hope.

My problem is simpler.

Given $N$ is it as hard as factoring to decide the number of prime factors of $N$ is $>2$?

Given $N$ is it as hard as factoring to decide the number of prime factors $\bmod k$ of $N$ is $1$ for some fixed prime $k$?

Answer 1

Interesting question. I might add this to my slide deck for Lambaconf.

$(x+a)^n$ counts members of the binomial function space,

binomial :: $n\rightarrow (x+a)$

We know from the binomial formula ${n(n-1)!\over k! (n-k)!}$ we get multiples of $n$ for primes, no number less than $n$ is a factor, but compsites can cancel out our $n$ factor up top.

How do we efficently search the $n$th row of Pascal's triangle to find those cancelations?

Enter one of my favorite papers, Combinatorial Proofs of Fermat's, Lucas's, and Wilson's Theorems. It ties primality to fixed points of iterated function composition. That paper was the springboard for the Endoscope project.

AKS used the Fermat's little theorem version with polynomial residue functions to narrow the search. From the above paper we know that any endofuction will tell us primality properties under self-composition.

We need to try other endofuctions more amenable to giving us distribution information. There is nothing magical about the binomial endofuction AKS used.