การลด Barret เพื่อให้ได้จำนวน 64 บิตที่เหลือจากจำนวน 128 บิต

รหัสของคำถามคำนวณ 64 บิต รับ<2>(I)=$h:=f\,g\bmod n$ จากอินพุต:

• 64 บิต โมดูลัส_ค่า=$n$ กับ $n\in[2,\,2^{63}]$
• 64 บิต รับ<0>(I)=$f$ กับ $f\in[0,\,2^{64}-1]$
• 64 บิต รับ<1>(I)=$g$ กับ $g\in[0,\,2^{64}-1]$ และ $f\,g<2^{64}\,n$เงื่อนไขที่เป็นไปตามถ้า $f,g\in[0,\,n-1]$ (ซึ่งฉันคิดว่าเป็นกรณีนี้เสมอในแอปพลิเคชัน)

ผลลัพธ์ $h$ คือส่วนที่เหลือของการหารแบบยุคลิดของ $f\,ก$ โดย $n$. ถูกกำหนดโดยทางคณิตศาสตร์ $0\le ชั่วโมง<m$ และ $\exists q\in\mathbb Z,\ f\,g=q\cdot n+h$.

รหัสจะคำนวณ 128 บิตก่อน ซี$=z:=f\,g$แล้วผลลัพธ์ รับ<2>(I)$=h:=z\bmod n$ โดย การลดบาร์เร็ตต์:

• มันถูกคำนวณล่วงหน้า (ภายนอกกับรหัสของคำถาม) const_ratio$=r=\left\lfloor2^{128}/n\right\rfloor$
• $\hat q:=\left\lชั้น z\,r/2^{128}\right\rชั้น$ซึ่งถูกต้อง $คิว$ ภายในหนึ่งโดยค่าเริ่มต้น (หมายเหตุ: $\หมวก q$ เป็นค่าสุดท้ายของตัวแปร tmp1).
• $\หมวก h:=z-q\cdot n$ซึ่งถูกต้อง $h$ ภายในอาจเกินพอดี $n$ (บันทึก: $\หมวก h$ เป็นค่าสุดท้ายของตัวแปร tmp3).
• $h:=\หมวก h-n$ เมื่อไร $\หมวก h\ge n$, หรือ $h:=\หมวก h$ มิฉะนั้น.

รหัสนี้ใช้อัลกอริทึมของโรงเรียนประถมศึกษาในการคำนวณเลขหลายหลักโดยเปลี่ยนจากฐาน $10$ เพื่อฐาน $2^{64}$ (ด้วยการเพิ่มประสิทธิภาพและรายละเอียดปลีกย่อยในส่วนถัดไป) สิ่งที่เทียบเท่ากับตัวเลขเรียกว่า แขนขาที่นี่ 64 บิต

ผลิตภัณฑ์ ซี$=z$ แสดงเป็นสองแขนขา ซี[0]$=z_0$ (ลำดับต่ำ), ซี[1]$=z_1$ (ลำดับสูง) ด้วยประการฉะนี้ $z=z_0+2^{64}\,z_1$, และ $z_0, z_1\in[0,\,2^{64}-1]$.

ตัวคูณ Barrett const_ratio$=r=\left\lfloor2^{128}/n\right\rfloor$ แสดงออกมาในทำนองเดียวกันเป็นสองแขนขา const_ratio_0$=r_0$ และ const_ratio_1$=r_1$ขอบคุณค่าต่ำสุดของช่วงเวลาในเงื่อนไขเบื้องต้น $n\in[2,\,2^{63}]$.

ผลิตภัณฑ์ตัวกลาง $z\,r$ พอดีกับสามขาเสมอ (แม้ว่าโดยทั่วไปแล้วผลิตภัณฑ์ของปริมาณสองที่แสดงเป็นสองขาจะต้องใช้สี่ขา)

ผลหารเบื้องต้นโดยค่าเริ่มต้น $\หมวก q$ เหมาะกับแขนขาเดียวตั้งแต่ $\หมวก q\le q$ และ $q<2^{64}$โดยมีผู้ประกันตนรายล่าสุดตามเงื่อนไขเบื้องต้นในการป้อนข้อมูล $f\,g<2^{64}\,n$.

