Fermat'sTheorem
페르마 이론
If p is prime and a is apositive integer not divisible by p (gcd(a,p)=1), then
p가 소수이고 a가 양의 정수이면서 p에 의해 나누어 지지 않는다면, gcd(a,p)=1 이면
ap-1 = 1(mod p)
also known as Fermat’s LittleTheorem
An alternative form of Fermat’stheorem is also useful
ap =a(mod p)
This form does not require that a be relatively prime to p
useful in public key and primality testingEulerTotient Function ø(n)
이건 별로 어려운건 아니지만 헷갈 릴 수 있다.
어떤 수 n으로 나누어서 나오는 나머지의 집합은 : 0 .. n-1 이다.
이제 예를 들어보자 10으로 나누어서 나올 수 있는 나머지는 1, 2, 3, .... ,9 인데
여기서 10과 서로소인 것을 다 제거 해보자
그러면 1, 3, 7 ,9 가 나올 것이다.
이것을 용어로 정리하면
complete set of residues = {0, 1, ..... 9}
reduced set of residues = {1, 3, 7, 9}
이고
Euler totient function Φ(10)은 바로 reduced set of residues의 원소 갯수 4 이다.
만약 n이 소수라면 그것은 모든 수와 다 서로소 이기 떄문에 Φ(n) = n-1 이된다.
Euler'sTheorem
오일러 이론은 페르마 이론의 일반화를 한것이다.
aø(n) = 1 (mod n)
for any a,n where gcd(a,n)=1 a와 n 은 서로소 이다.
if n is prime and gcd(a,n)=1, this is Fermat’s theorem. That is, aø(n) = an-1 = 1 (mod n)
n이 소수라면 페르마 정리랑 같아 진다.
eg.
a=3;n=10; ø(10)=4;
hence34 = 81= 1 mod 10
a=2;n=11; ø(11)=10;
hence210 =1024 = 1 mod 11
Alternative form of the Euler’s theorem also useful.
aø(n)+1 = a (mod n), where gcd(a,n)=1 a,n은 서로소 이다.
이게 무엇일까? 만은 암호알고리즘에서 랜덤으로 매우 큰 소수를 선택하는것이 중요한데 그래서 우리는 어떤큰수가 소수인지 아닌지를 판별할 수 있어야 한다. 옛날에는 무식하게 나누는 것을 했겠지만 이건 엄청난 시간이 들겠지. 모든 소수가 만족하는 속성과, 수도 프라임이라고 불리는 것또한 알아보자 이것들이 primality testing의 핵심이다.
Naïvemethods
가장간단한 방법인데 n이 있으면 2~n-1 까지 다 나누어 보고 나누어지는게 없음 그게 소수 라는건데
The probabilistic tests:
Most popular primality tests areprobabilistic tests
가장 유명한 테스트가 바로 확률 테스트다
These tests use, apart from thetested number n, some other numbers a which are chosen at random from some sample space
이 테스트들은 사용되는데 테스트 되는 숫자 n 과 다른 숫자 a가 서로 떨어진다. a 어떤 샘플 공간에서 랜덤적으로 선택이된다.
The usual randomized primality tests never report a primenumber as composite, but it is possible for a composite number to be reportedas prime
일반적으로 랜덤화하는 소수 테스트는 소수가 합성수로 보고가 되지 않는다, 하지만 합성수가 소수로 보고 되는 가능성이있다.
The probability of error can bereduced by repeating the test with several independently chosen as; for two commonly used tests
에러를 없애기 위해서 테스트 어떤 독립적인 선택된수 as 와 함게 반복적으로 테스트를 행한다; 두개의 널리쓰이는 테스트들이 있다.
For any composite n at least half the as detect n 's compositeness, so krepetitions reduce the error probability to at most 2−k, which can be made arbitrarilysmall by increasing k.
어떤 합성수 n은 적어도 aS의 절반이고 n의 합성수가 ?? 그래서 에러를 줄인다 뭐 이런 내용인듯??
1. 랜덤하게 숫자 a를 뽑는다.
2. a 와 주어진수 n 의 equality를 검사한다. 만약 equality fails to hold가 참이면, n은 함성수, a은 n이 합성수인것의 목격자가 되고 테스트는 중단.
3. 스텝1을 반복한다.
뭐 이런식으로 하는데 이것도 확실 치 않다.
'CSE(컴퓨터 공학) > 컴퓨터 보안' 카테고리의 다른 글
| Chapter5 Advanced Enctyption Standartd (0) | 2009.04.15 |
|---|---|
| 필요한 약간의 이산수학 2 지식 (0) | 2009.04.15 |
| 보안 강의자료 중간고사 까지 모듬 (0) | 2009.04.14 |
| Chater3 Block Ciphers & DES(Data Enctyption Standard) (0) | 2009.04.14 |
