GF (p ^ n) 가로 와 역

4013 단어 암호 화
수학 용어
이 또는: 같은 것 은 0 이 고 다른 것 은 1 과: 하 나 는 0 이 며 결 과 는 0 이다.
아래 의 기 호 는 일종 의 연산 + 표시 덧셈 연산 을 나타 낸다. * 곱셈 연산 을 나타 내 는 이곳 의 덧셈 과 곱셈 은 모두 하나의 연산 이지 정수 중의 덧셈 과 곱셈 을 특별히 가리 키 는 것 이 아니다.
무리.
설정 G 는 비 공 집합 이 고 연산 '•' 가 존재 합 니 다. 만족 하면 (1) 결합 율: (a • b) • c = a • (b • c) (2) 항등원: e • a = a • e = a (3) 에 역 원소 가 존재 합 니 다. a • b = b • a = e 는 G 를 군 이 라 고 부 릅 니 다.
예 를 들 어 정수 중의 덧셈 연산 에 있어 e = 0 은 다음 과 같은 조건 (a + b) + c = a + (b + c) 0 + a = a + 0 = a + (- a) = (- a) + a = 0 을 만족 시 키 는 것 이 분명 하 다.
실수 중의 곱셈 연산 에 있어 e = 1 (a * b) * c = a * (b * c) 1 * a = a * 1 = a * 1 = a * 1 / a = 1 / a * a = 1 / a * a = 1
정 수 는 하나의 덧셈 군 이지 만 곱셈 군 이 아니다. 왜냐하면 곱셈 역 원 이 없 기 때문이다.
고리.
설정 R 은 두 가지 연산 조작 이 있 는데 각각 +, *, 즉 덧셈 조작 과 곱셈 조작 이 고 덧셈 군 이 며 다음 과 같은 조건 을 만족시킨다.
  • ( a * b ) * c = a * ( b * c )
  • 분배 율 a * (b + c) = a * b + a * c (b + c) * a = b * a + c * a
  • R 을 고리 라 고 부 르 는 것 은 분명 하 다. 정수, 실수, 복 수 는 모두 고리 이다.
    교환 고리
    만약 에 다음 과 같은 조건 을 만족 시 키 면 a * b = b * a 는 라 고 부른다.
    영역
    만약 에 다음 과 같은 조건 (1) 에 e 요소 가 존재 한다 면 e • a = a • e = a (2) 에 역 요소 가 존재 한다. a • b = b • a = e 는 라 고 부른다.
    정수 가 하나 가 아니다 유한 도 메 인
    정의.
    만약 에 과 역 중의 요소 가 유한 하 다 면 이 라 고 부 르 고 그 요소 의 개 수 를 n 으로 설정 합 니 다.
    특성:
  • 유한 도 메 인 요소 의 개 수 는 반드시 하나의 소수 이다. (왜 그런 지 모 르 겠 지만 페 마 의 작은 정리 와 관련 이 있 을 것 으로 추정 된다)
  • 곱셈 항등원 e1 과 덧셈 항등원 e0, e1 + e1 + e1 +... + e1 = e0, (즉 n 개 e1 더하기)
  • 예 를 들다
    동 여 연산 을 예 로 들 면 a mod p, b mod p, c mod p 를 각각 a, b, c 대 p 의 모델 링 규칙 을 설정 하면 다음 과 같다 (a mod p) + (b mod p) = (a + b) mod p 는 분명 하 다. 덧셈 작업 만족 도 메 인의 정 의 는 다음 과 같다 (a mod p) * (b mod p) = (a * b) mod p 는 분명 하 다. 곱셈 작업 은 교환 율 을 만족시킨다.
    다음은 mod 기호 덧셈 항등원 을% 로 대체 하여 0% p 곱셈 항등원 은 1% p 이다.
    하나의 질 수 를 취하 여 11 이 라 고 가정 하면 이러한 수 집 (p = 11) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 은 어떤 특성 을 만족 시 키 는 지 먼저 보고 다음은 mod 를% 로 대체 합 니 다.
  • 11 개 1% 11 을 더 하면 11% 11 로 0% 11
  • 과 같다.
  • 모든 비 0 원소 에는 역 원 이 있다. 예 를 들 어 1% 11 * 1% 11 = 1% 11 2% 11 * 6% 11 = 12% 11 = 1% 11 3% 11 * 4% 11 = 12% 11 = 1% 11 5% 11 * 9% 11 = 45% 11 = 1% 11 7% 11 * 8% 11 = 56% 11 = 1% 11 10% 11 * 10% 11 = 100% 11 = 1% 11 즉 1 에서 10 까지 의 모든 원소 에 곱셈 역 원 이 존재 한다. (기묘 하 다)
  • 예시 2
    극단 적 인 예 를 들 어 p = 2 {0, 1} 을 보면 덧셈 의 성질 1% 2 + 1% 2 = 0% 2 0% 2 + 0% 2 = 0% 2 1% 2 + 0% 2 = 1% 2 덧셈 규칙 은 같은 0, 다른 1 로 컴퓨터 에서 이 연산 을 연산 이 라 고 부른다.
    곱셈 의 성질 을 다시 보면 1% 2 * 1% 2 = 1% 2 0% 2 * 0% 2 = 0% 2 1% 2 * 0% 2 = 0% 2 곱셈 규칙 은 그 중의 한 요소 가 0 이면 결 과 는 0 이 고 컴퓨터 에 서 는 이 연산 을 연산 이 라 고 부른다.
    GF(q)
    GF (q) 의 정의:
  • q = pn, p 는 소수
  • 그 요 소 는 여러 가지 식 으로 표현 된다. 즉, {1, x1, x2, x3..., xn - 1} 으로 여러 가지 조합 을 한다.
  • 그의 덧셈 연산 규칙 은 매우 특수 하여 같은 항목 의 계수 에 대해 연산 을 한 다음 에 n 차 다항식 M 취 모
  • 를 한다.
  • 그의 곱셈 연산 규칙 은 먼저 일반적인 다항식 곱셈 에 따라 n 차 다항식 M 에 대해 모형 을 취한 다
  • .
  • 이런 다항식 M 을 본원 다항식 이 라 고 하 는데 어떻게 찾 아 냈 습 니까?나 도 몰라, 매 거 진 으로?맞 춰 볼 까?어차피 인터넷 에서 계 산 된 걸 찾 을 수 있 을 거 야
  • 예 를 들 어 p = 2, n = 3 을 설정 하면 {1, x1, x2} 을 여러 조합 한 다음 에 0 을 더 해서 GF (8) {0, 1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1} M = x3 + x + 1 을 얻 을 수 있 습 니 다.
  • 덧셈 연산 규칙 예 를 들 어 현재 덧셈 연산 (사실은 연산) x + x = 0 (계수 가 같 고 값 이 0) 을 검증 하고 역 연산 은 0 - x = x, 즉 - x = x, 즉 GF (q) 에서 요소 의 덧셈 역 원 은 바로 그 자체 x + x + 1 = 1 x + x2 = x2 + x + x2 + x + x 2 + x = x2
  • 이다.
  • 곱셈 연산 규칙 예시 x * (x2 + 1)% M = (x3 + x)% M = (x3 + x + 1)% M = (x3 + x + 1)% M = (x3 + x + 1)% M = (x3 + x + x 2 + x)% M = (x3 + x + x)% M = (x3 + x + 1 + 1)% M = (x3 + x + 1 + 1)% M = 1 같은 이치 에 x2 * (x2 + x + 1)% M = 1 이 있 음 을 알 수 있 듯 이 모든 비 0 요소 에 곱셈 역 원
  • 이 있 음
    컴퓨터 의 bit 로 x2 + x1 + x0 을 111 x2 로 표시 하고 100 x1 을 010 으로 표시 하면 GF (8) 는 {000, 001, 011, 100, 101, 110, 111} M = 1011 010 * 101 = 001 011 * 110 = 001 100 * 111 = 001
    컴퓨터 에서 의 응용
    1 개의 바이트 8bit, GF (28) 도 메 인 을 생 성 할 수 있 습 니 다. 원래 의 다항식 은 x8 + x4 + x3 + x + 1 입 니 다.https://en.wikipedia.org/wiki/Finite_field_arithmetic#Rijndael.27s_finite_field

    좋은 웹페이지 즐겨찾기