ส่วนที่เหลือเบื้องต้น $\หมวก h$ เหมาะกับแขนขาเดียวตั้งแต่ $\หมวก ชั่วโมง<2n$ และ $2n\le2^{64}$ตามมาด้วยจุดสิ้นสุดสูงของช่วงเวลาในเงื่อนไขเบื้องต้น $n\in[2,\,2^{63}]$.

รายละเอียดอัลกอริทึมของโค้ด (ตามที่ถามใน ความคิดเห็น และค่าหัว):

ฉันจะใช้ภาพประกอบเป็นทศนิยม ในฐานนั้นเป็นต้นมา $2\le n\le10/2$, const_ratio$=r$ สามารถเป็นได้ $\left\lfloor100/2\right\rfloor=50$, $\left\lfloor100/3\right\rfloor=33$, $\left\lfloor100/4\right\rfloor=25$, $\left\lfloor100/5\right\rfloor=20$แต่ฉันจะเสแสร้ง const_ratio$=r=29$ เพราะนั่นเป็นตัวอย่างที่น่าสนใจกว่า ด้วยเหตุผลเดียวกันฉันจะใช้ ซี$=z=34$แม้ว่าจะไม่ได้เป็นผลคูณของเลขสองหลักก็ตาม

ผลิตภัณฑ์ ซี ได้รับในรหัสโดย multiply_uint64(รับ<0>(I), รับ<1>(I), z) เป็นสองขา ซี[0] และ ซี[1].

เนื้อของการคำนวณคือ $\hat q:=\left\lชั้น z\,r/2^{128}\right\rชั้น$. นั่นคืออะนาล็อกในฐาน $2^{64}$ ของ $9:=\left\floor29\cdot34/100\right\rfloor$ ในฐาน 10 อาร์กิวเมนต์ทั้งสอง $29$ และ $34$ ในการคูณเป็นตัวเลขสองหลัก แต่มีขนาดเล็กพอที่ผลคูณของมัน $986$ เป็นตัวเลขสามหลัก (แทนที่จะเป็นสี่) และเราสนใจเฉพาะตัวเลขที่สามจากด้านขวาเท่านั้น อัลกอริทึมของโรงเรียนประถมศึกษาในการคำนวณ $986:=29\cdot34$ จะนำเสนอเป็น

      2 9 const_ratio
   x 3 4 ซ
    -----
    1 1 6
+ 8 7
  -------
    9 8 6

ในอัลกอริทึมของโรงเรียนประถมมีการคูณเลขหลักเดียวสี่ตัว (ซึ่งรหัสดำเนินการ) และการดำเนินการพิเศษบางอย่าง (ที่รหัสจัดระเบียบใหม่เล็กน้อย):

• 4 ครั้ง 9, 36; เขียน 6, เก็บไว้ 3;
• 4 ครั้ง 2, 8; บวก 3 (เก็บไว้), 11; เขียนว่า.
• 3 ครั้ง 9, 27; เขียน 7, เก็บไว้ 2;
• 3 ครั้ง 2, 6; บวก 2 (เก็บไว้), 8; เขียนว่า.

การคูณครั้งแรกในสี่ครั้งนี้เกิดขึ้นในโค้ดแฟรกเมนต์ multiply_uint64_hw64(z[0], const_ratio_0, &พกพา)ซึ่งคูณแขนขาลำดับต่ำของ $r$ ด้วยแขนขาลำดับต่ำของ $z$เหมือนเราคูณเลขลำดับต่ำ 4 ของ 34 ด้วยเลขลำดับต่ำ 9 ของ 29. สังเกตว่า "เขียน 6" ไม่มีประโยชน์ในกรณีนี้ เนื่องจากหลักใดก็ตามที่เขียนจะถูกแยกออกจากกันในคอลัมน์ด้านขวาของการคำนวณโดยไม่มีโอกาสที่จะส่งผลต่อหลักซ้ายสุด และจะไม่สนใจเมื่อเราหารด้วย 100 และปัดเศษลง (เท่ากับ เก็บเฉพาะหลักที่สามจาก ด้านขวา) นั่นเป็นสาเหตุที่ผลิตภัณฑ์ 128 บิตลำดับต่ำ 64 บิตไม่ได้รับการคำนวณด้วยซ้ำตามที่ระบุไว้ในคำถาม เทียบเท่ากับ 3 ใน 36 ถูกเก็บไว้ใน พก.

