난수생성자 목록

List of random number generators

무작위 숫자 생성기는 물리, 공학 또는 수학적 컴퓨터 연구(예: 몬테카를로 시뮬레이션), 암호학 및 도박(게임 서버의 경우)을 포함한 많은 종류의 기술 응용 분야에서 중요하다.

이 목록은 품질에 관계없이 많은 일반적인 유형을 포함한다.

유사 번호 생성기(PRNG)

가성수 생성기를 사용할 때마다 존 폰 노이만(John von Neumann)의 받아쓰기를 명심하라. "산술적인 난수 생성 방법을 고려하는 사람은 물론 죄악의 상태에 있다."[1]

다음 알고리즘은 유사수치 생성기다.

제너레이터 날짜 첫 번째 지지자 참조 메모들
중간 제곱법 1946 J. 폰 노이만 [2] 원래 형태로는 질이 나쁘고 역사적으로만 관심이 있다.
레머 발전기 1951 D. H. 레머 [3] 가장 초창기적이고 가장 영향력 있는 디자인 중 하나이다.
선형 결합 발전기(LCG) 1958 W. E. 톰슨; A.로텐베르크 [4][5] 레머 발전기와 역사적으로 가장 영향력 있고 연구된 발전기의 일반화.
지연 피보나치 발생기(LFG) 1958 G. J. 미첼과 D. P. 무어 [6]
선형 피드백 시프트 레지스터(LFSR) 1965 R. C. 타우스워테 [7] 매우 영향력 있는 디자인.Tausworthe 발전기라고도 한다.
위크만힐 발전기 1982 B. A. 비히만과 D.아이. 힐 [8] 16비트 CPU에 적합한 세 개의 작은 LCG 조합.Excel 함수 LAND에서[9] Excel 2003 이상 버전에서 사용되며 버전 2.2까지의 Python 언어에서 기본 생성기였습니다.[10]
규칙 30 1983 S. 울프람 [11] 셀룰러 오토마타 기준.
역방향 동반 발전기(ICG) 1986 J. 아이케나워와 J. 렌 [12]
파크 밀러 발전기 1988 S. K. Park와 K. W. Miller [13] Lehmer 발전기의 구체적인 구현, C++에 함수로 포함되기 때문에 널리 사용된다.minstd_rand0C++11 이후부터.[14]
도토리 생성기 (1984년) 1989년 R. S. 위키라마라트나 [15] [16] 가법적합성 난수 생성기.

구현이 간편하고, 빠르며, 널리 알려지지 않음.적절한 초기화를 통해 현재의 모든 경험적 시험 세트를 통과하고, 공식적으로 수렴이 입증된다.임의 기간 길이에 대해 쉽게 연장할 수 있으며, 더 높은 치수와 더 높은 정밀도로 통계 성능 개선.

