To interesujące pytanie jest o wiele trudniejsze, niż się wydaje, i nie ma na nie odpowiedzi. Pytanie można rozłożyć na 2 bardzo różne pytania.
1 mając N, znajdź listę L czynników pierwszych N.
2 biorąc pod uwagę L, oblicz liczbę unikalnych kombinacji
Wszystkie odpowiedzi, które do tej pory widzę, odnoszą się do nr 1 i nie wspominają, że nie da się tego rozwiązać w przypadku ogromnych liczb. Dla średniej wielkości N, nawet 64-bitowych, jest to łatwe; dla ogromnego N problem faktoringu może trwać „wiecznie”. Od tego zależy szyfrowanie klucza publicznego.
Pytanie nr 2 wymaga dalszej dyskusji. Jeśli L zawiera tylko unikalne liczby, jest to proste obliczenie przy użyciu wzoru kombinacji do wyboru k obiektów z n elementów. W rzeczywistości należy zsumować wyniki zastosowania wzoru, zmieniając k od 1 do sizeof (L). Jednak L zwykle zawiera wiele wystąpień wielu liczb pierwszych. Na przykład L = {2,2,2,3,3,5} to faktoryzacja N = 360. Teraz ten problem jest dość trudny!
Powtarzając # 2, dany zbiór C zawiera k elementów, tak że element a ma „duplikaty, a element b ma duplikaty b” itd. Ile jest unikalnych kombinacji elementów od 1 do k-1? Na przykład {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} muszą wystąpić raz i tylko raz, jeśli L = {2,2 , 2,3,3,5}. Każda taka unikalna pod-kolekcja jest niepowtarzalnym dzielnikiem N przez pomnożenie elementów w pod-kolekcji.