การคูณครั้งที่สองเกิดขึ้นใน multiply_uint64(z[0], const_ratio_1, tmp2)ซึ่งคูณแขนขาลำดับสูงของ $r$ ด้วยแขนขาลำดับต่ำของ $z$โดยมีผลให้แขนขาทั้งสองของ tmp2; 64 บิต ทีเอ็มพี[0] ได้รับเทียบเท่ากับ 8 ใน 8, และ ทีเอ็มพี[1] ได้รับเทียบเท่ากับ 0 สำหรับ (สังเกตนำหน้า 0 ถูกระงับในการเขียนเลขจำนวนเต็มฐานสิบแบบเดิม) เท่ากับ 8 บวก 3 เกิดขึ้นใน add_uint64(tmp2[0], พกพา, &tmp1)ด้วยตัวเลขลำดับต่ำ 1 ของผลลัพธ์ 11 ใน tmp1และพกพาใหม่ 1 ในเอาต์พุตของฟังก์ชันนั้น ที่ใช้เป็นตัวถูกดำเนินการใน tmp3 = tmp2[1] + â¦ (ซึ่งถูกข้ามไปในอัลกอริทึมของโรงเรียนประถมด้วยตัวอย่างเฉพาะที่ฉันเอามาตั้งแต่ 0 ถูกระงับ) ให้ผลเท่ากับฝ่ายซ้าย 1 ใน 116. [หมายเหตุเกี่ยวกับผลลัพธ์ของ add_uint64: มันถูกสร้างขึ้นโดย static_cast<ถ่านที่ไม่ได้ลงนาม>(ผลลัพธ์* <ตัวถูกดำเนินการ1)ซึ่งเปรียบเทียบ *ผลลัพธ์ และ ตัวถูกดำเนินการแล้วเลี้ยว จริง ถึง 1, เท็จ ถึง 0. ทำหลังจาก *ผลลัพธ์ = ตัวถูกดำเนินการ 1 + ตัวถูกดำเนินการ 2ที่บอกว่าการเพิ่มนี้ทำให้เกิดการพกพาหรือไม่ คอมไพเลอร์บางคนรู้จักสำนวนนี้ ใช้บิต C ของคำสถานะ และใช้ C ซ้ำในส่วนเพิ่มเติมที่กำลังจะมาถึง]

การคูณครั้งที่สามเกิดขึ้นใน multiply_uint64(z[1], const_ratio_0, tmp2)ซึ่งคูณแขนขาลำดับต่ำของ $r$ ด้วยกิ่งก้านสาขาระดับสูงของ $z$มีผลให้แขนขาใน tmp2เหมือนที่เราทำ 3 x 9 = 27. เวลานี้เราต้องการทั้งแขนขา/หลัก: เทียบเท่ากับ 7 ไปที่ tmp2[0] และเทียบเท่ากับ 2 ไปที่ tmp2[1]. นี่คืออัลกอริทึมของโรงเรียนประถมที่แตกต่างกัน: เพิ่มทันที tmp1 (เทียบเท่าของกลาง 1 ใน 116) ไปสู่กิ่งก้านลำดับต่ำด้วย add_uint64(tmp1, tmp2[0], &tmp1)มีประสิทธิภาพเทียบเท่ากับ 1 + 7 = 8,ไม่มีพกพา. ผลลัพธ์ 8 ถูกเก็บไว้ใน tmp1 เพราะความหมายของ add_uint64 ต้องการปลายทาง แต่จริงๆ ไม่สนใจ เพราะเราไม่สนใจหลักกลางใน 986. การส่งออกโดย add_uint64 ใช้เป็นตัวถูกดำเนินการใน พกพา = tmp2[1] + â¦มีประสิทธิภาพเทียบเท่ากับ 1 + 0 = 1 ในตัวอย่างของเรา แม้จะมีชื่อ พกที่เก็บแขนขา/หลัก 64 บิตเต็มรูปแบบ

การคูณที่สี่เกิดขึ้นใน z[1] * const_ratio_1ซึ่งคูณแขนขาลำดับสูงของ $r$ ด้วยกิ่งก้านสาขาระดับสูงของ $z$เหมือนที่เราทำ 3 x 2 = 6. ในที่นี้ บริบทรับประกันว่าผลลัพธ์จะพอดีกับแขนขาเดียว ดังนั้นจึงสามารถใช้โอเปอเรเตอร์ C ดั้งเดิมสำหรับการคูณได้ ผลลัพธ์จะถูกใช้เป็นตัวดำเนินการด้านซ้ายของ ⦠+ tmp3 + พกพามีประสิทธิภาพเทียบเท่ากับ 6 + 1 + 1 = 8. บริบทอีกครั้งรับประกันค่านี้ $\หมวก q$,เก็บไว้ใน tmp1พอดีกับแขนขา/หลักเดียว

