Score:1

วิธีการเลือก Smoothness Bound ที่เหมาะสมโดยใช้วิธี Index Calculus

ธง et

ในขณะที่ใช้งาน Quadratic Sieve หนังสือเรียนจะให้สูตรคร่าวๆ ว่าคุณควรใช้ Smoothness bound ใดใน Factor Base ของคุณ

ในการแยกตัวประกอบจำนวน N โดยใช้ Quadratic Sieve เราสามารถใช้สิ่งต่อไปนี้:

$L = e^{\sqrt {\ln(N)ln(ln(N))}}$, $B = L^{\frac {1}{\sqrt 2}}$

สำหรับวิธี Index Calculus สำหรับแก้ปัญหา Discrete Log in $\mathbb F_p$มีสูตรที่คล้ายกันหรือไม่? หลายข้อความที่ฉันตรวจสอบ แค่บอกว่าเลือกความเรียบของขอบ B ที่เหมาะสม แต่ไม่ได้ระบุถึงวิธีการเลือก B ที่เหมาะสม

Score:1
ธง pe

Coppersmith, Odlyzko และ Schroeppel ตั้งไว้แต่เดิม $B = L[1/2, 1/2]$ สำหรับตะแกรงเชิงเส้นและตะแกรงเสียน ปอมเมอเรนซ์ ชุด $B = L[1/2, 1/\sqrt{2}]$ สำหรับตัวแปรแคลคูลัสดัชนีอย่างเข้มงวดโดยใช้วิธีเส้นโค้งวงรีเป็นวิธีการทดสอบความเรียบ

ขอบเขตเหล่านี้ไม่มีซีมโทติคเท่านั้น ขอบเขตในการใช้งานมักจะถูกปรับเพื่อบัญชีสำหรับประสิทธิภาพจริงที่ไม่ใช่ซีมโทติคของรูทีนย่อยที่เกี่ยวข้อง

et flag
ฉันลองใช้สูตรนี้กับตัวอย่างที่แก้ไขแล้วในหนังสือบางเล่ม & ผลลัพธ์ดูเหมือนจะค่อนข้างแตกต่างจากตัวอย่างที่ใช้ ตัวอย่างเช่นในหนังสือวิทยาการเข้ารหัสลับทางคณิตศาสตร์ของซิลเวอร์แมน เขาแก้ $37^x \equiv 211 \pmod 18443$ ถ้าฉันใช้สูตร $B = L^{\frac {1}{\sqrt 2}}$ ฉันจะได้ 28.5 อย่างไรก็ตาม เพื่อแก้ปัญหานี้ Silverman ใช้ B=5 ซึ่งค่อนข้างห่างไกลจาก B ที่คำนวณได้ Silverman ยังมีโจทย์แบบฝึกหัด $17^x \equiv 19 \pmod 19079$ โดยที่ B คำนวณได้คือ 28.5 แต่ฉันก็ทำได้ เพื่อแก้ปัญหาอีกครั้งโดยใช้ B=5
et flag
คุณหมายถึงอะไรโดย ` เลิกก่อนกำหนดในฐานะเครื่องทดสอบความเรียบ `?
et flag
ทำไมถึงมี 2 สูตร เช่น ทำไม $B = L[1/2, 1/\sqrt{2}]$ - $L^{1/2}$ คืออะไร
pe flag
หากคุณกำลังดูหนังสือของ Silverman การสิ้นสุดของหัวข้อ 3.8 ในหน้า 169 น่าจะตอบคำถามของคุณได้ อย่าให้ความสนใจกับพารามิเตอร์ในตัวอย่างมากนัก พารามิเตอร์เหล่านี้ได้รับการปรับให้เหมาะสมเพื่อความชัดเจนมากกว่าประสิทธิภาพ (กล่าวคือ มันจะดูแย่กว่าสำหรับตัวอย่างที่ใช้งานได้หากมีจำนวนเฉพาะมากเกินไป ต้องการความสัมพันธ์มากขึ้น เป็นต้น)
pe flag
$L[1/2, 1/\sqrt{2}]$ เป็น [L-notation](https://en.wikipedia.org/wiki/L-notation) ที่กว้างกว่า มีความหมายเหมือนกับ $L^{1/\sqrt{2}}$ ของคุณ
et flag
ขอบคุณ คุณช่วยบอกฉันด้วยว่าคุณหมายถึงอะไรด้วยคำว่า `กับการเลิกก่อนกำหนดในฐานะเครื่องทดสอบความเรียบ'
pe flag
ไม่เป็นไร ฉันสับสนกับกระดาษ Pomerance อื่น นี่เป็นเพียง ECM แต่นั่นไม่สำคัญมากเกินไป การแบ่งการทดลองใช้งานก็จะใช้งานได้เช่นกัน โดยมีรันไทม์ที่ค่อนข้างแย่กว่า

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา