<p>Interesting question. I might add this to my slide deck for Lambaconf.</p>

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

<blockquote>
  <p>binomial :: $n\rightarrow (x+a)$</p>
</blockquote>

<p>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.</p>

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

<p>Enter one of my favorite papers, <a href="http://users.wfu.edu/rouseja/cv/flwthms.pdf" rel="nofollow">Combinatorial Proofs of Fermat's, Lucas's, and Wilson's Theorems</a>. It ties primality to fixed points of iterated function composition. That paper was the springboard for the <a href="https://github.com/chadbrewbaker/endoscope" rel="nofollow">Endoscope project</a>.</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-04-24T16:32:33.127Z
2016-04-24T16:32:33.127Z
Chad Brewbaker
<p>We also know that following AKS given $N$ it is easy to decide the number of prime factors of $N$ is $&gt;1$.</p>

<p>On other hand the problem of counting number of prime factors is considered here <a href="https://cstheory.stackexchange.com/questions/7862/how-hard-is-it-to-count-the-number-of-factors-of-an-integer">How hard is it to count the number of factors of an integer?</a> and we think there is not much hope.</p>

<p>My problem is simpler. </p>

<p>Given $N$ is it as hard as factoring to decide the number of prime factors of $N$ is $&gt;2$?</p>

<p>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$?</p>

<factoring>
Deciding almost prime numbers
Turbo
# Deciding almost prime numbers

(Asked by: username_0 on 2016-04-24)

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?](https://cstheory.stackexchange.com/questions/7862/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$?

**Tags:** factoring

---

## 1 answers

### Answer by username_1 on 2016-04-24. Score: -2

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](http://users.wfu.edu/rouseja/cv/flwthms.pdf). It ties primality to fixed points of iterated function composition. That paper was the springboard for the [Endoscope project](https://github.com/chadbrewbaker/endoscope).

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.


---

