เราควรกลัวการมาถึงของควอนตัมอมพิวเตอร์ จริง ๆ นะ

disclaimer: ผู้เขียนไม่ได้จบสายคอม หรือคณิต

ความน่ากลัวของควอนตัมอมพิวเตอร์ คือ มันสามารถคำนวณสิ่งที่ คอมปกติใช้เวลาแบบ exponential (เช่น ECDSA ใน bitcoin) ให้อยู่ในเวลา polynomial ได้

exponential คือ k^n; polynomial คือ n^k

k คือค่าคงที่, n คิดซะว่าเป็นความยาว private key

พบว่า ถ้า n สูงถึงจุดนึง k^n (expo) จะมากกว่า n^k เสมอ

ดูง่ายๆ อย่าง

2^256 = 1.16*10^7 = 1.16+ล้าน12รอบ

ส่วน 256^2 = 65536

นี่คือความน่ากลัวของ expo ที่โตเร็วมากๆ

เพราะฉะนั้นการที่ google แก้ปัญหาที่ต้องแก้ใน 10^25 ปี (5*(10^30) นาที) ได้ใน 5 นาที อาจไม่ได้หมายถึงต้องใช้เวลาในการแก้โจทย์ที่ปกติต้องใช้เวลา 10^77 นาที ในเวลา (10^77)/(10^30)=10^47 (ล้าน7รอบ) นาที

แต่อาจหมายถึงใช้แค่ (77^10)/(30^10) = หมื่น นาที

อย่างไรก็ตามอันนี้พูดให้ดูโอเวอร์เฉย ๆ ค่า k ของควอนตัมคอมพิวเตอร์คงไม่ต่ำขนาดนั้นหรอกมั้ง และปัญหาที่ google แก้ก็ง่ายกว่า (ในทางการเขียนในควอนตัมคอมพิวเตอร์จริงๆ) ECDSA แบบคนละระดับ และไม่ได้รวมข้อจำกัดทางกายภาพอื่น ๆ

ปล. เลขและหน่วยซุยมากน่าจะมีผิดบางจุด ถ้าร้ายแรงมากช่วยบอกให้แก้ด้วย

#siamstr