MEXMAX 발전기 1991 G. K. Savvidy와 N. G. Ter-Arutyunyan-Savvidy. [17] 그것은 LCG의 일반화인 매트릭스 선형 응집 발전기 클래스의 일원이다.MIXMAX 발전기군에 대한 이론적 근거는 에르고딕 이론과 고전 역학의 결과에 의존한다.
추가 운송(AWC) 1991 G. 마르사글리아와 A. 자만 [18] Lagged-Fibonacci 생성기의 수정.
차감(SWB) 1991 G. 마르사글리아와 A. 자만 [18] Lagged-Fibonacci 생성기의 수정.SWB 발전기는 입자 물리학 시뮬레이션 등에 널리 사용되는 RANLUX 발전기의 기초가 된다.[19]
최대 주기적 왕복선 1992 R. A. J. 매튜스 [20] 숫자 이론에 뿌리를 두고 있는 방법, 비록 실용적인 응용에서는 사용되지 않았다.
키스 1993 G. 마르사글리아 [21] 조합 생성기의 프로토타입 예제.
MWC(Multiple-with-carry) 1994 G. Marsaglia; C.콕스 [22][23]
CMWC(Multiplemental-multiple-with-carry) 1997 R. 쿠튀르와 P. L'Ecuyer [24]
메르센 트위스터(MT) 1998 M. 마츠모토와 T.니시무라 [25] LFSR과 밀접하게 관련됨.MT19937 구현에서는 아마도 가장 일반적으로 사용되는 현대식 PRNG. 기본 생성기는 R과 버전 2.3부터 시작되는 파이썬 언어일 것이다.
호르시프트 2003 G. 마르사글리아 [26] 그것은 매우 빠른 LFSR 발전기의 하위 유형이다.마르사글리아는 또한 Xorshift 발전기의 출력이 Weyl 시퀀스로 추가되는 xorwow 발전기의 개선으로 제안했다.xorwow 발생기는 그래픽 처리 유닛을 위한 nVidia CUUDA 애플리케이션 프로그래밍 인터페이스의 CURAND 라이브러리에 있는 기본 생성기다.
균등분포 장기 선형(WEL) 2006 F. 파네톤, P. L'Ecuyer, M.마츠모토 [27] LFSR은 메르센 트위스터와 밀접하게 연관되어 있으며, 그것의 단점을 보완하는 것을 목표로 하고 있다.
소형 비결정형 PRNG(JSF) 2007 밥 젠킨스 [28]
ARS(Advanced Randomization System) 2011 J. Salmon, M. Moraes, R. Dror, D.쇼 [29] AES-NI를 지원하는 시스템에서 매우 빠른 성능을 제공하는 AES 블록 암호의 단순화된 버전.
스리프라이 2011 J. Salmon, M. Moraes, R. Dror, D.쇼 [29] GPU 구현에 적합한 3피쉬 블록 암호의 단순화된 버전.
필록스 2011 J. Salmon, M. Moraes, R. Dror, D.쇼 [29] S-box를 추가하여 블록 암호 쓰리피쉬의 단순화 및 수정.
스플릿믹스 2014 G. L. 스틸, D.리아와 C.H. 홍수 [30] DumorHash3의 최종 배합 기능에 기초한다.Java Development Kit 8 이상에 포함됨.
PCG(순열식 동시 발생기) 2014 M. E. 오닐 [31] LCG 수정.
RCB(Random Cycle Bit Generator) 2016 R. 쿡맨 [32] RCB는 메르센 트위스터와 단기간/비트 길이 제한으로 시프트/모듈로 발전기의 일부 단점을 극복하기 위해 만들어진 비트 패턴 발생기로 설명된다.
중간 사각형 웨일 시퀀스 RNG 2017 B. 위딘스키 [33][34] John von Neumann의 원래 중간 제곱법에 대한 변화로, 이 발전기는 모든 통계적 시험을 통과한 가장 빠른 RNG일 수 있다.
소로시로128+ 2018 D. 블랙먼, S. 비그나 [35] 현대적인 64비트 CPU에서 가장 빠른 발전기 중 하나인 Marsaglia의 Xorshift 발전기 수정.관련 발전기로는 xoroshiro128**, xoshiro256+, xoshiro256** 등이 있다.
64비트 MELG(MELG-64) 2018 S. 하라세, T. 기모토 [36] 64비트 F-선형2 발전기를 메르센 전성기와 최대 등분산한다.
정사각형 RNG 2020 B. 위딘스키 [37] 카운터 기반 Middle Square Weyl Sequence RNG 버전. 설계상 Philox와 유사하지만 훨씬 더 빠르다.

암호 알고리즘

암호 알고리즘과 암호 해시는 매우 높은 품질의 유사함수 생성기로 사용될 수 있다.그러나 일반적으로 고속 비결정적 무작위 숫자 생성기보다 상당히 느리다(일반적으로 요인 2-10에 의해).

여기에는 다음이 포함된다.

암호학적으로 안전한 몇 개의 유사성 숫자 생성기는 암호 알고리즘에 의존하지 않고 '진정한' 무작위 스트림에서 산출물을 구별하는 난이도를 계산적으로 어려운 문제와 수학적으로 연결하려고 한다.이러한 접근방식은 이론적으로는 중요하지만 대부분의 적용에서 실용화하기에는 너무 느리다.여기에는 다음이 포함된다.

