มีหมายเลขเฉพาะที่ง่ายต่อการโมดูโลภายใน 40 บิตถึง 60 บิตหรือไม่

ฉันต้องการใช้โครงร่างการเข้ารหัสที่ใช้ LWE ซึ่งเป็นโมดูโล $คิว$ สามารถย่อยสลายได้เป็น $q = q_0\cdot q_1\cdots q_k$ ตาม CRT. ฉันเดาว่าเลขคณิตแบบโมดูลาร์โดย $q_i$ เป็นการดำเนินการหลัก ดังนั้นฉันจึงพยายามเลือก Mersenne Prime อย่างไรก็ตาม มีเพียงสองจำนวนเฉพาะเท่านั้นที่พึงพอใจ: $2^{31}-1$ และ $2^{61}-1$.

มีช่วงเวลาเฉพาะอื่น ๆ เช่น $2^n-b$ ที่ง่ายต่อการโมดูโล (ควรอยู่ระหว่าง $2^{40}$ และ $2^{60}$)?

ประการแรก เห็นได้ชัดว่าสิ่งนี้เป็นจริงโดยไม่มีข้อจำกัด $ข$. ตัวอย่างเช่นสำหรับ $b = 2^n-2$ เราได้รับสิ่งนั้น $2^n - b = 2^n - (2^n-2) = 2$ เป็นนายก สิ่งนี้น่าเบื่อและอาจไม่ใช่สิ่งที่คุณหมายถึง (แต่ฉันคิดว่าคุณต้องการ $ข$ เล็ก).

น้อยแค่ไหน $ข$ เราควรคาดหวังว่าสิ่งนี้จะคงอยู่ต่อไปหรือไม่? การตีความทฤษฎีบทจำนวนเฉพาะประการหนึ่งคือจำนวนเฉพาะมี "ความหนาแน่น $1/\ln x$". กล่าวคือเมื่อ $x = 2^{40}$ ถึง $2^{60}$เรา (ประมาณ) คาดหวัง $\ประมาณ 1/40$ ถึง $1/60$ ตัวเลขที่เป็นจำนวนเฉพาะ มีหลายวิธีในการทำให้สิ่งนี้เป็นทางการ (ขึ้นอยู่กับว่าคุณเชื่อในสมมติฐานของ Riemann หรือไม่) ดู หน้านี้ โดยเฉพาะส่วน "ข้อมูลทั่วไป".

อย่างไรก็ตาม Takeaway ควรเป็นอย่างนั้น

1. จำนวนเฉพาะค่อนข้าง "มากมาย" ดังนั้น
2. หากต้องการค้นหาจำนวนเฉพาะ (ในรูปแบบที่คุณต้องการ) ให้ "ดูสิ"

นี่คือการบอกว่าเป็นเรื่องง่ายที่จะเขียนโปรแกรมที่ค้นหาค่าบวกที่น้อยที่สุด $ข$ ดังนั้น $2^n-b$ เป็นนายก ต่อไปนี้คือโปรแกรม Sage และควรแสดงให้เห็นว่าสิ่งต่างๆ เรียบง่ายเพียงใด (หากมีการใช้การทดสอบเบื้องต้น)

def find_b(n):
    คิว = 2**น
    ข = 0
    ในขณะที่ไม่ใช่ (qb).is_prime():
        ข += 1
    กลับ ข

ตามที่คุณสนใจในกรณีของ $2^{40}$ ถึง $2^{60}$ฉันได้คำนวณสิ่งเหล่านั้นให้คุณแล้วด้านล่าง

[(40, 87), (41, 21), (42, 11), (43, 57), (44, 17), (45, 55), (46, 21), (47, 115), (48, 59), (49, 81), (50, 27), (51, 129), (52, 47), (53, 111), (54, 33), (55, 55), (56, 5), (57, 13), (58, 27), (59, 55), (60, 93)].

รูปแบบข้อมูลก็คือ $(ก,ข)$ หมายถึงตัวเลข $2^a-b$ตัวอย่างเช่น รายการแรกคือตัวเลข $2^{40}-87$. ตัวเลขทั้งหมดในรายการด้านบนเป็นจำนวนเฉพาะ นอกจากนี้ ทางเลือกของ $ข$ ในข้างต้นคือ (ดังที่กล่าวไว้ก่อนหน้านี้) เป็นทางเลือกที่น้อยที่สุดเสมอ $(ก,ข)$ เป็นนายก การดำเนินการโปรแกรมนี้มีประสิทธิภาพมาก ใช้เวลาเพียงเสี้ยววินาทีบนเดสก์ท็อปของฉัน

ทั้งหมดที่กล่าวมา โครงสร้างที่แม่นยำของ $q_i$ ที่ยอมรับว่าเลขคณิตที่มีประสิทธิภาพนั้นซับซ้อนกว่าที่คุณอธิบายเล็กน้อย อย่างน้อยก็เมื่อทำสิ่งต่าง ๆ ประเภท Ring-LWE (โดยที่คุณใช้เลขคณิตพหุนาม) ที่นี่ ความสามารถในการใช้การแปลงตามทฤษฎีเชิงตัวเลข (แม้ว่าจะมีเพียงการแปลงที่ "ไม่สมบูรณ์") นั้นมีประโยชน์มากทีเดียว สิ่งนี้กำหนดข้อกำหนดที่เข้มงวดพอสมควรสำหรับรูปแบบโมดูลัสที่แม่นยำที่เลือก (สำหรับ NTT ที่สมบูรณ์ คุณต้องใช้ $q\equiv 1\bmod 2n$ เมื่อทำงานใน $\mathbb{Z}_q[x]/(x^n+1)$ ไออาร์ซี). ดังที่ได้กล่าวไปแล้ว การเพิ่มประสิทธิภาพเหล่านี้อาจเกี่ยวข้องกับทางเทคนิคมากกว่าเล็กน้อย ดังนั้นควรข้ามไปในตอนแรกเมื่อเรียนรู้เกี่ยวกับการเข้ารหัส

ฉันต้องการใช้โครงร่างการเข้ารหัสที่ใช้ LWE ซึ่งเป็นโมดูโล $คิว$ สามารถย่อยสลายได้เป็น $q = q_0\cdot q_1\cdots q_k$ ตาม CRT.

ที่จริงแล้ว เพื่อให้ CRT ทำงานได้ สิ่งที่จำเป็นก็คือปัจจัยต่างๆ นั้นค่อนข้างเป็นจำนวนเฉพาะ พวกมันไม่จำเป็นต้องเป็นจำนวนเฉพาะทีละตัว $2^x-1$ และ $2^y-1$ จะค่อนข้างสำคัญเมื่อใดก็ตามที่ $x$ และ $y$ เป็น; ดังนั้นสิ่งที่คุณต้องมีคือชุดเลขชี้กำลังจากช่วง $[40, 60]$ ที่ค่อนข้างเป็นไพร์ม

ทางเลือกหนึ่งที่ชัดเจนคือการใช้ปัจจัย $2^{p}-1$ สำหรับ $p \in \{41, 43, 47, 49, 53, 55, 57, 58, 59\}$ (ซึ่งฉันเชื่อว่าเป็นชุดของค่าเฉพาะร่วมกันจากช่วงที่มีผลรวมสูงสุด) ที่อาจเพียงพอต่อความต้องการของคุณ (หาก $q \ประมาณ 2^{462}$ มากพอสมควร)