การหารากของพหุนาม $X^2 - X + 19$ ใน $\mathbb Z/61 \mathbb Z$
Aug 18 2020
สำหรับ $p = 61$.
ฉันได้รับรากของ $X^2 + 3$ ใน $\mathbb Z/p \mathbb Z$ซึ่ง ได้แก่ $\pm 27 + p\mathbb Z$.
ฉันจะต้องหารากของ $X^2 - X + 19$ ใน $\mathbb Z/p\mathbb Z$ซึ่งฉันได้พบโดยไม่ต้องใช้ข้อมูลก่อนหน้านี้
อย่างไรก็ตามฉันควรใช้ข้อมูลที่กำหนดเพื่อค้นหารากของไฟล์ $X^2 - X + 19$ ใน $\mathbb Z/p\mathbb Z$ซึ่งฉันไม่รู้ว่าจะก้าวต่อไปอย่างไร
คำตอบ
1 J.W.Tanner Aug 18 2020 at 11:49
เติมเต็มกำลังสอง
$X^2-X+19\equiv0\bmod61\iff 4X^2-4X+76\equiv0\bmod61$
$\iff (2X-1)^2\equiv-75=-3\times 5^2 \bmod61$
$\iff 2X-1\equiv\pm27\times5\bmod61$.
เอาไปจากที่นี่ได้ไหม