เนื้อหา
การคำนวณรากดั้งเดิมเป็นทักษะที่มีประโยชน์ในการเข้ารหัสและทฤษฎีจำนวน ตัวเลข "g" เป็นรากดั้งเดิมสำหรับจำนวนเฉพาะ "p" ที่กำหนดหาก g mod p มีลำดับโมดูลัส p-1 ซึ่งหมายความว่ารายการของ "g1 mod p", "g2 mod p" ถึง "g (p-1) mod p" มีจำนวนเต็มทั้งหมดตั้งแต่ 1 ถึง (p-1) ไม่มีอัลกอริทึมที่รู้จักกันในการคำนวณรากแบบดั้งเดิมได้อย่างมีประสิทธิภาพ วิธีที่ง่ายที่สุดคือลองตัวเลขที่เป็นไปได้ตั้งแต่ 2 ถึง (p-1)
คำสั่ง
-
เลือกจำนวนเฉพาะ "p" เช่นห้า จำนวนเฉพาะไม่มีตัวหารใด ๆ ตัวอย่างเช่นสี่ไม่ใช่หมายเลขเฉพาะเนื่องจาก "4/2 = 2" มันมี 2 เป็นหนึ่งในตัวหาร
-
คำนวณ "2 ^ n mod p" สำหรับแต่ละจำนวนเต็ม "n" จาก 1 ถึง (p-1) ใช้ตัวอย่าง "p" คือ 5 จากนั้นคำนวณ "2 ^ n mod 5" สำหรับ "n" จาก 1 ถึง 4 สิ่งนี้จะสร้างรายการ:
2 ^ 1 = 2 mod5 = 2 2 ^ 2 = 4 mod5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
ตรวจสอบให้แน่ใจว่ารายการตัวเลขมีร่องรอยที่เป็นไปได้ทั้งหมดห้ารายการ รายการ 2, 4, 3 และ 1 ผ่านการรับรองดังนั้น 2 จึงเป็นรากดั้งเดิมที่มีส่วนที่เหลือ 5 หากแทนรายการจะเป็น 2,1,4 และ 1 ซึ่งเป็นรายการสำหรับ 4 ดังนั้น 4 จะไม่เป็น รากดั้งเดิมเนื่องจากหมายเลข 3 หายไปจากรายการ
-
ทำซ้ำขั้นตอนก่อนหน้าสำหรับจำนวนเต็มทั้งหมดที่น้อยกว่าห้า หมายเลขสามยังเป็นรากเหง้าดั้งเดิมของการพักห้า แต่ไม่มีสี่ประการ จากนั้นสองและห้าเป็นรากดั้งเดิมสำหรับห้า