แล้ว tmp3 = z[0] - tmp1 * โมดูลัส_ค่า ดำเนินการ $\หมวก h:=z-q\cdot n$. บริบทรับประกันว่าผลลัพธ์ที่แน่นอนทางคณิตศาสตร์จะพอดีกับแขนขา/หลักเดียว (เก็บไว้ใน tmp3) แม้ว่า $q\cdotn$ ไม่. สิ่งนี้ทำให้สามารถใช้ตัวดำเนินการเนทีฟ C ซึ่งข้ามการคำนวณส่วนที่มีลำดับสูงไปโดยสิ้นเชิง

แล้ว SEAL_COND_SELECT(tmp3 >= modulus_value, tmp3 - modulus_value, tmp3) คำนวณ $h$ จาก $\หมวก h$ โดยการลบอย่างมีเงื่อนไข $n$ เมื่อไร $\หมวก h\ge n$. ตัวดำเนินการการเลือกถูกซ่อนอยู่ในแมโคร

สองตัวอย่างสำหรับฐาน $2^{64}$ (ค่าเป็นเลขฐานสิบหกแบบ big-endian โดยมีช่องว่างระหว่างรยางค์):

โมดูลัส_ค่า 000076513ae0b1cd
const_ratio 00000000000229e6 7f4ca82ba3a115f1
รับ<0>(I) 00005f0fd669f2c7
รับ<1>(I) 000041a1f91ef16f
z 00000000185f2ae8 a455846cb7cf9b49
tmp1 000034bb854f9a8d
tmp3 00000fcebfd55b60
รับ<2>(I) 00000fcebfd55b60

โมดูลัส_ค่า 686f4b7702a9c775
const_ratio 0000000000000002 7387d66ffd685b82
รับ<0>(I) 536094611fa2b19b
รับ<1>(I) 675ef5187093ff63
z 21aac8fcf31d6421 62e675ba16d513f1
tmp1 5287278703394bb1
tmp3 72b1d3d2b9f5e50c
รับ<2>(I) 0a42885bb74c1d97

หมายเหตุ: สำหรับ $n\in[2^{63}+1,\,2^{64}-1]$, ปริมาณ $\หมวก h$ สามารถล้นแขนขาหนึ่งและรหัสในขณะที่มันล้มเหลว เช่น. สำหรับการป้อนข้อมูล $f=g=2^{32}$, เราได้รับ $z=2^{64}$ ดังนั้น $\หมวก q=0$ (สำหรับใดๆ $n>2^{63}$), ดังนั้น $\หมวก h=z=2^{64}$ และเอาต์พุตของ $0$ มากกว่าที่จะเป็นความจริง $h=2^{64}-n$. แหล่งที่มาแบบเต็มมีความคิดเห็น "คลาสโมดูลัสแสดงถึงโมดูลัสจำนวนเต็มที่ไม่ใช่ค่าลบสูงถึง 61 บิต" ดังนั้นปัญหาดังกล่าวสำหรับขนาดใหญ่ $n$ จะเกิดขึ้นเฉพาะเมื่อรหัสการโทรผิดพลาดเท่านั้น นอกจากนี้ ถ้าผมเข้าใจถูกต้อง $n=2^{60}-2^{14}+1$ เป็นเป้าหมายหลัก

ทางเลือก: สำหรับสิ่งที่ทำหน้าที่เดียวกันกับรหัสของคำถาม ในรหัสสั้นๆ 4 บรรทัดแทน 11 สำหรับทั้งหมด $n\in[1,\,2^{64}-1]$ไม่จำเป็นต้องมีการคำนวณล่วงหน้า อาจเร็วกว่า แต่เข้ากันได้กับคอมไพเลอร์ x64+CPU ล่าสุดเท่านั้น ดูส่วนแรกของ ข้อมูลโค้ดเหล่านี้ (อันที่สองคือตัวแปรขนาดเล็กที่ไม่มีข้อจำกัด $f\,g<2^{64}\,n$ ). ฉันไม่ได้แถลงเกี่ยวกับความคงที่ของรหัสทั้งสอง