잔류수 체계

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글에는 주제의 여러 측면에 대한 정보가 누락되어 있다(토크 페이지 참조). 이 정보를 포함하도록 문서를 확장하십시오. 자세한 내용은 대화 페이지에 있을 수 있다.(2018년 7월) 이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "재고번호 시스템" – 뉴스 · 신문 · 도서 · 학자 · JSTOR (2018년 7월) 이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2018년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

잔류수계(RNS)는 moduli라고 불리는 여러 쌍의 복사 정수로 그 값으로 정수를 나타내는 숫자계다.이 표현은 중국의 나머지 정리에 의해 허용되는데, 이 정리는 만약 M이 모듈리의 산물이라면, 길이 M의 간격에 주어진 모듈 값을 가진 정수가 정확히 한 개 있다고 주장한다.잔류수계의 산술은 다모듈식 산술이라고도 한다.

다모형 산술은 일반적으로 선형대수에서 큰 정수를 가진 계산에 널리 쓰이고 있는데, 이는 숫자계 사이의 변환 시간을 고려하더라도 일반적인 숫자계보다 더 빠른 계산을 제공하기 때문이다.다항식 산술의 다른 응용 프로그램으로는 다항식 최대 공통 디비저, 그뢰브너 기반 계산 및 암호화가 있다.

정의

잔류수계는 k 정수의 집합에 의해 정의된다.

${\displaystyle \{m_{1},m_{2},m_{3},\ldots,m_{k}\},}$

일반적으로 쌍으로 이루어진 복사(즉, 둘 중 어느 것이든 1과 같은 가장 큰 공통의 구분자를 가지고 있다)라고 하는 moduli라고 한다.잔류물 번호 시스템은 비복사 시간 모듈리에 대해 정의되었지만, 더 나쁜 특성 때문에 일반적으로 사용되지 않는다.따라서 이 글의 나머지 부분에서는 이러한 사항을 고려하지 않을 것이다.^[1]

정수 x는 잔여 숫자 시스템에 잔존자 집합으로 표시된다.

${\displaystyle \{x_{1},x_{2},x_{3},\ldots,x_{k}\}}}$

모둘리에 의한 유클리드 분할하에그것은

${\displaystyle x_{i}=x\designname {mod}m_{i}}$

그리고

${\displaystyle 0\leq x_{i}<m_{i}}$

어느 모로 보나

