mathjs 님의 블로그

합성수 n에 대하여 이차잉여의 성질을 일반화한 것으로 Legendre 확장형으로 아래와 같은 정의한다.정의.1합성수 n = ∏(pi)ei (i = 1, 2, ... k) 홀수인 양의 정수이고, 최대공약수 (a, n) = 1을 만족하는 a가 있다고하면Jacobi Symbol (a/n)는 다음과 같이 정의 된다.(a/n) = (a/p1)e1.(a/p2)e2 ... (a/pk)ek  (i = 1, 2, ... k)여기서, (a/pk)는 Legendre Symbol이다.※ Legendre 성질을 그대로 만족하지만, (a/n)=1이라고해서 x2 ≡ a mod n이 해를 갖는다고 할 수 없다.정리.1m과 n을 홀수의 정수라고 두자. Jacobi Symbol은 다음과 같은 성질이 있다.1) (a/n) = ((a-n)..

르장드르 기호(Legendre Symbol)은 이차잉여 여부를 판별하는 기호로 홀수인 소수 p와 정수 a에 대해 다음과 같이 정의 합니다.정의.1홀수의 소수를 p라 두면, Legendre Symbol은  다음과 같이 정의 된다. 예제 1. x2 ≡ a (mod 7)에서 Legendre Symbol ( a / 7 )x = 1 ~ 6 입력한 계산값.▷ 12 ≡ 1 (mod 7)▷ 22 ≡ 4 (mod 7)▷ 32 ≡ 2 (mod 7)▷ 42 ≡ 2 (mod 7)▷ 52 ≡ 4 (mod 7)▷ 62 ≡ 1 (mod 7) a = 1, (1/7) = 1, → QR,a = 2, (2/7) = 1, → QR,a = 3, (3/7) = -1, → NQRa = 4, (4/7) = 1, → QR,a = 5, (5/7) =..

주어진 합성수 n=pq (여기서 p와 q는 소수)의 법 아래에서 임의의 정수 u가 2차 잉여류인지 여부를 결정하는 문제는, n의 소인수 p와 q가 알려져 있지 않을 경우 매우 어려운 문제로 알려져 있습니다. u가 법 n에 대한 이차 잉여류라는 것은 w2 ≡ u mod  n을 만족하는 w가 존재함을 의미합니다.정의.1 법 n = p*q에 대한 2차 잉여류 u가 존재할때, a mod p와 a mod q는 각각 법 p,q에 대한 2차 잉여류이다.만약 up= u mod p, uq = u mod q라 하면, u가 법 n에 대한 2차 잉여류이면 w2 ≡ u (mod n)을 만족하는 제곱근 w가 존재하고 w2 ≡ u (mod p) 또는 w2 ≡ u (mod q)가 성립한다.따라서, w2 ≡ up (mod p) 그리고..

이차 잉여 제곱근 구하기이차 잉여 제곱근 알고리즘 /*   @ 이차잉여 x2 ≡  a (mod p)를 만족하는 제곱근을 구한다.  @ 초기값: 이차 비잉여 b  @ 초기값: 방정식 p - 1 = 2s * t  만족하는 s와 t 계산한다. (여기서 t 홀수)  @ 파라메터: ( a, p ) a:이차잉여, p: 소수  @ 반환값: x, p-x */function squareRootMod ( a, p) {     let inv_a, b, c, d, e, i, rx, s = 0, t = p - 1;    // 임의의 이차 비잉여(NQR)     do {                     b = Math.floor((Math.random()*p));                           if (b ==..

홀수의 소수 p에 대해, 이차 합동 관계 a·x2 + b·x + c ≡ 0 (mod p), (a ≠ 0)가 주어졌을 때, 이를 단순히 나타내기 위해 x → (x - b)/2a로 치환하고 특정형태로 변형할 수 있다. 그 결과는 다음과 같은 합동식으로 나타낼 수 있다.    x2 ≡ k (mod p) 정의.1홀수 소수를 p라 두고, p로 나누어지지 않는 정수를 k라하자. 합동식 x2 ≡ k (mod p)을 만족하는 어떤 x가 존재하면 k를 "이차 잉여(Quadratic Residue, QR)"라고 부른다. 만약 그러한 x가 존재하지 않으면, k를 "이차 비잉여(Quadratic Non-Residue, NQR)"라고 한다. 예제 1. p = 7, 원소 { 1, 2, 3, 4, 5, 6 } 일 때, 이차 잉여(..

중국인의 나머지 정리(CRT)정리.1r개의 정수 p1, p2, ..., pr 이 주어졌을 때,임의의 두 정수에 대해서 서로 소의 관계에 있다면, i ≠ j 에 대해서 gcd( pi , pj ) = 1 이면,연립 합동식 x ≡ xi (mod pi) i = 1, 2, ..., r에는 법 n = p1·p2· ... ·pr에 유일한 해가 존재한다.        x = [ ∑ (n/pi)·qi·xi ] mod n (범위: i = 1부터 r 까지)이때 qi는 법 pi에 대한 (n/pi)의 곱셈상의 역원이 된다. 예제 1. x ≡ 3 (mod 11), x ≡ 7 (mod 17)의 연립합동식?→ p1 = 11, p2 = 17, 서로소의 관계 법 n = p1*p2 = 11*17 = 187→ 곱셈상의 역원을 각각 구한다...

페르마의 소정리(Fermat's Little Theorem). 오일러 피함수   aφ(n) ≡ 1 (mod n) 연장선으로 보면 된다.n = p (소수)라면 φ(p) = p - 1aφ(p) = a(p-1) ≡ 1 (mod p) ∴  ap ≡ a (mod p) 정리.1소수 p라 두고, 어떤 정수를 a라 두면,     ap ≡ a (mod p) 예제 1. a = 5, p = 7    → 57 = 78125 ≡ 5 (mod 7)    → 56 = 15625 ≡ 1 (mod 7)

오일러 피 함수(Euler's Totient Function)정의.1φ(n) = |{ 1 ≤ i ≤ n | gcd(i, n) = 1 }|φ(n)는 n과 서로소의 관계가 있는 1과 n사이의 정수의 개수이다.예제) n = 1부터 15까지 각각의 φ(n)과 서로소 원소를 나열하자.   → n =   1 일때,   φ(1) = 1,  { 1 }   → n =   2 일때,   φ(2) = 1,  { 1 } (소수)   → n =   3 일때,   φ(3) = 2,  { 1, 2 } (소수)   → n =   4 일때,   φ(4) = 2,  { 1, 3 }   → n =   5 일때,   φ(5) = 4,  { 1, 2, 3, 4 } (소수)   → n =   6 일때,   φ(6) = 2,  { 1, 5 } ..

정의.1양의 정수 n에 대하여 두 정수 a,b의 차 a-b가 n의 배수일 때, 즉 n|(a-b)이면 a와 b는 법(modulus) n에 대하여 서로 합동이라하고 다음과 같이 나타낸다.    a ≡ b (mod n)정수 a를 n으로 나누었을 때의 나머지는 다음과 같이 나타낸다.    a mod n = ra mod n = r이면, a ≡ r (mod n)이 만족된다. r을 법 n에 대한 a의 잉여(residue)라 부른다.임의의 정수 a는 {0, 1, 2, ...,n-1} 중의 어느 한 정수와 법 n에 대하여 합동이다. 예제 1. a = 23, b = 3, n = 5일 때, 23 ≡ 3 (mod 5)는 합동관계이다.     →  a = 23 mod 5 = 3     →  b = 3 mod 5 = 3     ..

최소공배수(The Least Common Multiple)는  두 개 또는  그 이상의 자연수에서 공통으로 나오는 배수 중 가장 작은 값을 의미합니다. 이를 계산하는 방법은 다음과 같습니다. 1. 공약수로 나누기: 입력한 자연수가 서로소가 될 때까지 공약수로 계속 나누는 방법     예) LCM(24, 20) = 120      →  2  )_ 24 , 20       →  2  )_12 , 10                     6 ,   5       → 최소공배수(LCM)= 2*2*6*5 = 120, 참고로 최대공약수(GCD) =  2*2 = 4. 2. 소인수 분해: 각 수를 소인수 분해하여 소인수 중 최대 지수를 선택해 곱하는 방법    예) LCM(24, 20) = 120    →  24 = ..