ตัวแก้ลอการิทึมไม่ต่อเนื่องออนไลน์
หาเลขชี้กำลัง x ที่น้อยที่สุดสำหรับ g^x ≡ h (mod p) จากค่าที่ป้อน
เริ่มใช้งาน
การแก้ปัญหาลอการิทึมไม่ต่อเนื่อง
เครื่องมือนี้ออกแบบมาเพื่อค้นหาเลขชี้กำลัง x ที่เล็กที่สุดซึ่งทำให้ g^x ≡ h (mod p) โดยใช้การค้นหาแบบละเอียด (exhaustive search) ตั้งแต่ x=0 ไปจนถึง p-1 ตัวอย่างเช่น ถ้าป้อน g=2, h=8, p=13 เครื่องมือจะเริ่มจากค่าเริ่มต้น 1 (แทน 2^0) แล้วคูณด้วย 2 และ mod 13 ไปเรื่อย ๆ จนพบว่า 2^3 = 8 พอดี จึงคืนค่า x=3
ขั้นตอนการทำงาน
- เริ่มต้นด้วยค่า value = 1 สำหรับ x=0
- ในแต่ละรอบ ตรวจสอบว่า value เท่ากับ h mod p หรือไม่ ถ้าใช่ คืนค่า x ปัจจุบัน
- ถ้าไม่ใช่ อัปเดต value = (value * g) mod p และเพิ่ม x ทีละ 1
- ทำซ้ำจนถึง x = p-1 ถ้ายังไม่พบ ให้รายงานว่าไม่มีคำตอบ
ข้อจำกัดที่ควรทราบ
- p ต้องเป็นจำนวนเต็มระหว่าง 2 ถึง 1,000,000 เท่านั้น
- การค้นหาเป็นแบบ O(p) จึงเหมาะสำหรับการศึกษาหรือ p ขนาดเล็ก ไม่เหมาะกับงานเข้ารหัสจริง
- ไม่จำเป็นต้องให้ p เป็นจำนวนเฉพาะ และไม่มีการรับประกันว่า g จะสร้างกลุ่มครบ
- ถ้า g และ p ไม่เป็นจำนวนเฉพาะร่วมกัน ลำดับอาจวนเป็นรอบสั้น แต่การค้นหายังคงพบคำตอบถ้ามี
คำถามที่พบบ่อย
1. ถ้าป้อน h เป็นลบหรือมากกว่า p จะเกิดอะไรขึ้น?
h จะถูกปรับให้เป็นเศษเหลือ (mod p) ก่อนเปรียบเทียบ เช่น h = -5 และ p = 13 จะถูกแปลงเป็น 8 (เพราะ -5 mod 13 = 8) ดังนั้นผลลัพธ์จะเหมือนกับป้อน h = 8
2. ทำไมผลลัพธ์จึงเป็น x ที่น้อยที่สุดเสมอ?
เพราะการค้นหาเริ่มจาก x=0 และเพิ่มขึ้นทีละ 1 เมื่อพบค่าแรกที่ตรงกัน จะหยุดทันทีและคืนค่านั้น จึงเป็นการรับประกันว่าเป็นเลขชี้กำลังที่น้อยที่สุดในช่วงที่ตรวจสอบ
3. เครื่องมือนี้ใช้สำหรับถอดรหัสกุญแจส่วนตัวหรือประเมินความปลอดภัยได้หรือไม่?
ไม่ใช่ เครื่องมือนี้เป็นเพียงการสาธิตเชิงการศึกษาสำหรับแนวคิดลอการิทึมไม่ต่อเนื่อง ไม่ได้ใช้ขั้นตอนวิธีขั้นสูง และไม่สามารถจัดการกับมอดุลัสขนาดใหญ่ที่ใช้ในการเข้ารหัสจริงได้ จึงไม่ควรนำผลไปใช้ในการอ้างสิทธิ์ด้านความปลอดภัย
ต้องกรอก g และ h เป็นจำนวนเต็มที่แทนค่าได้อย่างแม่นยำตั้งแต่ -9007199254740991 ถึง 9007199254740991 ส่วน p ต้องเป็นจำนวนเต็มตั้งแต่ 2 ถึง 1000000 โดยจะปรับฐานและค่าเป้าหมายให้เป็นเศษเหลือเมื่อหารด้วย p ก่อนค้นหา
การประมวลผลเกิดขึ้นภายในเบราว์เซอร์ของคุณ