Bagaimana mengukur kompleksitas masalah logaritma diskrit?

Jawaban untuk pertanyaan ini di Crypto Stack Exchange pada dasarnya mengatakan bahwa, untuk mengukur kompleksitas masalah logaritma, kita harus memperhitungkan panjang angka yang mewakili ukuran grup. Tampaknya sewenang-wenang, mengapa kita tidak memilih ukuran kelompok sebagai argumen? Adakah kriteria untuk mengetahui argumen apa yang harus dipilih? Sebenarnya, saya tahu saya mengabaikan sesuatu yang penting karena kompleksitasnya berubah sangat besar jika kita melakukannya berdasarkan ukuran grup.

time-complexity discrete-mathematics cryptography Nassim HADDAM
sumber

Pertanyaan menarik! Saya mengeditnya untuk mengatakan "ukur kompleksitas", daripada "hitung" itu, karena jawaban bagaimana kita menghitungnya adalah ¯ \ _ (ツ) _ / ¯. :-)

David Richerby

Saya pikir lebih baik seperti itu. :)

Nassim HADDAM

Jawaban:

Tidak masalah apakah Anda memilih ukuran grupatau ukuran bilangan bulat yang menyatakannya sebagai parameter, karena. Ada dua alasan yang biasanya kompleksitasnya dijelaskan dalam bentuk daripada: $|G|$ $n$ $n \approx \log |G|$ $n$ $|G|$

$n$ adalah panjang input (lebih akurat, input memiliki panjang ), dan kami biasanya mengukur kompleksitas algoritma sebagai fungsi dari panjang input. $\Theta(n)$
Biasanya adalah angka kecil seperti , sedangkanadalah angka yang sangat besar seperti (kira-kira) . $n$ $1024$ $|G|$ $2^{1024}$

Yuval Filmus
sumber

Saya mengerti maksud Anda, tetapi bukankah itu menjadi masalah di P jika kita memilih ukuran grup sebagai parameter?

Nassim HADDAM

Anda tidak dapat memilih parameter dalam kasus itu - parameter selalu merupakan panjang input.

Yuval Filmus

Terima kasih atas jawabannya. Saya punya masalah dengan apa yang mungkin terjadi jika kita mempertimbangkan kasus lain (masalah dalam P menjadi NP dan sebaliknya). Saya dapat melihat dengan jelas sekarang :) .

Nassim HADDAM

Kami tidak melakukan perhitungan secara unary karena tujuan kami adalah menghitung sejumlah angka atau menghitung logaritma diskrit, dan kami tidak peduli bagaimana angka tersebut diwakili. Memberikannya sebagai input dalam biner atau unary tidak mempengaruhi "waktu dinding" yang diperlukan untuk menyelesaikan masalah, hanya kompleksitasnya dalam hal ukuran input (karena kami mengubah ukuran input!).

Yuval Filmus

Selain itu, kita tidak bisa benar-benar memiliki integer panjang 128-bit sebagai input unary untuk algoritma dunia nyata. Tidak ada cukup atom di alam semesta.

Yuval Filmus