${\displaystyle M_{}}$을 모든 $m{\displaystyle {}_{}}$ i ${\$의 산물이 되게 하라$.$ M의 배수가 다른 두 정수는 ms에_i 의해 정의된 잔류수 시스템에서 동일한 표현을 가진다.더 정확히 말하면, 중국의 나머지 정리는 각각의 다른 M의 가능한 잔류물 세트가 정확히 하나의 잔류물 등급 모듈로 M을 나타낸다고 주장한다.That is, each set of residues represents exactly one integer ${\displaystyle X}$ in the interval ${\displaystyle 0,\dots ,M-1}$. For signed numbers, the dynamic range is ${\textstyle -\lfloor M/2\rfloor \leq X\leq \lfloor {\frac {M-1}{2}}\rfloor }$ (when ${\displaystyle$$M}$은(는) 짝수이며, 일반적으로 음수 값이 추가로 표시된다).^[2]

산술 연산

잔류물 번호 시스템에 표시된 숫자를 추가, 빼기 및 곱하기 위해, 각 잔류물 쌍에 대해 동일한 모듈식 연산을 수행하는 것으로 충분하다.더 정확히 말하자면

${\displaystyle [m_{1},\ldots ,m_{k}]}$

is the list of moduli, the sum of the integers x and y, respectively represented by the residues ${\displaystyle [x_{1},\ldots ,x_{k}]}$ and ${\displaystyle [y_{1},\ldots ,y_{k}],}$ is the integer z represented by ${\displaystyle [z_{1},\ldots ,z_{k}]$$,}$ 그런$$ 것.

${\displaystyle z_{i}=(x_{i}+y_{i})\modname {m_{i}}}$

i = 1, ..., k (평소처럼 모드는 오른쪽 피연산자에 의해 유클리드 분할의 나머지를 취하는 것으로 구성되는 모듈로 연산을 나타낸다.)뺄셈과 곱셈은 유사하게 정의된다.

연산을 위해서는 각 단계에서 modulo 운전을 적용할 필요가 없다.이는 계산이 끝날 때 또는 계산 중에 하드웨어 작동의 오버플로우를 방지하기 위해 적용될 수 있다.

단, 진도비교, 부호계산, 오버플로 감지, 스케일링, 디비전 등의 작업은 잔류수 시스템에서 수행하기가 어렵다.^[3]

비교

만약 두 정수가 같다면, 그들의 모든 잔여물은 동일하다.반대로 모든 잔류물이 동일하면 두 정수가 같거나 그 차이가 M의 배수인 것이다.평등을 시험하는 것은 쉽다는 것을 따른다.

반대로, 불평등(x < y)을 시험하는 것은 어렵고, 일반적으로 정수를 표준 표현으로 변환해야 한다.따라서 이러한 숫자의 표현은 유클리드 분할 및 유클리드 알고리즘과 같은 불평등 시험을 사용하는 알고리즘에는 적합하지 않다.

나누기

잔류수 체계의 분할은 문제가 있다.한편, $B{\displaystyle }$ ${\displaystyle B}$이(가) M ${\displaystyle M}($b ${\displaystyle \mathrm{i}{}_{}{i}_{}}$ 0$${\$displaystyle b_{i}\not =$0})과$($와) 동일하다면,

${\displaystyle C=A\cdot B^{-1}\mod M}$

에 의해 쉽게 계산할 수 있다

${\displaystyle c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i}}}$

