ตัวสร้างเลขสุ่มเทียมแบบผกผันเชิงคอนกรุเอเลน ต์ (Inversive congruential generators)เป็นประเภทหนึ่งของตัว สร้างเลขสุ่มเทียมเชิงคอนกรุเอเลนต์แบบไม่เชิงเส้น ซึ่งใช้ตัวผกผันการคูณแบบโมดูลัส (ถ้ามี) ในการสร้างเลขถัดไปในลำดับ สูตรมาตรฐานสำหรับตัวสร้างเลขสุ่มเทียมแบบผกผันเชิงคอนกรุเอเลนต์ โมดูลัสจำนวนเฉพาะqคือ:

${\displaystyle x_{0}={\text{seed}},}$

${\displaystyle x_{i+1}={\begin{cases}(ax_{i}^{-1}+c){\bmod {q}}&{\text{ถ้า }}x_{i}\neq 0,\\c&{\text{ถ้า }}x_{i}=0.\end{cases}}}$

ตัวสร้างดังกล่าวจะถูกแสดงด้วยสัญลักษณ์ICG( q , a , c , seed )และเรียกว่าเป็น ICG ที่มีพารามิเตอร์q , a , cและseed seed

ลำดับจะต้องมีจำนวนขั้นตอนที่จำกัด และเนื่องจากองค์ประกอบถัดไปขึ้นอยู่กับองค์ประกอบก่อนหน้าโดยตรงเท่านั้น ดังนั้นจึง เป็นเช่นนั้นต่อไปเรื่อยๆ คาบสูงสุดที่เป็นไปได้สำหรับค่าสัมบูรณ์qคือqเอง กล่าวคือ ลำดับจะรวมค่าทุกค่าตั้งแต่ 0 ถึงq − 1 ก่อนที่จะวนซ้ำ ${\displaystyle (x_{n})_{n\geq 0}}$${\displaystyle x_{i}=x_{j}}$${\displaystyle x_{i+1}=x_{j+1}}$

เงื่อนไขที่เพียงพอสำหรับลำดับที่จะมีคาบสูงสุดที่เป็นไปได้คือการเลือกaและcที่ทำให้พหุนาม ( วงแหวนพหุนามเหนือ) เป็นพหุนามดั้งเดิมนี่ไม่ใช่เงื่อนไขที่จำเป็น มีการเลือกq , aและcที่ทำให้ไม่ใช่พหุนามดั้งเดิม แต่ลำดับก็ยังมีคาบเท่ากับqพหุนามใดๆ ไม่ว่าจะเป็นพหุนามดั้งเดิมหรือไม่ก็ตาม ที่นำไปสู่ลำดับที่มีคาบสูงสุดเรียกว่าพหุนามผกผันที่มีคาบสูงสุด (IMP) Chou อธิบายอัลกอริทึมสำหรับการเลือกพารามิเตอร์aและcเพื่อให้ได้พหุนามดังกล่าว^{[ 1 ]}${\displaystyle f(x)=x^{2}-cx-a\in \mathbb {F} _{q}[x]}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle f(x)}$

Eichenauer-Herrmann, Lehn, Grothe และNiederreiterได้แสดงให้เห็นว่าเครื่องกำเนิดความสอดคล้องแบบผกผันมีคุณสมบัติความสม่ำเสมอที่ดี โดยเฉพาะอย่างยิ่งในส่วนที่เกี่ยวกับโครงสร้างแลตติสและความสัมพันธ์แบบอนุกรม

ICG(5, 2, 3, 1) ให้ลำดับ 1, 0, 3, 2, 4, 1, 0, 3, 2, 4, 1, 0, ...

ในตัวอย่างนี้ไม่สามารถแยกตัวประกอบได้ในเนื่องจากไม่มี 0, 1, 2, 3 หรือ 4 เป็นราก นอกจากนี้ยังสามารถตรวจสอบได้ว่าxเป็นองค์ประกอบดั้งเดิมของและดังนั้นf ก็ เป็นองค์ประกอบดั้งเดิมเช่น กัน${\displaystyle f(x)=x^{2}-3x-2}$${\displaystyle \mathbb {F} _{5}[x]}$${\displaystyle \mathbb {F} _{5}[x]/(f)}$

การสร้างเครื่องกำเนิดผกผันแบบผสม (CIG) อาศัยการรวมเครื่องกำเนิดผกผันแบบสอดคล้องกันสองเครื่องขึ้นไปตามวิธีการที่อธิบายไว้ด้านล่าง

