Score:0

กำหนดชุด $g^n \mod P$ สามารถกำหนดสมาชิกที่ต่อเนื่องกันเป็นค่าที่ไม่ซ้ำกันซึ่งหากได้รับค่าที่ไม่ซ้ำกันถัดไปและก่อนหน้าสามารถคำนวณได้

ธง at

ให้นายกที่ปลอดภัย $พี$ และเครื่องกำเนิดไฟฟ้า $g$ ซึ่งสร้างค่าทั้งหมดจาก $1$ ถึง $P-1$ กับ $$g^n \mod P$$

1.) ตอนนี้มีฟังก์ชั่น $f$ ซึ่งกำหนดค่าเฉพาะให้กับช่วงของสมาชิก

$$f(g^{i-a_i},...,g^{i+b_i}) = f(g^i) = v_{ia_ib_i}$$

2.) ให้ค่าเฉพาะดังกล่าว $v_{ia_ib_i}$ ชดเชยต่อไป $g^{q_i}$ และก่อนหน้านี้ $g^{-q'_i}$ สามารถคำนวณ/ประมาณได้ในเวลาค่อนข้างเร็ว (ชั่วโมง)


ตัวอย่าง:
ให้ค่าเฉพาะเหล่านั้นเป็นสมาชิกกลุ่มด้วย $g^k \equiv 0 \mod 10,000$.
การมอบหมาย (1.) จะเป็นค่าที่ใกล้เคียงที่สุด
ขณะนี้มีวิธีคำนวณค่าชดเชยที่เล็กที่สุดหรือไม่ $t$ เพื่อหาค่าเฉพาะถัดไป $g^r \equiv 0 \mod 1,000 $ กับ $$g^k\cdot g^t = g^r$$ เหมือนกันสำหรับค่าเฉพาะก่อนหน้า (ทั้งที่มี $|t| \นาที$)


รายละเอียดเพิ่มเติม:

  • จำนวนค่าที่ไม่ซ้ำกันจะน้อยกว่ามาก $พี$
  • จะมีการสุ่มหมายเลขที่ไม่ซ้ำกันหนึ่งหมายเลขเสมอ คำนวณงานที่ได้รับมอบหมาย 1.) ไม่จำเป็นต้องเร็ว (ฉันเดาว่าหากมีวิธีแก้ไขบางอย่างก็ไม่สามารถแก้ไขได้อย่างรวดเร็วมิฉะนั้นการแก้ dlog จะง่าย)
  • 2.) ไม่จำเป็นต้องเป็นการคำนวณที่แน่นอนการค้นหาบางประเภทระหว่างชุดค่าที่เป็นไปได้เล็กน้อยก็ใช้ได้เช่นกัน แต่จำเป็นต้องนำไปสู่ค่าเฉพาะถัดไป/ก่อนหน้าเสมอ
  • ไม่จำเป็นต้องกำหนดสมาชิกกลุ่มทุกคนให้เป็นค่าเฉพาะดังกล่าว - ความยาวของช่วงเวลา ($a+b+1$) ควรแตกต่างกัน (ในกรณีส่วนใหญ่) สำหรับค่าที่ไม่ซ้ำกัน

ดังนั้นทุกค่าที่สามารถสร้างขึ้นด้วย $g^{i-a_i}$ ถึง $g^{i+b_i}$ ได้รับมอบหมายให้ $f(ก^i)$.

เว้นแต่การกำหนดจะเปลี่ยนช่วงเวลา ($a,ข$) ก็เปลี่ยนไปทีละอย่างเช่นกัน ดังนั้นสำหรับ $g^{i+1}$: $$a_{i+1} = a_i +1$$ $$b_{i+1} = b_i -1$$ ($b = 0$ จะเป็นเส้นขอบของงาน)