외부 엔트로피를 사용하는 난수 생성기

이러한 접근법은 의사 난수 생성기(흔히 블록이나 스트림 암호의 형태로)와 무작위의 외부 소스(예: 마우스 이동, 키보드 누름 사이의 지연 등)를 결합한다.

임의 번호 서버

다음 (비배출) 웹사이트 목록은 많은 웹사이트들이 추가적인 무작위화 서비스를 제공하는 진정한 무작위 소스로부터 생성된 무작위 번호를 제공한다고 주장한다.

잘 알려진 PRNG API

참고 항목

참조

  1. ^ Von Neumann, John (1951). "Various techniques used in connection with random digits" (PDF). National Bureau of Standards Applied Mathematics Series. 12: 36–38.
  2. ^ 폰 노이만의 1949년 논문 중 일부는 1951년에야 인쇄되었다.존 폰 노이만(John von Neumann), A.S.의 "임의의 숫자와 관련하여 사용되는 다양한 기술"하우스홀더, G.E. 포사이스, H.H. 게먼드, 에드, 몬테카를로 메서드, 국립표준 응용수학 시리즈, vol. 12 (워싱턴 D.C: 미국 정부 인쇄소, 1951) 페이지 36-38.
  3. ^ Lehmer, Derrick H. (1951). "Mathematical methods in large-scale computing units". Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery: 141–146.
  4. ^ Thomson, W. E. (1958). "A Modified Congruence Method of Generating Pseudo-random Numbers". The Computer Journal. 1 (2): 83. doi:10.1093/comjnl/1.2.83.
  5. ^ Rotenberg, A. (1960). "A New Pseudo-Random Number Generator". Journal of the ACM. 7 (1): 75–77. doi:10.1145/321008.321019.
  6. ^ D. E. Knuth, The Art of Computer Programming, Vol. 2 세미머럴 알고리즘, 3번째 에드, 애디슨 웨슬리 롱먼(1998);페이지 27을 참조하십시오.
  7. ^ Tausworthe, R. C. (1965). "Random Numbers Generated by Linear Recurrence Modulo Two" (PDF). Mathematics of Computation. 19 (90): 201–209. doi:10.1090/S0025-5718-1965-0184406-1.
  8. ^ Wichmann, Brian A.; Hill, David I. (1982). "Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Applied Statistics). 31 (2): 188–190. doi:10.2307/2347988. JSTOR 2347988.
  9. ^ "Microsoft Support - Description of the RAND function in Excel". Apr 17, 2018.
  10. ^ "Documentation » The Python Standard Library » 9. Numeric and Mathematical Modules » 9.6. random — Generate pseudo-random numbers".
  11. ^ Wolfram, S. (1983). "Statistical mechanics of cellular automata". Rev. Mod. Phys. 55 (3): 601–644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
  12. ^ Eichenauer, Jürgen; Lehn, Jürgen (1986). "A nonlinear congruential pseudorandom number generator". Statistische Hefte. 27: 315–326. doi:10.1007/BF02932576.
  13. ^ Park, Stephen K.; Miller, Keith W. (1988). "Random Number Generators: Good Ones Are Hard To Find" (PDF). Communications of the ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042.
  14. ^ "Pseudo-random number generation". cppreference.com. Retrieved 14 November 2021.
  15. ^ Wikramaratna, R. S. (1989). "ACORN — A new method for generating sequences of uniformly distributed Pseudo-random Numbers". Journal of Computational Physics. 83 (1): 16–31. Bibcode:1989JCoPh..83...16W. doi:10.1016/0021-9991(89)90221-0.
  16. ^ Wikramaratna, R.S. 적층 일치 난수 생성기, 연산 및 응용 수학 저널(2009), doi:10.1016/j.cam.2009.10.015
  17. ^ Savvidy, G.K; Ter-Arutyunyan-Savvidy, N.G (1991). "On the Monte Carlo simulation of physical systems". Journal of Computational Physics. 97 (2): 566. Bibcode:1991JCoPh..97..566S. doi:10.1016/0021-9991(91)90015-D.
  18. ^ a b George, Marsaglia; Zaman, Arif (1991). "A new class of random number generators". Annals of Applied Probability. 1 (3): 462–480. doi:10.1214/aoap/1177005878.
  19. ^ Martin, Lüscher (1994). "A portable high-quality random number generator for lattice field theory simulations". Computer Physics Communications. 79 (1): 100–110. arXiv:hep-lat/9309020. Bibcode:1994CoPhC..79..100L. doi:10.1016/0010-4655(94)90232-1.
  20. ^ Matthews, Robert A. J. (1992). "Maximally periodic reciprocals". Bull. Inst. Math. Appl. 28: 147–148.
  21. ^ Marsaglia, George; Zaman, Arif (1993). "The KISS generator". Technical Report, Department of Statistics, Florida State University, Tallahassee, FL, USA.
  22. ^ 2018년 8월 1일자 뉴스그룹 sci.stat.math에 조지 마르사글리아가 'Yet another RNG'라는 제목으로 게재했다.
  23. ^ Koç, Cemal (1995). "Recurring-with-Carry Sequences". Journal of Applied Probability. 32 (4): 966–971. doi:10.2307/3215210. JSTOR 3215210.
  24. ^ Couture, Raymond; L'Ecuyer, Pierre (1997). "Distribution properties of multiply-with-carry random number generators" (PDF). Mathematics of Computation. 66 Number. 218 (218): 591–607. Bibcode:1997MaCom..66..591C. doi:10.1090/S0025-5718-97-00827-2.
  25. ^ Matsumoto, M.; Nishimura, T. (1998). "MersenneTwister: A623-dimensionally Equidistributed Uniform Pseudo-Random Number Generator". ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995.
  26. ^ Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14). doi:10.18637/jss.v008.i14.
  27. ^ Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Pierre (March 2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. CiteSeerX 10.1.1.73.5499. doi:10.1145/1132973.1132974.
  28. ^ Jenkins, Bob (2009). "A small noncryptographic PRNG".
  29. ^ a b c Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Parallel random numbers: as easy as 1, 2, 3". Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16. doi:10.1145/2063384.2063405.
  30. ^ Steele, Guy L. Jr.; Lea, Doug; Flood, Christine H. (2014). "Fast splittable pseudorandom number generators" (PDF). OOPSLA '14 Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications.
  31. ^ O'Neill, Melissa E. (2014). "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation" (PDF). Technical Report.
  32. ^ Cookman, Richard (2016). "random cycle bit generator (rcb_generator)". Technical Report.
  33. ^ Widynski, Bernard (2017). "Middle Square Weyl Sequence RNG". arXiv:1704.00358 [cs.CR].
  34. ^ Kneusel, Ron (2018). Random Numbers and Computers (1 ed.). Springer. pp. 13–14.
  35. ^ Blackman, David; Vigna, Sebastiano (2018). "Scrambled Linear Pseudorandom Generators". arXiv:1805.01407 [cs.DS].
  36. ^ Harase, S.; Kimoto, T. (2018). "Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period". ACM Transactions on Mathematical Software. 44 (3): 30:1–30:11. arXiv:1505.06582. doi:10.1145/3159444.
  37. ^ Widynski, Bernard (2020). "Squares: A Fast Counter-Based RNG". arXiv:2004.06278 [cs.DS].
  38. ^ Corona 방전을 사용한 True Random Number Generator:인도 특허청.특허출원번호 : 201821026766
  39. ^ Thomas Symul; Syed M. Assad; Ping Koy Lam (2011-06-07), "Real time demonstration of high bitrate quantum random number generation with coherent laser light", Applied Physics Letters, 98 (23): 231103, arXiv:1107.4438, Bibcode:2011ApPhL..98w1103S, doi:10.1063/1.3597793

외부 링크