โมดูลัสที่แตกต่างกันในเลขยกกำลัง

อนุญาต $\mathbb G$ ด้วยเครื่องกำเนิดไฟฟ้า $g$เป็นลำดับไพรม์ 256 บิต $คิว$และไพรม์ 128 บิต $p$ เป็นที่รู้จักและคงอยู่

สมมติว่าเราได้อัลกอริทึม $\คณิตศาสตร์ A$ ซึ่งเมื่อป้อนข้อมูล $(h_1,h_2)\in\mathbb G^2$, กับ $h_1=g^{a_1}$, $h_2=g^{a_2}$ สำหรับการสุ่ม $a_1,a_2\in\mathbb Z_q$, เอาท์พุต $h_3=g^{a_1+a_2\bmod p}$ ด้วยความน่าจะเป็นที่ไม่หายไป ดังคำถาม

กำหนดอัลกอริทึม $\คณิตศาสตร์แคล A'$ ที่อินพุต $h\in\mathbb G$ พยายามส่งออก $y$ กับ $g^y=h$และต่อสิ่งนี้:

• วาด $u$ สุ่มเข้ามา $\mathbb Z_q$,คำนวณ $h_1=g^u\;h$ซึ่งตอนนี้สุ่มเข้ามาแล้ว $\mathbb G$; จึงมีเอกลักษณ์เฉพาะตัว (ยังไม่ทราบ สุ่ม) $a_1\in\mathbb Z_q$ กับ $g^{a_1}=h_1$
• วาด $a_2$ สุ่มเข้ามา $\mathbb Z_q$,คำนวณ $h_2=g^{a_2}$
• วิ่ง $\คณิตศาสตร์ A$ ด้วยการป้อนข้อมูล $(h_1,h_2)$ได้รับ $h_3$ สันนิษฐานว่าเป็น (ด้วยความน่าจะเป็นที่ไม่หายไป) $g^{a_1+a_2\bmod p}$
• พบ $x\in\mathbb Z_q$ กับ $0\le x<p<2^{128}$ ดังนั้น $ก^x=h_3$ซึ่งกำหนดให้ในลำดับที่ $2^{66}$ การดำเนินการกลุ่มโดยใช้ โรโฮของโพลาร์ด มีจุดเด่น หน่วยความจำน้อย และกระจายได้ง่าย
• คำนวณ $r=x-a_2\bmod p$; มันถือ $a_1\equiv r\bmod p$, และ $0\le a_1<q$; ให้ (sd ยังไม่ทราบ) $s\in\left[0,\left\floor q/p\right\rfloor\right]$ เป็นอย่างนั้น $a_1=r+s\,p$, ดังนั้น $g^{r+s\,p}=h_1$, ดังนั้น $g^{s\,p}=h_1\,g^{q-r}$, ดังนั้น $g^s=(h_1\,g^{q-r})^{p^{-1}\bmod q}$
• คำนวณ $h_4=(h_1\,g^{q-r})^{p^{-1}\bmod q}$; มันถือ $g^s=h_4$ และ $s<2^{129}$
• พบ $s$ โดยหลักวิธีเดียวกับ $x$
• คำนวณ $a_1=r+s\,p$ซึ่งก็เป็นอย่างนั้น $g^{a_1}=h_1$
• คำนวณและส่งออก $y=a_1-u\bmod q$ซึ่งเป็นอย่างนั้น $g^y=h$.

อัลกอริทึมของเรา $\คณิตศาสตร์แคล A'$ จึงสามารถคำนวณลอการิทึมแยกได้ $y$ เพื่อฐาน $g$ ของธาตุใดธาตุหนึ่ง $h$ ใน $\mathbb G$ ด้วยความน่าจะเป็นที่ไม่หายไปและผลงานเล็กน้อยที่เป็นไปได้ นี่เป็นสมมติฐานที่เป็นไปไม่ได้ ดังนั้นสมมติฐานของเราว่า $\คณิตศาสตร์ A$ มีอยู่เป็นเท็จ

เราจึงตอบคำถามในแง่ลบ