Algorithm 2.1. This algorithm takes

Algorithm 2.1. This algorithm takes as input a smoothness bound B, a search bound T ,
an odd prime power divisor qe of p − 1, two number rings O1 and O2 which contain no
primitive qth roots of unity and for which there are maps φ1 and φ2 as described above,
a B-smooth element τ in O1 whose image t ∈ Fp is primitive, and a B-smooth element σ
in O1 or O2 whose image σ ∈ Fp is non-zero. The purpose of the algorithm is to compute
the residue of logt σ modulo qe, where σ as before denotes the image of σ in Fp. We note
that it is not difficult to determine the roots of unity in a number field (see [4]). Of course,
primitive qth roots of unity can easily be avoided by choosing fields whose discriminants
are prime to q.
Step 1. For i = 1, 2, let Si be the set of prime ideals q ⊂ Oi for which q ∩ Z is generated
by a rational prime
B. Search for elements δ = (δ1, δ2) ∈ O1 ×O2 which are B-smooth
and which satisfy
φ1(δ1) = φ2(δ2).

ผลลัพธ์ (ไทย) 1:

อัลกอริทึม 2.1 อัลกอริทึมนี้ใช้ป้อนข้อมูลราบรื่นการผูก B, T ผูกค้นหามี qe หารพลังงานหลักคี่ของ p − 1, 2 เลขแหวน O1 และ O2 ซึ่งไม่ประกอบด้วยqth ดั้งเดิมรากของความสามัคคี และซึ่งมีแผนที่ φ1 และ φ2 ตามที่อธิบายไว้ข้างต้นτเป็นองค์ประกอบ B เรียบใน O1 รูป t ∈ Fp มากับขึ้น σเป็นองค์ประกอบ B เรียบใน O2 หรือ O1 รูปσ∈ Fp ไม่ใช่ศูนย์ วัตถุประสงค์ของขั้นตอนวิธีจะคำนวณสารตกค้างของσ logt modulo qe ที่σเป็นก่อนแสดงภาพของσใน Fp เราทราบว่า มันไม่ยากที่จะกำหนดรากฐานของความสามัคคีในเขต (ดู [4]) แน่นอนรากดั้งเดิม qth ของสามัคคีสามารถสามารถหลีก โดยเลือกเขตข้อมูล discriminantsนายกจะ q ได้ขั้นตอนที่ 1 หา = 1, 2 ให้ซีเป็นอุดมคติสำคัญ q ⊂ Oi q ที่∩ Z มีสร้างชุดโดยนายกเชือดบีหาองค์ประกอบδ = (δ1, δ2) ∈× O1 O2 ซึ่งบีเรียบและการตอบสนองΦ1(Δ1) = Φ2(Δ2)

ผลลัพธ์ (ไทย) 2:

อัลกอริทึม 2.1 ขั้นตอนวิธีการนี้จะใช้เวลาเป็น input เรียบผูกพัน B, T
ค้นหาผูกพันที่หารอำนาจนายกแปลกQE ของพี - 1 สองจำนวนแหวน O1 และ O2
ที่มีไม่มีรากqth ดั้งเดิมของความสามัคคีและการที่มีแผนที่มีφ1และφ2เป็น
อธิบายไว้ข้างต้นเป็นองค์ประกอบB-เรียบτใน O1 ที่มีภาพที∈ Fp เป็นพื้นฐานและองค์ประกอบ
B-เรียบσในO1 หรือ O2 ที่มีภาพσ∈ Fp เป็นที่ไม่ใช่ศูนย์ วัตถุประสงค์ของขั้นตอนวิธีการคือการคำนวณตกค้างของ logt σโมดูโล QE ที่σเป็นก่อนหมายถึงภาพของσใน Fp
เราทราบว่ามันไม่ยากที่จะกำหนดรากของความสามัคคีในด้านจำนวน (ดู [4])
แน่นอนราก qth ดั้งเดิมของความสามัคคีสามารถจะหลีกเลี่ยงได้โดยการเลือกสาขาที่มี discriminants มีความสำคัญในการคิว. ขั้นตอนที่ 1 สำหรับ i = 1, 2, ศรีให้เป็นชุดของอุดมคติที่สำคัญคิว⊂เฮ้ยที่คิว∩ Z จะถูกสร้างขึ้นโดยมีเหตุผลที่สำคัญ? บีค้นหาองค์ประกอบ = δ (δ1, δ2) ∈ O1 × O2 ซึ่งเป็น B-เรียบและตอบสนองความφ1 (δ1) = φ2 (δ2)

ผลลัพธ์ (ไทย) 3:

ขั้นตอนวิธี 2.1 . ขั้นตอนวิธีนี้จะใช้เวลาเป็น input ค่าผูกพัน B ค้นหาผูกทีแปลกนายกพลังประชาน QE ของ P − 1 , 2 เบอร์ 01 และ O2 ซึ่งไม่มีแหวนรากของความสามัคคีและเล่นดั้งเดิมซึ่งมีφφแผนที่ 1 และ 2 ตามที่อธิบายไว้ข้างต้นเป็นองค์ประกอบใน b-smooth τ 01 ที่มีภาพไม่∈ FP เป็นดั้งเดิม และ b-smooth องค์ประกอบσใน 01 หรือ O2 ซึ่งภาพσ∈ FP เป็นไม่เป็น . วัตถุประสงค์ของวิธีการคำนวณกาก logt σมอดุโล QE ที่σก่อนแสดงภาพσใน FP . เราทราบมันไม่ได้เป็นเรื่องยากที่จะตรวจสอบรากของความสามัคคีในฟิลด์หมายเลข ( ดู [ 4 ] ) แน่นอนดั้งเดิมเล่นรากเหง้าของความสามัคคีได้อย่างง่ายดายสามารถหลีกเลี่ยงได้โดยการเลือกเขตข้อมูลที่มี discriminantsเป็นเฉพาะกับ Qขั้นตอนที่ 1 สำหรับฉัน = 1 , 2 ให้จังหวัดเป็นตั้งอุดมคติของนายก q ⊂นี่ที่ถาม∩ Z ถูกสร้างขึ้นโดยเข้าแง่ นายก . ค้นหาองค์ประกอบδ = ( δ 1 , δ 2 ) ∈ 01 × O2 ซึ่งเป็น b-smoothและที่ตอบสนองφ 1 ( δ 1 ) = φ 2 ( δ 2 )