ในทฤษฎีจำนวนเชิงคำนวณและพีชคณิตเชิงคำนวณ อัลกอริทึมจิงโจ้ของพอลลาร์ด (หรืออัลกอริทึมแลมบ์ดาของพอลลาร์ดดูการตั้งชื่อด้านล่าง) เป็นอัลกอริทึมสำหรับแก้ ปัญหา ลอการิทึมแบบไม่ต่อเนื่องอัลกอริทึมนี้ได้รับการแนะนำในปี 1978 โดยนักทฤษฎีจำนวนจอห์น เอ็ม. พอลลาร์ด ในบทความเดียวกันกับ อัลกอริทึมโรของพอลลาร์ดที่รู้จักกันดีกว่าสำหรับการแก้ปัญหาเดียวกัน^{[ 1 ] [ 2 ]}แม้ว่าพอลลาร์ดจะอธิบายการประยุกต์ใช้อัลกอริทึมของเขากับปัญหาลอการิทึมแบบไม่ต่อเนื่องในกลุ่มการคูณของหน่วยโมดูลัสจำนวนเฉพาะp แต่ในความเป็นจริงแล้วมันเป็นอัลกอริทึมลอการิทึมแบบไม่ต่อเนื่องทั่วไป—มันจะทำงานได้ใน กลุ่มวัฏจักรจำกัดใดๆ

สมมติว่าเป็นกลุ่มวัฏจักรจำกัดที่มีอันดับซึ่งสร้างขึ้นโดยสมาชิกและเราต้องการหาลอการิทึมแบบไม่ต่อเนื่องของสมาชิกบนฐานกล่าวอีกนัยหนึ่งคือ เราต้องการหาที่ทำให้อัลกอริทึมแลมบ์ดาช่วยให้เราค้นหาในช่วงใดช่วงหนึ่งได้ เราอาจค้นหาลอการิทึมที่เป็นไปได้ทั้งหมดโดยการตั้งค่า และ${\displaystyle G}$${\displaystyle n}$${\displaystyle \alpha }$${\displaystyle x}$${\displaystyle \beta }$${\displaystyle \alpha }$${\displaystyle x\in Z_{n}}$${\displaystyle \alpha ^{x}=\beta }$${\displaystyle x}$${\displaystyle [a,\ldots ,b]\subset Z_{n}}$${\displaystyle a=0}$${\displaystyle b=n-1}$

1. เลือกเซตของจำนวนเต็มบวกที่มีค่าเฉลี่ยโดยประมาณและกำหนดแผนที่สุ่มเทียม ${\displaystyle S}$${\displaystyle {\sqrt {ba}}}$${\displaystyle f:G\rightarrow S}$

2. เลือกจำนวนเต็มหนึ่งจำนวนแล้วคำนวณลำดับของสมาชิกในกลุ่มตาม: ${\displaystyle N}$${\displaystyle \{x_{0},x_{1},\ldots ,x_{N}\}}$

• ${\displaystyle x_{0}=\alpha ^{b}\,}$
• ${\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i})}{\text{ สำหรับ }}i=0,1,\ldots ,N-1}$

3. คำนวณ

${\displaystyle d=\sum _{i=0}^{N-1}f(x_{i}).}$

โปรดสังเกตว่า:

${\displaystyle x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.}$

4. เริ่มคำนวณลำดับที่สองขององค์ประกอบกลุ่มตาม: ${\displaystyle \{y_{0},y_{1},\ldots \}}$

• ${\displaystyle y_{0}=\เบต้า \,}$
• ${\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i})}{\text{ for }}i=0,1,\ldots ,N-1}$

และลำดับจำนวนเต็มที่สอดคล้องกันดังนี้: ${\displaystyle \{d_{0},d_{1},\ldots \}}$

${\displaystyle d_{n}=\sum _{i=0}^{n-1}f(y_{i})}$.

โปรดสังเกตว่า:

${\displaystyle y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}{\mbox{ for }}i=0,1,\ldots ,N-1}$

5. หยุดการคำนวณเทอมของและเมื่อเงื่อนไขใดเงื่อนไขหนึ่งต่อไปนี้เป็นจริง: ${\displaystyle \{y_{i}\}}$${\displaystyle \{d_{i}\}}$

ก) สำหรับบางค่าถ้าลำดับและ"ชนกัน" ในลักษณะนี้ เราจะได้ว่า: ${\displaystyle y_{j}=x_{N}}$${\displaystyle j}$${\displaystyle \{x_{i}\}}$${\displaystyle \{y_{j}\}}$

${\displaystyle x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j}}\Rightarrow \beta =\alpha ^{b+d-d_{j}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}}$

และแล้วเราก็เสร็จสิ้นภารกิจแล้ว

