cgy12306

Extended_Euclidean extended_gcd를 이용해서 역원을 구할 수 있다. Modular Exponentiation 밑, 지수, 나머지 계산할 값을 넣고, 지수를 2진수 형태로 바꾼 다음 바이너리 값에서 1에 해당하는 값들을 모두 곱한 후 다시 mod 계산을 해준다. Chinese remainder Theorem 확장 유클리디안 알고리즘을 이용해서 s와 t를 구하고 중국인 나머지 정리 이론 식으로 값을 구한다. Text-book RSA 우선 키 길이와 평문을 먼저 설정해준다. rsa_genkey 함수에서 키 길이를 이용해서 랜덤한 서로소인 소수 p와 q를 생성한다. 소수를 생성할 때 is_prime함수로 소수를 생성하고, is_prime 함수 내부에서 밀러라빈 테스트 함수를 호출하여 소수..

1. integer divisibility(가분성) 0이 아닌 정수 a와 정수가 있다. a가 b를 나눴을 때 b=ak가 되는 k가 존재한다면 Divisibility라고 한다. a|b로 표기한다. Divisibility는 숫자를 작은 원소(primes)로 분해할 때 중요하다. a, b, c 정수가 있다. a가 0이 아닐 때 a|0과 a|a는 성립한다. 또한 1|b의 모든 값은 b이다. a|b이고 b|c이면 a|c이다. a|b이고 a|c이면, 모든 정수 s와 t에 대한 a(sb+tc)이 있다 2. Prime(소수) 만약 p>1이고 1과 자기 자신으로만 나눠진다면 p는 prime이다. 단순히 n>1이면 n은 prime이 아닌 composite이다. 모든 양의 정수는 소수의 결과이다. 소수에 대한 요인은 독특하..