ให้ n และ r เป็นจำนวนเฉพาะที่แตกต่างกัน โดยแต่ละ n ≤ r สำหรับแต่ละดัชนีjโดยที่ 1 ≤ j ≤ rให้ r เป็นลำดับขององค์ประกอบที่มีคาบความยาวเท่ากับ r กล่าวอีกนัยหนึ่งคือ r = r ${\displaystyle p_{1},\dots ,p_{r}}$${\displaystyle p_{j}\geq 5}$${\displaystyle (x_{n})_{n\geq 0}}$${\displaystyle \mathbb {F} _{p_{j}}}$${\displaystyle p_{j}}$${\displaystyle \{x_{n}^{(j)}\mid 0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}}$

สำหรับแต่ละดัชนีjโดยที่ 1 ≤ j ≤ r เราจะพิจารณาโดยที่คือความยาวคาบของลำดับต่อไปนี้ ${\displaystyle T_{j}=T/p_{j}}$${\displaystyle T=p_{1}\cdots p_{r}}$${\displaystyle (x_{n})_{n\geq 0}}$

ลำดับของตัวเลขสุ่มเทียมแบบผสมถูกกำหนดให้เป็นผลรวม ${\displaystyle (x_{n})_{n\geq 0}}$

${\displaystyle x_{n}=\left(T_{1}x_{n}^{(1)}+T_{2}x_{n}^{(2)}+\dots +T_{r}x_{n}^{(r)}\right){\bmod {T}}}$.

วิธีการแบบผสมผสานนี้ช่วยให้สามารถรวมเครื่องกำเนิดไฟฟ้าแบบผกผันที่สอดคล้องกันได้ โดยมีเงื่อนไขว่าเครื่องกำเนิดไฟฟ้าเหล่านั้นต้องมีคาบเวลาครบถ้วน ในระบบการผลิตแบบขนาน

CIG ได้รับการยอมรับเพื่อนำไปใช้ในทางปฏิบัติด้วยเหตุผลหลายประการ

ประการแรก ลำดับไบนารีที่สร้างขึ้นด้วยวิธีนี้จะปราศจากความเบี่ยงเบนทางสถิติที่ไม่พึงประสงค์ ลำดับผกผันที่ผ่านการทดสอบอย่างกว้างขวางด้วยการทดสอบทางสถิติที่หลากหลายจะยังคงมีเสถียรภาพภายใต้การเปลี่ยนแปลงของพารามิเตอร์^{[ 2 ] [ 3 ] [ 4 ]}

ประการที่สอง มีวิธีการเลือกพารามิเตอร์ที่มั่นคงและเรียบง่าย โดยอิงตามอัลกอริทึม Chou ^{[ 1 ]}ซึ่งรับประกันความยาวคาบสูงสุด

ประการที่สาม วิธีการแบบผสมมีคุณสมบัติเหมือนกับตัวสร้างผกผันเดี่ยว^{[ 5 ] [ 6 ]}แต่ยังให้ความยาวคาบที่มากกว่าที่ได้จากตัวสร้างผกผันแบบสอดคล้องเดี่ยวอย่างมีนัยสำคัญ ดูเหมือนว่าจะได้รับการออกแบบมาเพื่อใช้งานกับแพลตฟอร์มฮาร์ดแวร์แบบขนานมัลติโปรเซสเซอร์

มีอัลกอริทึม^{[ 7 ]}ที่ช่วยให้สามารถออกแบบตัวสร้างสารประกอบที่มีความยาวคาบที่คาดการณ์ได้ ระดับความซับซ้อนเชิงเส้นที่คาดการณ์ได้ พร้อมคุณสมบัติทางสถิติที่ยอดเยี่ยมของสตรีมบิตที่ผลิตได้

ขั้นตอนการออกแบบโครงสร้างที่ซับซ้อนนี้เริ่มต้นด้วยการกำหนดฟิลด์จำกัดของ องค์ประกอบ pและสิ้นสุดด้วยการเลือกพารามิเตอร์aและcสำหรับตัวสร้างคอนกรุเอทีฟผกผันแต่ละตัวซึ่งเป็นส่วนประกอบของตัวสร้างแบบผสม นั่นหมายความว่าตัวสร้างแต่ละตัวจะเชื่อมโยงกับพหุนาม IMP ที่กำหนดไว้ เงื่อนไขดังกล่าวเพียงพอสำหรับคาบสูงสุดของตัวสร้างคอนกรุเอทีฟผกผันแต่ละตัว^{[ 8 ]}และสุดท้ายสำหรับคาบสูงสุดของตัวสร้างแบบผสม การสร้างพหุนาม IMP เป็นแนวทางที่มีประสิทธิภาพที่สุดในการค้นหาพารามิเตอร์สำหรับตัวสร้างคอนกรุเอทีฟผกผันที่มีความยาวคาบสูงสุด