ข) หากเกิดกรณีนี้ แสดงว่าอัลกอริทึมไม่สามารถค้นหาได้สามารถลองใหม่ในครั้งต่อไปได้โดยการเปลี่ยนตัวเลือกของและ/ หรือ${\displaystyle d_{i}>b-a+d}$${\displaystyle x}$${\displaystyle S}$${\displaystyle f}$

พอลลาร์ดให้ความซับซ้อนเชิงเวลาของอัลกอริทึมเป็น โดยใช้การอ้างอิงเชิงความน่าจะเป็นบนพื้นฐานของสมมติฐานที่ว่าทำงานแบบสุ่มเทียม เนื่องจากสามารถแทนด้วยบิตได้ ความซับซ้อนนี้จึงเป็นแบบเลขชี้กำลังตามขนาดของปัญหา (ถึงกระนั้นก็ยังเป็นการปรับปรุงที่สำคัญกว่าอัลกอริทึมแบบใช้กำลังทั้งหมดแบบง่ายๆ ที่ใช้เวลา) สำหรับตัวอย่างของ อัลกอริทึมลอการิทึมแบบ ไม่ต่อเนื่องที่มีเวลาต่ำกว่าเลขชี้กำลังโปรด ดูอัลกอริทึมแคลคูลัสของดัชนี${\displaystyle O({\sqrt {b-a}})}$${\displaystyle f}$${\displaystyle a,b}$${\displaystyle O(\log b)}$${\displaystyle O(b-a)}$

อัลกอริทึมนี้เป็นที่รู้จักกันดีในสองชื่อ

อย่างแรกคือ "อัลกอริทึมจิงโจ้ของพอลลาร์ด" ชื่อนี้อ้างอิงถึงการเปรียบเทียบที่ใช้ในบทความที่นำเสนออัลกอริทึม โดยอธิบายอัลกอริทึมในแง่ของการใช้จิงโจ้ที่เชื่อง เพื่อดักจับจิงโจ้ป่า พอลลาร์ดได้อธิบาย ^{[ 3 ]}ว่าการเปรียบเทียบนี้ได้รับแรงบันดาลใจจากบทความที่ "น่าสนใจ" ซึ่งตีพิมพ์ในScientific American ฉบับเดียวกัน ซึ่งเป็นการอธิบายระบบการเข้ารหัสคีย์สาธารณะRSAบทความ^{[ 4 ]}อธิบายถึงการทดลองที่ "ต้นทุนพลังงานในการเคลื่อนที่ของจิงโจ้ ซึ่งวัดในแง่ของการบริโภคออกซิเจนที่ความเร็วต่างๆ ถูกกำหนดโดยการวางจิงโจ้บนลู่วิ่ง "

อย่างที่สองคือ "อัลกอริทึมแลมบ์ดาของพอลลาร์ด" คล้ายกับชื่อของอัลกอริทึมลอการิทึมแบบไม่ต่อเนื่องอีกตัวหนึ่งของพอลลาร์ด คือ อัลกอริทึมโรของ พอลลาร์ ด ชื่อนี้หมายถึงความคล้ายคลึงกันระหว่างการแสดงภาพของอัลกอริทึมกับอักษรกรีกแลมบ์ดา ( ) เส้นขีดที่สั้นกว่าของอักษรแลมบ์ดาตรงกับลำดับเนื่องจากเริ่มต้นจากตำแหน่ง b ทางด้านขวาของ x ในทำนองเดียวกัน เส้นขีดที่ยาวกว่าตรงกับลำดับซึ่ง "ชนกับ" ลำดับแรก (เช่นเดียวกับเส้นขีดของแลมบ์ดาที่ตัดกัน) แล้วจึงตามมาในภายหลัง ${\displaystyle \lambda }$${\displaystyle \{x_{i}\}}$${\displaystyle \{y_{i}\}}$

พอลลาร์ดแสดงความชอบชื่อ "อัลกอริทึมจิงโจ้" ^{[ 5 ]}เนื่องจากวิธีนี้ช่วยหลีกเลี่ยงความสับสนกับอัลกอริทึมโรบางเวอร์ชันคู่ขนานของเขา ซึ่งเรียกอีกอย่างว่า "อัลกอริทึมแลมบ์ดา"

• มายากลไพ่ของไดน์กิน
• จำนวน Kruskal ^{[ 6 ]}
• โต๊ะสีรุ้ง

• Montenegro, Ravi [ที่ Wikidata] ; Tetali, Prasad V. (2010-11-07) [2009-05-31]. ใช้เวลานานแค่ไหนในการจับจิงโจ้ป่า? (PDF) . รายงานการประชุมวิชาการประจำปีครั้งที่ 41 ของ ACM ว่าด้วยทฤษฎีการคำนวณ (STOC 2009). หน้า  553–560 . arXiv : 0812.0789 . doi : 10.1145/1536414.1536490 . S2CID  12797847 . เก็บถาวร(PDF)จากต้นฉบับเมื่อ 2023-08-20 . เรียกดูเมื่อ2023-08-20 .