Seberapa sulit untuk menghitung jumlah faktor bilangan bulat?

Diberikan bilangan bulat dengan panjang bit, seberapa sulitkah untuk menampilkan jumlah faktor utama (atau jumlah faktor) dari ? $N$ $n$ $N$

Jika kita tahu faktorisasi utama $N$ , maka ini akan mudah. Namun, jika kita mengetahui jumlah faktor prima, atau jumlah faktor umum, tidak jelas bagaimana kita akan menemukan faktorisasi utama yang sebenarnya.

Apakah masalah ini dipelajari? Adakah algoritma yang dikenal yang memecahkan pertanyaan ini tanpa menemukan faktorisasi prima?

Pertanyaan ini dimotivasi oleh rasa ingin tahu dan sebagian oleh pertanyaan matematika .

cc.complexity-theory counting-complexity nt.number-theory factoring Artem Kaznatcheev
sumber

Jika jumlah faktor prima besar, itu menyiratkan bahwa N memiliki faktor kecil yang dapat ditemukan dengan mudah. Di sisi lain, jika jumlah faktor prima dari N kecil, katakanlah 2, maka itu mirip dengan masalah anjak produk dari dua bilangan prima, dan mengetahui bahwa jumlah faktor 2 tampaknya tidak membantu. Lihat pertanyaan ini oleh Omid tentang kekerasan rata-rata mereka.

Kaveh

Satu hal lagi, karena pembagian berseragam

, masalah penghitungan semua faktor (bukan hanya faktor prima) ada di

dan karena itu juga dalam

(dan mungkin juga lengkap untuk

bawah

Pengurangan

T C^{0}

$\mathsf{TC^0}$

# T C^{0}

$\mathsf{\#TC^0}$

P

$\mathsf{P}$

# T C^{0}

$\mathsf{\#TC^0}$

A C^{0}

$\mathsf{AC^0}$

Kaveh

Kaveh, jika Anda bisa memperluas komentar Anda di atas menjadi jawaban, itu akan bagus. Saya tidak benar-benar melihat bagaimana pembagian dalam

membuat Anda menghitung faktor dalam

tanpa juga menyiratkan bahwa anjak piutang adalah dalam

. Kesalahpahaman ini kemungkinan disebabkan oleh kegagalan saya sendiri tetapi jawaban yang lebih rinci akan membantu.

{TC}^{0}

$\text{TC}^0$

# {TC}^{0}

$\#\text{TC}^0$

{TC}^{0}

$\text{TC}^0$

Derrick Stolee

dikenal AFAIK! dan ini terlalu mudah. Tapi saya tidak melihat di mana argumen itu pecah. ps: Saya kira saya tahu begitu, definisi saya

tidak baik (sama dengan

) dan itu masalahnya.

# T C^{0}

$\mathsf{\#TC^0}$

# P

$\mathsf{\#P}$

Kaveh

@Artem,

didefinisikan sebagai jumlah menerima jalur dari

mesin, dan

mesin hanya dapat menggunakan logaritma (di

) jumlah ruang untuk menebak

. Kami menduga terlalu banyak bit jika kita menggunakan definisi saya menulis, sebuah

perhitungan dengan polynomially banyak dugaan akan menangkap

, sama menghitung jumlah

s ukuran polinomial bahwa

mesin menerima mereka akan memberikan

# L

$\mathsf{\#L}$

N L

$\mathsf{NL}$

N L

$\mathsf{NL}$

| y |

$|y|$

x

$x$

A C^{0}

$\mathsf{AC^0}$

N P

$\mathsf{NP}$

x

$x$

A C^{0}

$\mathsf{AC^0}$

# P

$\mathsf{\#P}$ (tebak juga perhitungannya dan verifikasi bahwa itu benar-benar perhitungan yang menerima).

Kaveh

Jawaban:

Ini bukan jawaban saya, tetapi Terrence Tao memberikan jawaban yang indah untuk pertanyaan ini di MathOverflow.

Inilah beberapa baris pertama jawabannya. Untuk membaca jawaban yang lengkap, ikuti tautannya.

Ada pengamatan cerita rakyat bahwa jika seseorang dapat dengan cepat menghitung jumlah faktor prima dari bilangan bulat, maka orang mungkin akan dapat dengan cepat memfaktorkan n sepenuhnya. Jadi masalah penghitungan faktor prima diyakini memiliki kesulitan yang sebanding dengan memfaktorkan sendiri.

(Saya tidak yakin apakah ini harus menjadi jawaban atau komentar. Tapi itu benar-benar jawaban, meskipun tidak ditulis oleh saya. Saya sudah membuat jawaban Community Wiki sehingga dapat di-unduh atau diterima tanpa perlu. memberi saya reputasi.)

Robin Kothari
sumber

Menurut pendapat saya, sebuah penunjuk ke jawaban seperti ini layak mendapat poin reputasi (jadi seharusnya bukan wiki komunitas), tetapi saya mengerti bahwa orang yang berbeda memiliki pandangan yang berbeda.

Tsuyoshi Ito

Tapi ini bukan pengurangan formal ....

arnab

@arnab: Tidak, tidak. Itulah sebabnya ia menulis, "maka orang mungkin akan dapat dengan cepat memfaktorkan n sepenuhnya."

Tsuyoshi Ito

Seperti yang telah dinyatakan orang lain, menghitung faktor-faktor kemungkinan besar akan membutuhkan anjak piutang n. Namun, pembagian sidang dapat mengikat sejumlah faktor. Anda tahu, misalnya, bahwa memiliki paling banyak faktor, karena tidak ada faktor yang bisa kurang dari 2. Dengan menguji apakah dapat dibagi 2, Anda juga tahu bahwa memiliki paling banyak faktor , dll. Kelemahannya adalah bahwa setiap pengurangan ukuran semakin sulit - Anda harus menguji hingga untuk mengesampingkan mengandung lebih dari faktor . $N$ $n$ $N$ $N$ $\log_3(N)$ $N^{1/p}$ $N$ $p$

Foo Barrigno
sumber