รายละเอียดของขั้นตอนวิธี ของ แมร์แซนทวิสเตอร์

ขั้นตอนวิธีแมร์แซน ทวิสเตอร์นั้นคือวิธีชิฟท์รีจิสเตอร์ป้อนกลับแบบทั่วไป (Generalised feedback shift register) ซึ่งผ่านการดัดแปลง (twisted GFSR หรือ TGFSR) ของรูปแบบปกติตรรกยะ (rational normal form) (TGFSR(R)) ที่มีสถานะการสะท้อนและลดลงของบิต (state bit reflection and tempering) ซึ่งมีลักษณะพิเศษดังต่อไปนี้

  • w: ขนาดของเวิร์ด (จำนวนบิต)
  • n: ดีกรีของการปรากฏซ้ำ (degree of recurrence)
  • m: คำกลาง หรือตัวเลขของลำดับแบบขนาน (middle word, or the number of parallel sequences) , 1 ≤ m ≤ n
  • r: จุดแยกคำหรือจำนวนบิตในบิตมาสก์ระดับต่ำกว่า (separation point of one word, or the number of bits of the lower bitmask) , 0 ≤ r ≤ w - 1
  • a: สัมประสิทธิ์ของรูปแบบปกติตรรกยะ (rational normal form) จากเมตริกซ์ที่ดัดแปลง (twist matrix)
  • b, c: TGFSR(R) บิตมาสก์ที่ลดลง (tempering bitmasks)
  • s, t: TGFSR(R) บิตชิฟท์ที่ลดลง (tempering bit shifts)
  • u, l: บิตชิฟท์ที่ลดลงเพิ่มเติมของแมร์แซน ทวิสเตอร์ (additional Mersenne Twister tempering bit shifts)

ด้วยข้อจำกัดที่ว่า 2nw-r -1 เป็นจำนวนเฉพาะแมร์แซน (Mersenne prime) จะช่วยทำให้การทดสอบพื้นฐาน (primitivity test) และการทดสอบการกระจาย k (k-distribution test) ซึ่งจำเป็นในการค้นหาพารามิเตอร์ (parameter search) นั้นง่ายขึ้น

สำหรับ word x ที่มีขนาด w บิตสามารถนำมาเขียนเป็นความสัมพันธ์เวียนเกิดได้ดังนี้

โดย | คือ bitwise or และ คือ bitwise exclusive or (XOR) xu, xl เป็น x ที่มีบิตมาสก์ระดับสูงกว่าและต่ำกว่าตามลำดับ การแปลงแบบดัดแปลง (twist transformation) A นั้นถูกนิยามโดยรูปแบบปกติตรรกยะ (rational normal form)

โดย In-1 คือเมทริกซ์เอกลักษณ์มีมิติ (n - 1)*(n - 1) (มีความแตกต่างกับการคูณเมทริกซ์แบบปกติคือใช้การดำเนินการ XOR แบบ bitwise แทนการบวก) รูปแบบปกติตรรกยะ (rational normal form) มีประโยชน์ตรงที่สามารถแสดงได้ในรูปแบบดังต่อไปนี้

โดยในการที่จะหาขีดจำกัดบนทางทฤษฎี 2nw-r-1 ใน TGFSR ได้นั้น φB(t) ต้องเป็นพหุนามแบบพื้นฐาน (Primitive polynomial) และ φB(t) เป็นพหุนามลักษณะเฉพาะ (Characteristic polynomial) ของ

การแปลงแบบดัดแปลง (twist transformation) ช่วยทำให้ GFSR ดีขึ้นได้โดยคุณสมบัติที่สำคัญดังต่อไปนี้

  • ช่วงของเลขที่จะสุ่มกว้างถึงขีดจำกัดบนทางทฤษฎี 2nw-r-1 (ยกเว้นกรณีที่เริ่มต้นด้วย 0)
  • การกระจายที่มีความถี่ในการเกิดเท่ากัน(Equidistribution) ใน n มิติ (เช่น ขั้นตอนวิธีการสร้างความสอดคล้องกันแบบเชิงเส้น (Linear congruential generator) สามารถจัดการได้ถึงแค่การกระจายใน 5 มิติเท่านั้น)

เฉกเช่น TGFSR(R) แมร์แซน ทวิสเตอร์ ถูกลดหลั่นด้วยการแปลงที่ลดลง (tempering transform) เพื่อชดเชยการลดมิติของการกระจายที่มีความถี่ในการเกิดเท่ากัน(Equidistribution) (เพราะว่า A อยู่ในรูปแบบปกติตรรกยะ(rational normal form)) ซึ่งจะสมมูลกับการแปลง A = R → A = T-1RT โดยสามารถหาตัวผกผันของ T (T-1) ได้ การแปลงที่ลดลงนั้นถูกกำหนดไว้ในกรณีของแมร์แซน ทวิสเตอร์ ดังนี้

y := x ⊕ (x >> u)

y := :y ⊕ ((y << s) & b)

y := :y ⊕ ((y << t) & c)

z := y ⊕ (y >> l)

โดย << และ >> เป็นการชิฟท์ซ้ายแบบ bitwise และชิฟท์ขวาแบบ bitwise ตามลำดับ และ & เป็นการดำเนินการ bitwise and การแปลงในบรรทัดแรกและบรรทัดสุดท้ายถูกเพิ่มมาเพื่อเพิ่มประสิทธิภาพของการกระจายที่มีความถี่ในการเกิดเท่ากัน (Equidistribution) ในบิตล่าง ซึ่งเป็นคุณลักษณะของ TGFSR มีความจำเป็นในการที่จะไปให้ถึงขีดจำกัดบนของการกระจายที่มีความถี่ในการเกิดเท่ากัน สำหรับบิตบน

ค่าสัมประสิทธ์สำหรับ MT19937 ได้แก่

  • (w, n, m, r) = (32, 624, 397, 31)
  • a = 9908B0DF16
  • u = 11
  • (s, b) = (7, 9D2C568016)
  • (t, c) = (15, EFC6000016)
  • l = 18

ใกล้เคียง

แมร์แซนทวิสเตอร์ แมร์แยม มีร์ซอฆอนี แมร์แยม อีมอนีเยฮ์ แมร์แนปทาห์ แอร์แคนาดา แมร์ฮัยแรนิค แฌร์แม็ง กาต็องกา แอร์แบร์ที่ 2 เคานต์แห่งแวร์ม็องดัว แฮร์แบร์ท ฟ็อน คารายัน แมรีแห่งโมดีนา

แหล่งที่มา

WikiPedia: แมร์แซนทวิสเตอร์ http://www.tecgraf.puc-rio.br/~lhf/ftp/lua/ http://www.iro.umontreal.ca/~lecuyer/myftp/papers/... http://adrianhoe.com/adrianhoe/projects/adamt19937... http://cybertiggyr.com/gene/jmt/ http://groups.google.com/group/comp.lang.c/browse_... http://groups.google.com/group/sci.crypt/browse_th... http://www.hackinghat.com/index.php/lisp/mersenne-... http://archive.msdn.microsoft.com/MersenneTwister http://www.mitrionics.com/?page=mersenne http://www.ntrand.com/