kelalaka avatar
in flag
ค่าที่ไม่ซ้ำกันต้องไม่เล็กกว่า $p$ ข้อโต้แย้งนั้นชัดเจน จำนวนช่วงเวลาคืออะไร? ให้พิจารณา $a\times b$ เป็นกริดที่มี $a$ และ $b$ จาก 1 ถึง $p$ จากนั้นเราจะเห็นรูปสามเหลี่ยมเติมเต็มค่าเฉพาะซึ่งอยู่ที่ประมาณ $p^2/2$ หากคุณปล่อยให้ $i$ เป็นตำแหน่งว่างในช่วงนั้น เราก็ต้องการค่าเฉพาะที่สูงกว่ามาก โปรดทราบว่าฉันไม่ได้คำนวณอย่างแม่นยำ
J. Doe avatar
at flag
จำนวนช่วงเวลาจะเท่ากับจำนวนของค่าเฉพาะเหล่านั้น ด้วยเหตุนี้ ช่วง $a_i,b_i$ จึงถูกกำหนดด้วย $i$ พวกเขามีดัชนีเพราะอาจแตกต่างกันสำหรับทุกๆ $i$ ในกรณีส่วนใหญ่ ถ้า $i$ เปลี่ยนทีละ 1 และ $a,b$ ก็เปลี่ยนแค่อันเดียว พวกเขาจะเปลี่ยนเป็นจำนวนเงินที่มากขึ้นหากการมอบหมายเปลี่ยนแปลงเช่นกัน ฉันเพิ่มข้อความบางส่วนเพื่อให้ชัดเจนยิ่งขึ้น
kodlu avatar
sa flag
ประการแรก คุณไม่สามารถสร้าง $0$ ด้วย $g^n$ เนื่องจาก $g$ ไม่ใช่ศูนย์ และไม่มี $g$ หาร $P$ ซึ่งเป็นจำนวนเฉพาะประการที่สอง ความสามารถในการทำในสิ่งที่คุณแนะนำจะบ่งบอกถึงการโจมตีอย่างรวดเร็วอย่างหนาแน่นบน Discrete Log ดังนั้นจึงไม่น่าจะมีอยู่จริง โดยอิงตามหลักฐานปัจจุบันทั้งหมดสำหรับปัญหา DL ในกลุ่มไพรม์ขนาดใหญ่ ไม่มีฟังก์ชันง่ายๆ ที่รักษาช่วงเวลา นั่นคือจุดรวมของการยกกำลังที่นำไปสู่บันทึกที่ไม่ต่อเนื่อง
J. Doe avatar
at flag
@kodlu ขอบคุณสำหรับคำใบ้ แก้ไขคำผิด (0->1) ความยาวของช่วงเวลาเหล่านั้นไม่จำเป็นต้องคงไว้ (ไม่ควรเช่นกัน) ระหว่างค่าเฉพาะเหล่านั้น คุณเป็นจริงอย่างแน่นอนเกี่ยวกับการทำนายจำนวนก้าวข้างหน้า แต่ฉันไม่ค่อยแน่ใจว่าเป็นกรณีนี้สำหรับตัวอย่างถัดไป/ก่อนหน้าด้วยหรือไม่ เช่น. จากตัวอย่างด้านบน $g^k \equiv 0 \mod 10000$ และ $g^k$ และ $g
J. Doe avatar
at flag
อีกตัวอย่างง่ายๆ ในเครื่องคือถ้าเรากำหนด 'ค่าเฉพาะ' เหล่านั้นเป็นค่าทุกค่าที่ต้องใช้ตัวดำเนินการ mod (ในทิศทางไปข้างหน้า) เช่น สำหรับ $P=11, g=2$ รายชื่อสมาชิกจะเป็น $[1,2,4,8,5,10,9,7,3,6]$ รายการ 'ค่าเฉพาะ' จะเป็น $[5 ,9,7,3]$. สิ่งนี้จะคำนวณได้ง่ายในพื้นที่ แต่ขนาดสมาชิกของ 'รายการเฉพาะ' เหล่านั้นจะไม่เล็กกว่ารายการทั้งหมด จำเป็นต้องมี $g \lll P$ เพื่อให้ทำงานได้ดี ซึ่งแทบจะเป็นไปไม่ได้เลยที่จะหาได้สำหรับ $P$ ขนาดใหญ่

โพสต์คำตอบ

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