เหตุใดจึงถามว่า gcd(pq,(p-1)(q-1))=1 ในรูปแบบการเข้ารหัส Paillier

คำแนะนำ: เงื่อนไข (หรือเทียบเท่า) คือ [ในเอกสารของ Paillier](https://link.springer.com/content/pdf/10.1007/3-540-48910-X_16.pdf#page=4) ใน _"ตั้งแต่ $\gcd(\lambda,n)=1$"_ ในการพิสูจน์บทแทรก 3 จะเกิดอะไรขึ้นหากไม่ตรงตามเงื่อนไขนี้ (และพิสูจน์ว่าความน่าจะเป็นของเงื่อนไขนั้นต่ำมากสำหรับโมดูลัส RSA ที่สร้างขึ้นตามอัตภาพ $n$) เหลือเพียงคำตอบ (ที่ฉันไม่ได้วางแผนที่จะเขียน) สำหรับคำถามที่น่าสนใจ นอกจากนี้ หากมีใครสามารถระบุเหตุผลสำหรับ _"ตั้งแต่"_ แทนที่จะเป็น _เพิ่มเติมโดยสันนิษฐานถึงเงื่อนไขที่มีแนวโน้มอย่างท่วมท้น_ ฉันก็อยากทราบ

$gcd(\lambda,n)=1$ และ $gcd(n,(p-1)(q-1)=1$ หมายถึงกันและกัน ดังนั้น พวกมันจึงเทียบเท่ากัน อย่างไรก็ตาม ฉันก็ยังไม่รู้ว่าทำไมถึงเป็นเช่นนั้น จำเป็น เนื่องจากในวิกิ $g$ ไม่ได้ถูกสร้างเหมือนในกระดาษของ Paillier

ไม่มีใครรู้ว่าเวอร์ชัน wiki มาจากไหน?

คำใบ้เพิ่มเติม: ถ้าเรายกตัวอย่างเล็กๆ น้อยๆ ปลอมๆ ของ $p=23$, $q=47$, $n=1081$ จะมีปัญหาที่ $1^n\equiv24^n\pmod{n^2}$, ดังนั้นอะไรก็ตามที่ $g$ เราเลือกฟังก์ชัน $\varepsilon_g:\mathbb Z_n\times\mathbb Z_n^*\to\mathbb Z_{n^2}^*$ กำหนดโดย $(x,y)\mapsto x^g y^ n\bmod n^2$ จะชนกัน

คำถามนี้เป็นภาษาอื่นๆ: