Score:1

จะเร่งการสร้างส่วนแบ่งความลับของ Shamir ได้อย่างไร

ธง sy

สมมติว่าเราต้องสร้างส่วนแบ่งลับของ Shamir สำหรับจุดข้อมูล n จุด มีวิธีเร่งการดำเนินการนอกเหนือจากการใช้กฎของ Horner สำหรับการประเมินพหุนามหรือไม่?

SEJPM avatar
us flag
การทำให้ขนานกันและการทำให้เป็นเวกเตอร์ควรเป็นไปได้เช่นกันหากคุณต้องการใช้ความพยายามมากพอ (การขนานกันอาจจะง่ายกว่าเนื่องจากลักษณะที่ขนานกันของงานนี้)
Score:1
ธง ru

หากคุณใช้การตั้งค่าทั่วไปที่มีการแบ่งปัน $f(1), f(2),\ldots f(n)$ ที่ไหน $f(x)=c_kx^k+\cdots+c_0$ เป็นพหุนามดีกรี $k$จากนั้นคุณสามารถใช้ แคลคูลัสของผลต่างจำกัด. ข้ามขั้นตอนการเริ่มต้นไปชั่วขณะ

สำหรับ j=1,...,n 
    อัปเดต f = (f + Deltaf[1]) mod หน้า
    สำหรับ i=1,..., k-1 
        อัปเดต Deltaf[i] = (Deltaf[i] + Deltaf[i+1]) mod p
    ส่งออกตัวแปร f เป็น f(j)
จบ

ห่วงหลักใช้เวลา $kn$ การเพิ่มและการเพิ่ม (คุณสามารถบันทึก $O(k^2)$ เพิ่มเติมถ้าคุณรู้สึกตระหนี่จริงๆ) ซึ่งมีประสิทธิภาพมาก

ค่าเริ่มต้นของ $f$ เป็น $ฉ(0)$. ค่าเริ่มต้นของ $\เดลต้า^if$ ค่อนข้างยุ่ง: $\Delta^if(0)=i!\sum_{j=i}^kc_jS(j,i)$ ที่ไหน $S(ญ,ผม)$ คือ หมายเลขสเตอร์ลิงชนิดที่สอง. หรือคุณสามารถประเมินสิ่งแรกได้ $k$ เงื่อนไขของ $f$ และคำนวณความแตกต่างที่วนซ้ำโดยตรงเพื่อคำนวณถัดไป $n-k$.

โพสต์คำตอบ

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