(Kriptografi) masalah dipecahkan dalam jumlah langkah aritmatika polinomial

9

Dalam makalah dari Adi Shamir [1] dari 1979 ia menunjukkan, bahwa anjak piutang dapat dilakukan dalam sejumlah langkah aritmatika polinomial . Fakta ini disajikan kembali, dan dengan demikian menjadi perhatian saya, dalam makalah Borwein dan Hobart baru-baru ini [2] dalam konteks program garis lurus (SLP).

Karena saya agak terkejut membaca ini, saya memiliki pertanyaan berikut: Apakah ada masalah kriptografi lain atau mungkin juga masalah yang relevan, yang dapat diselesaikan dalam sejumlah langkah polinomial dengan SLP dan yang saat ini tidak diketahui dapat dipecahkan efisien pada komputer klasik "normal"?

[1] Adi Shamir, Anjak Angka dalam langkah-langkah hitung HAI(catatan⁡n) . Pemrosesan Informasi Letters 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, Kekuatan Luar Biasa Divisi dalam Program Garis Lurus , The American Mathematical Monthly Vol. 119, No. 7 (Agustus ‒ September 2012), hlm. 584-592

cc.complexity-theory cr.crypto-security algebraic-complexity Etsch
sumber
Apa yang dimaksud "dipecahkan dalam jumlah polinomial langkah aritmatika"? Algoritma anjak terbaik saat ini tersedia membutuhkan waktu subeksponensial (tetapi super polinomial). Saya tidak dapat menemukan kertas Shamir di mana pun.
mikeazo
Saya sarankan memposting ini di Crypto.SE karena Anda belum mendapat banyak tanggapan di sini.
mikeazo
Ada entri blog terkait oleh Lipton: rjlipton.wordpress.com/2012/10/16/... Model perhitungan ini agak curang, karena Anda mengizinkan perhitungan dengan presisi panjang yang sewenang-wenang. Saya tidak mengetahui masalah terkait kripto lainnya yang telah dibahas dalam model ini. Tapi modelnya sangat kuat sehingga bisa dicoba.
minar
@ Minar masalah curang bukan dengan ketepatan aribtrary. kecurangan di sini adalah dengan operasi lantai dan langit-langit.
T ....

Jawaban:

-2

Saya tidak membaca makalah juga tetapi abstrak tampaknya mengatakan bahwa sejumlah operasi bit eksponen diperlukan.

Penelitian Chebyshev tentang kongruensi dan reformulasinya dalam algoritma AKS menunjukkan bahwa generasi prima ada di P. Oleh karena itu, divisi percobaan menghasilkan faktor-faktor yang tidak sepele. Dalam hal itu, untuk beberapa angka N, Anda dapat mengharapkan kepadatan bilangan prima 1 / ln (N).

Selain itu, Anda dapat melihat tesis Turing 1937 PhD tentang masalah ini.

Phil
sumber
3
Hai Phil. Selamat datang di cstheory. Anda telah memposting jawaban untuk banyak pertanyaan dalam waktu singkat yang tidak biasa di sini. Posting yang benar-benar komentar dan bukan jawaban atas pertanyaan tidak boleh diposting sebagai jawaban. Anda mungkin ingin melihat-lihat dan memeriksa pertanyaan lain dan cara kerja di sini sebelum mengirim lebih banyak jawaban.
Kaveh