คุณสมบัติการกระจายตัวอย่างสม่ำเสมอและความเป็นอิสระทางสถิติของลำดับที่สร้างขึ้น ซึ่งมีความสำคัญอย่างยิ่งต่อการนำไปใช้ในการจำลองแบบสุ่มสามารถวิเคราะห์ได้โดยพิจารณาจากความคลาดเคลื่อนของs -tuple ของตัวเลขสุ่มเทียมที่ต่อเนื่องกัน โดยมีค่าและตามลำดับ ${\displaystyle s=1}$${\displaystyle s=2}$

ค่าความคลาดเคลื่อนจะคำนวณระยะห่างของตัวสร้างเลขสุ่มจากตัวสร้างเลขสุ่มแบบสม่ำเสมอ ค่าความคลาดเคลื่อนต่ำหมายความว่าลำดับเลขสุ่มที่สร้างขึ้นสามารถนำไปใช้เพื่อ วัตถุประสงค์ ทางด้านการเข้ารหัสได้และเป้าหมายแรกของตัวสร้างเลขสุ่มแบบผกผันก็คือการสร้างเลขสุ่มเทียม

สำหรับจุดN ใดๆ ความคลาดเคลื่อนจะถูกกำหนดโดย โดย ที่ ค่าสูงสุดจะขยายไปทั่วช่วงย่อยJ ทั้งหมด ของมี ค่า เท่ากับจำนวนจุดใน ที่ตกอยู่ในJและแทนปริมาตรs มิติของJ${\displaystyle {\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}\in [0,1)}$${\displaystyle D_{N}({\mathbf {t} __{1},\dots ,{\mathbf {t} __{N-1})={\rm {sup}__{J}|F_{N}(J)-V(J)|}$${\displaystyle [0,1)^{s}}$${\displaystyle F_{N}(J)}$${\displaystyle N^{-1}}$${\displaystyle {\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}}$${\displaystyle V(J)}$

จนถึงตอนนี้ เรามีลำดับของจำนวนเต็มตั้งแต่ 0 ถึง⁠ ⁠${\displaystyle T-1}$เพื่อให้ได้ลำดับของเราสามารถหารลำดับของจำนวนเต็มด้วยคาบT ของมัน ได้ ${\displaystyle [0,1)^{s}}$

จากนิยามนี้ เราสามารถกล่าวได้ว่า หากลำดับนั้นเป็นแบบสุ่มโดยสมบูรณ์ ลำดับนั้นจะกระจายตัวอย่างดีในช่วงและจุดทั้งหมดจะอยู่ในJดังนั้นแต่ ถ้าหากลำดับนั้นกระจุกตัวอยู่ใกล้จุดใดจุดหนึ่ง ช่วงย่อยJ ก็ จะเล็กมากดังนั้น จากนั้นเราจะได้จากกรณีที่ดีที่สุดและแย่ที่สุด: ${\displaystyle {\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}}$${\displaystyle J=[0,1)^{s}}$${\displaystyle V(J)=1}$${\displaystyle F_{N}(J)=N/N=1}$${\displaystyle D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=0}$${\displaystyle V(j)\approx 0}$${\displaystyle F_{N}(j)\approx N/N\approx 1}$${\displaystyle D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=1}$

${\displaystyle 0\leq D_{N}({\mathbf {t} __{1},\dots ,{\mathbf {t} __{N-1})\leq 1}$.

จำเป็นต้องมีสัญลักษณ์เพิ่มเติมอีกเล็กน้อย สำหรับจำนวนเต็มและให้เป็นเซตของจุดบนโครงตาข่ายที่ไม่เป็นศูนย์โดยที่ สำหรับ${\displaystyle k\geq 1}$${\displaystyle q\geq 2}$${\displaystyle C_{k}(q)}$${\displaystyle (h_{1},\dots ,h_{k})\in Z^{k}}$${\displaystyle -q/2<h_{j}<q/2}$${\displaystyle 1\leq j\leq k}$

กำหนด

${\displaystyle r(h,q)={\begin{cases}q\sin(\pi |h|/q)&{\text{สำหรับ }}h\in C_{1}(q)\\1&{\text{สำหรับ }}h=0\end{cases}}}$

และ

${\displaystyle r(\mathbf {h} ,q)=\prod _{j=1}^{k}r(h_{j},q)}$

สำหรับ. จริงๆ แล้ว มีการใช้ ตัวย่อและหมายถึงผลคูณภายในมาตรฐานของใน. ${\displaystyle {\mathbf {h} }=(h_{1},\dots ,h_{k})\in C_{k}(q)}$${\displaystyle t}$${\displaystyle e(t)={\rm {exp}}(2\pi \cdot it)}$${\displaystyle u\cdot v}$${\displaystyle u,v}$${\displaystyle R^{k}}$

ให้และเป็นจำนวนเต็ม ให้โดยที่ สำหรับ${\displaystyle N\geq 1}$${\displaystyle q\geq 2}$${\displaystyle {\mathbf {t} }_{n}=y_{n}/q\in [0,1)^{k}}$${\displaystyle y_{n}\in \{0,1,\dots ,q-1\}^{k}}$${\displaystyle 0\leq n<N}$

ดังนั้น ความคลาดเคลื่อนของคะแนน จึงเป็นไปตามที่ยอมรับได้ ${\displaystyle {\mathbf {t} }_{0},\dots ,{\mathbf {t} }_{N-1}}$

${\displaystyle D_{N}(\mathbf {t} _{0},\mathbf {t} _{1},\dots ,\mathbf {t} _{N-1})}$≤ +${\displaystyle {\frac {k}{q}}}$${\displaystyle {\frac {1}{N}}}$${\displaystyle \sum _{h\in \mathbb {C} _{k}(q)}}$${\displaystyle {\frac {1}{r(\mathbf {h} ,q)}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}}$

ความคลาดเคลื่อนของจุดที่กำหนดขึ้นเองนั้นเป็นไปตามเงื่อนไข ${\displaystyle N}$${\displaystyle \mathbf {t} _{1},\dots ,\mathbf {t} _{N-1}\in [0,1)^{k}}$

${\displaystyle D_{N}(\mathbf {t} _{0},\mathbf {t} _{1},\dots ,\mathbf {t} _{N-1})\geq {\frac {\pi }{2N((\pi +1)^{l}-1)\prod _{j=1}^{k}{\rm {max}}(1,h_{j})}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}}$

สำหรับจุดแลตติสที่ไม่เป็นศูนย์ใดๆโดยที่แทนจำนวนพิกัดที่ไม่เป็นศูนย์ของจุดนั้น ${\displaystyle {\mathbf {h} }=(h_{1},\dots ,h_{k})\in Z^{k}}$${\displaystyle l}$${\displaystyle {\mathbf {h} }}$

ทฤษฎีบททั้งสองนี้แสดงให้เห็นว่า CIG ไม่ใช่เครื่องกำเนิดไฟฟ้าที่สมบูรณ์แบบ เนื่องจากค่าความคลาดเคลื่อนมีค่ามากกว่าค่าบวก แต่ในขณะเดียวกัน CIG ก็ไม่ใช่เครื่องกำเนิดไฟฟ้าที่แย่ที่สุด เนื่องจากค่าความคลาดเคลื่อนมีค่าน้อยกว่า 1

นอกจากนี้ยังมีทฤษฎีบทที่จำกัดค่าเฉลี่ยของความคลาดเคลื่อนสำหรับเครื่องกำเนิดผกผันแบบผสม และทฤษฎีบทที่รับค่าที่ทำให้ความคลาดเคลื่อนถูกจำกัดด้วยค่าบางค่าขึ้นอยู่กับพารามิเตอร์ สำหรับรายละเอียดเพิ่มเติม โปรดดูเอกสารต้นฉบับ^{[ 9 ]}

• เครื่องกำเนิดเลขสุ่มเทียม
• รายชื่อเครื่องกำเนิดเลขสุ่ม
• เครื่องกำเนิดเชิงเส้นแบบสอดคล้อง
• เลขสุ่มเทียมแบบผกผันทั่วไปที่สอดคล้องกัน
• ฟังก์ชันสุ่มเทียมของ Naor-Reingold

• เครื่องกำเนิดแบบผกผัน (Inversive Generators) ถูกเก็บถาวรเมื่อวันที่ 24 กันยายน 2008 ที่Wayback Machineของมหาวิทยาลัยซาลซ์บูร์ก