여기서 $B{\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$는 $B{\displaystyle }$ ${\displaystyle B}$$모듈로M$ ${\displaystyle M}$의 곱셈 역이며$,$ $b{\displaystyle {}_{}^{}}$ -${\displaystyle 1_{}^{}}$ ${\$ $b_{i}^{$1}-$1}$는 $b{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ $m\_{\displaystyle {}_{}}${$i}$의 곱셈 역이다$.$

적용들

이 구간은 확장이 필요하다.추가하면 도움이 된다.(2018년 7월)

RNS는 디지털 컴퓨터 산술 분야에 응용 프로그램을 가지고 있다.이렇게 큰 정수를 작은 정수의 집합으로 분해함으로써, 큰 계산은 독립적으로 동시에 수행할 수 있는 일련의 작은 계산으로 수행할 수 있다.

참고 항목

• 커버링 시스템
• 잔류물 감소 시스템

참조

추가 읽기

• Szabo, Nicholas S.; Tanaka, Richard I. (1967). Residue Arithmetic and its Applications to Computer Technology (1 ed.). New York, USA: McGraw-Hill.
• Sonderstrand, 마이클 A., 젠킨스, W. 케네스, 줄리앙, 그레이엄 A;.테일러, 프레드 J., eds.(1986년).유수 번호 시스템 대수:디지털 신호 처리의 현대 응용 프로그램은 실패한다.IEEE프레스를 증쇄하다 시리즈(1판).미국 뉴욕:IEEE회선 및 제도에 협회 IEEE를 누르다.아이 에스비엔 0-87942-205-X.LCCN 86-10516.IEEE주문 코드 PC01982.(viii+418+6 페이지)
• 체르비야코프(N. I.); 몰라호세이니(A. S.), 리아호프(Lyakhov) P.A. (2017).일반 모듈리 집합의 잔존 변환은 대략적인 중국 잔여 정리에 기초한다.국제수학저널, 94:9, 1833-1849, doi: 10.1080/00207160.2016.124439.
• Fin'ko [Финько], Oleg Anatolevich [Олег Анатольевич] (June 2004). "Large Systems of Boolean Functions: Realization by Modular Arithmetic Methods". Automation and Remote Control. 65 (6): 871–892. doi:10.1023/B:AURC.0000030901.74901.44. ISSN 0005-1179. LCCN 56038628. S2CID 123623780. CODEN AURCAT. Mi at1588.
• 체르비야코프, 리야호프, P. A., 데랴빈, M. A. (2020)경동신경망의 하드웨어 비용 절감을 위한 잔여 번호 시스템 기반 솔루션.신경 컴퓨터, 407, 439-453, 도이: 10.1016/j.뉴콤.2020.04.018.
• Bajard, Jean-Claude; Méloni, Nicolas; Plantard, Thomas (2006-10-06) [July 2005]. "Efficient RNS bases for Cryptography" (PDF). IMACS'05: World Congress: Scientific Computation Applied Mathematics and Simulation. Paris, France. HAL Id: lirmm-00106470. Archived (PDF) from the original on 2021-01-23. Retrieved 2021-01-23. (1+7페이지)
• Omondi, Amos; Premkumar, Benjamin (2007). Residue Number Systems: Theory and Implementation. London, UK: Imperial College Press. ISBN 978-1-86094-866-4. (296쪽)
• Mohan, P. V. Ananda (2016). Residue Number Systems: Theory and Applications (1 ed.). Birkhäuser / Springer International Publishing Switzerland. doi:10.1007/978-3-319-41385-3. ISBN 978-3-319-41383-9. LCCN 2016947081. (351쪽)
• Amir Sabbagh, Molahosseini; de Sousa, Leonel Seabra; Chip-Hong Chang, eds. (2017-03-21). Embedded Systems Design with Special Arithmetic and Number Systems (1 ed.). Springer International Publishing AG. doi:10.1007/978-3-319-49742-6. ISBN 978-3-319-49741-9. LCCN 2017934074. (389쪽)
• https://web.archive.org/web/20050217165652/http://www.cs.rpi.edu/research/ps/93-9.ps. Archived from the original on 2005-02-17. Retrieved 2021-01-23. {{cite web}}: 누락 또는 비어 있는(도움말) 분할 알고리즘
• Knuth, Donald Ervin. The Art of Computer Programming. Addison Wesley.
• Harvey, David (2010). "A multimodular algorithm for computing Bernoulli numbers". Mathematics of Computation. 79 (272): 2361–2370. doi:10.1090/S0025-5718-2010-02367-1. S2CID 11329343.
• Lecerf, Grégoire; Schost, Éric (2003). "Fast multivariate power series multiplication in characteristic zero". SADIO Electronic Journal on Informatics and Operations Research. 5 (1): 1–10.
• Orange, Sébastien; Renault, Guénaël; Yokoyama, Kazuhiro (2012). "Efficient arithmetic in successive algebraic extension fields using symmetries". Mathematics in Computer Science. 6 (3): 217–233. doi:10.1007/s11786-012-0112-y. S2CID 14360845.
• Yokoyama, Kazuhiro (September 2012). "Usage of modular techniques for efficient computation of ideal operations". International Workshop on Computer Algebra in Scientific Computing. Berlin / Heidelberg, Germany: Springer. pp. 361–362.
• Hladík, Jakub; Šimeček, Ivan (January 2012). "Modular Arithmetic for Solving Linear Equations on the GPU". Seminar on Numerical Analysis. pp. 68–70.
• Pernet, Clément (June 2015). "Exact linear algebra algorithmic: Theory and practice". Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation. Association for Computing Machinery. pp. 17–18.
• Lecerf, Grégoire (2018). "On the complexity of the Lickteig–Roy subresultant algorithm". Journal of Symbolic Computation.
• Yokoyama, Kazuhiro; Noro, Masayuki; Takeshima, Taku (1994). "Multi-Modular Approach to Polynomial-Time Factorization of Bivariate Integral Polynomials". Journal of Symbolic Computation. 17 (6): 545–563. doi:10.1006/jsco.1994.1034.
• 이슈포프, 콘스탄틴(2021년)." 부유점 산술법을 이용한 잔존수 시스템의 고성능 연산"계산. 9(2): 9. doi:10.3390/computation 9020009.ISSN 2079-3197.