비밀 코드와 우주 통신의 기본 대수학

우주 탐사에는 엄청난 정확성이 필요합니다. 가장 가까운 주유소에서 70천만 마일 떨어진 화성에 로버를 착륙시킬 때 효율성을 극대화하고 예상치 못한 상황에 대비해야 합니다. 이것은 우주선 설계에서 데이터 전송에 이르기까지 모든 것에 적용됩니다. 0과 1의 꾸준한 흐름으로 지구로 돌아오는 메시지에는 약간의 오류가 포함될 수밖에 없으므로 귀중한 시간과 에너지를 낭비하지 않고 오류를 식별하고 수정할 수 있어야 합니다.

그것이 수학이 들어오는 곳입니다. 수학자들은 정보를 전송하고 저장하는 독창적인 방법을 발명했습니다. 놀랍도록 효과적인 한 가지 방법은 다음을 사용합니다. 리드 솔로몬 코드, 학생들이 학교에서 배우는 것과 동일한 기본 대수학을 기반으로 합니다. Reed-Solomon 코드가 비용이 많이 드는 팝업 오류를 수정하면서 정보를 전송하고 보호하는 데 어떻게 도움이 되는지 알아보기 위해 수학 수업에 들르십시오.

Art와 Zeke라는 두 학생이 Ms. Al-Jabr의 수학 수업에서 비밀 메시지를 교환하고 있습니다. Art는 Zeke의 최근 메모를 펼쳐 숫자 57과 99를 공개합니다. x-3과 6을 좌표화하여 점 (3, 57)과 (6, 99)를 만듭니다. Art는 각 점을 선형 방정식에 연결합니다. y = Ax + B 다음 방정식 시스템을 생성합니다.

57 = 3A + B

99 = 6A + B

메시지를 해독하기 위해 Art는 다음을 해결해야 합니다. A 과 B. 그는 두 번째 방정식에서 첫 번째 방정식을 빼는 것으로 시작합니다.

이것은 제거합니다 B. 이 새로운 방정식의 양쪽을 3으로 나누면 Art는 다음과 같이 알 수 있습니다. A = 14, 그리고 이것을 다시 첫 번째 방정식에 대입하면, 57 = 3 × 14 + B, 준다 B = 15.

Art는 이제 (3, 57)과 (6, 99)를 통과하는 선이 다음 방정식으로 설명된다는 것을 알고 있습니다. y = 14x + 15. 그러나 그는 Reed-Solomon 코드에서 비밀 메시지가 계수에 숨어 있다는 것도 알고 있습니다. 그는 동의한 간단한 알파벳 암호를 사용하여 Zeke의 메시지를 해독합니다. 14는 "N"이고 15는 "O"입니다. 이는 Art에게 아니요, Zeke는 오늘 방과 후 비디오 게임을 할 수 없다고 알려줍니다.

이 간단한 리드-솔로몬 코드의 비밀은 기하학의 두 가지 기본 사실에서 시작됩니다. 첫째, 임의의 두 점을 통과하는 고유한 선이 있습니다. 둘째, 계수의 경우 A 과 B, 모든 (수직이 아닌) 줄은 다음 형식으로 작성할 수 있습니다. y = Ax + B. 이 두 가지 사실을 종합하면 직선 위의 두 점을 알면 다음을 찾을 수 있습니다. A 과 B, 알고 있다면 A 과 B, 당신은 라인의 모든 포인트를 알고 있습니다. 요컨대, 두 정보 세트를 모두 소유하는 것은 라인을 아는 것과 같습니다.

Reed-Solomon 코드는 이와 동등한 정보 세트를 활용합니다. 비밀 메시지는 계수로 인코딩됩니다. A 과 B, 라인의 포인트는 여러 조각으로 나뉘며 그 중 일부는 공개적으로 전송되고 일부는 비공개로 유지됩니다. 메시지를 해독하려면 조각을 모아서 다시 모으기만 하면 됩니다. 그리고 이것이 요구하는 모든 것은 간단한 대수입니다.

Zeke의 작품은 그가 Art에 보낸 숫자 57과 99였습니다. 이 번호는 메시지의 공개 부분입니다. Art는 그것들을 자신의 조각인 3과 6과 함께 결합하여 점 (3, 57)과 (6, 99)를 재구성합니다. 여기서 3과 6은 Art와 Zeke가 미리 합의한 메시지의 비공개 부분을 구성합니다.

두 점은 선 위에 있고 메시지를 해독하려면 해당 선의 방정식을 찾으면 됩니다. 각 지점에 연결 y = Ax + B 둘 다 참이어야 하는 선에 대한 두 방정식의 시스템을 제공합니다. 이제 전략은 간단합니다. 시스템을 해결하고 라인을 결정하고 메시지를 해독합니다.

대수학 수업에서 그래프, 추측 및 확인, 대입과 같은 방정식 시스템을 푸는 많은 방법을 배웠을 것입니다. Art는 변수를 한 번에 하나씩 제거하기 위해 방정식을 대수적으로 조작하는 방법인 제거를 사용했습니다. 변수를 제거할 때마다 시스템을 해결하기가 조금 더 쉬워집니다.

다른 암호화 체계와 마찬가지로 메시지를 안전하게 유지하는 것은 공용 정보와 개인 정보의 영리한 조합입니다. Zeke는 교실 전체에서 57번과 99번을 외칠 수 있으며 Art에 대한 그의 메시지의 보안을 위태롭게 하지 않을 것입니다(Al-Jabr 씨와 곤경에 처할 수도 있지만). 해당 개인 정보가 없으면 — x-좌표 3과 6 — 선의 방정식을 식별하는 것은 불가능합니다. 이러한 가치를 자신에게만 유지하는 한 공개적으로 비밀 메시지를 안전하게 전달할 수 있습니다.

라인 y = 14x + 15는 두 글자 단어 "아니오"를 전송하는 데 적합하지만 학생들이 더 긴 비밀을 공유하고 싶다면 어떻게 해야 할까요? 여기에서 대수학, 기하학 및 선형 방정식 시스템의 모든 기능이 작동합니다.

Zeke가 Art가 내일 영어 시험을 어떻게 볼 것이라고 생각하는지 알고 싶어 한다고 가정해 보겠습니다. Art는 세 글자로 된 답을 숫자 14, 59, 82로 변환하여 Zeke에게 전달합니다. 학생들은 길이가 3인 리드-솔로몬 코드를 사용할 때 개인 번호가 2, 5, 6이므로 Zeke가 조각을 모아 점 (2, 14), (5, 59) 및 (6, 82).

이제 이 세 점을 통과하는 선형 함수는 없습니다. 그러나 고유한 이차 함수가 있습니다. 그리고 모든 이차 함수는 다음 형식으로 쓸 수 있기 때문에 y = Ax² + Bx + C, 동일한 일반적인 방법을 적용할 수 있습니다. 유일한 차이점은 시스템의 크기입니다.

각 지점에 연결 y = Ax² + Bx + C 하나의 방정식을 생성하므로 세 점은 다음 세 방정식의 시스템을 생성합니다.

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

XNUMX개의 미지수가 있는 XNUMX개의 방정식 시스템은 XNUMX개의 미지수가 있는 XNUMX개의 방정식 시스템보다 해결하는 데 약간 더 많은 작업이 필요하지만 목표는 동일합니다. 변수를 제거하기 위해 방정식 쌍을 영리하게 결합합니다.

예를 들어 두 번째 방정식에서 첫 번째 방정식을 빼면 새 방정식 45 = 21이 됩니다.A + 3B. 마찬가지로 세 번째 방정식에서 두 번째 방정식을 빼면 23 = 11이 됩니다.A + B. 이러한 대수적 조작은 새로운 시스템을 생성합니다.

45 = 21A + 3B

23 = 11A + B

이제 "two-by-two" 시스템이 있습니다. 두 개의 방정식과 두 개의 미지수가 있습니다. 이를 풀기 위해 두 번째 방정식에 −3을 곱하고 첫 번째 방정식에 추가할 수 있습니다.

반복 소거법이 세 방정식의 원래 시스템을 쉽게 풀 수 있는 단일 방정식으로 바꾸는 방법에 주목하십시오. A = 2. 거꾸로 작업하면 플러그를 꽂을 수 있습니다. A = 2를 XNUMXxXNUMX 시스템의 방정식 중 하나에 입력하여 찾습니다. B = 1, 그런 다음 두 값을 원래 방정식 중 하나에 연결하여 다음을 얻습니다. C = 4. 2, 1, 4에 간단한 알파벳 암호를 사용한 후 Zeke는 Art가 내일 영어 시험에서 "BAD"를 할 것이라는 것을 알고 있습니다. 적어도 그는 대수학 연습을 많이 받고 있습니다.

다항식 함수에 대한 특별한 사실 덕분에 리드-솔로몬 코드를 사용하여 어떤 길이의 메시지도 전송할 수 있습니다. 핵심은 이것입니다. n 서로 다른 평면의 점 x-좌표, "차수"의 고유한 다항식이 있습니다. n - 그것들을 통과하는 1. 다항식의 차수는 식에서 변수의 가장 높은 거듭제곱이므로 다음과 같은 이차 함수 Ax² + Bx + C 의 최고 거듭제곱이므로 차수가 2입니다. x 는 2입니다. 선형 함수의 차수는 1입니다. y = Ax + B, 가장 높은 전력 x 1입니다.

첫 번째 예에서 우리는 두 점이 고유한 선형 또는 1차 다항식을 결정한다는 사실을 사용했습니다. 두 번째에서 우리는 2개의 점이 고유한 10차 또는 10차 다항식을 결정한다는 사실에 의존했습니다. 그리고 길이가 9인 메시지를 보내려면 메시지를 10차 다항식 함수의 XNUMX개 계수로 인코딩하면 됩니다. 기능이 있으면 XNUMX 공개를 계산하십시오. y-미리 합의된 10 private에서 함수를 평가하여 값 x-값. 그렇게 하면 안전하게 통과할 수 있습니다. y-수신기가 디코딩할 수 있도록 공개적으로 좌표를 지정합니다. 실제로 Reed-Solomon 코드는 보다 정교한 종류의 계수 및 변환 체계를 사용하여 이보다 약간 더 복잡하지만 기본 아이디어는 동일합니다.

메시지를 안전하게 유지하는 것 외에도 Reed-Solomon 코드는 오류를 포착하고 수정하는 간단하고 효율적인 방법을 제공합니다. 일부 정보가 손실되거나 손상될 가능성이 항상 있으므로 데이터가 전송되거나 저장될 때마다 중요합니다.

이 문제에 대한 한 가지 해결책은 단순히 데이터의 추가 복사본을 보내는 것입니다. 예를 들어 Zeke는 [14, 14] 대신 [14, 15, 15, 15, 14, 15] 메시지를 보낼 수 있습니다. Art는 메시지의 모든 부분이 14중으로 전송된다는 것을 알고 있는 한 메시지를 해독하고 오류를 확인할 수 있습니다. 사실 그가 어떤 오류를 발견하면 그는 그것을 바로잡을 수 있는 좋은 기회가 있습니다. Art가 [14, 24, 15, 15, 15, 14]를 받으면 처음 세 개의 숫자가 다르다는 사실은 그에게 오류를 경고하고 그 중 두 개는 24이므로 그는 14가 아마도 XNUMX도. 메시지를 재전송하도록 요청하는 대신 Art는 해독을 계속할 수 있습니다. 이것은 효과적이지만 비용이 많이 드는 전략입니다. 보내는 데 시간과 에너지와 노력이 필요하더라도 n XNUMX배의 정보가 필요합니다.

그러나 Reed-Solomon 코드 뒤에 있는 수학은 효율적인 대안을 제공합니다. 모든 데이터의 사본을 여러 개 보내는 대신 추가 포인트 하나만 보낼 수 있습니다! 추가 포인트가 다항식에 맞으면 정보가 정확합니다. 그렇지 않은 경우 오류가 발생한 것입니다.

이것이 어떻게 작동하는지 보기 위해 첫 번째 예에서 "NO" 메시지를 확인한다고 가정합니다. Zeke는 추가 y-coordinate 155. 그와 Art가 세 번째 사병에 동의했다고 가정합니다. x-미리 조정, 말 x = 10, Art는 그가 해독한 라인에 대해 이 세 번째 포인트를 확인할 수 있습니다. 그가 플러그를 꽂을 때 x = 10으로 y = 14x + 15 그리고 결과가 155인 것을 보고 그는 전송에 오류가 없다는 것을 알고 있습니다.

이것은 라인에만 적용되는 것이 아닙니다. 두 번째 예에서 Zeke가 "BAD"를 확인할 수 있도록 Art는 다음을 보낼 수 있습니다. y = 25. 3이 추가 비공개라고 동의한 경우 x-coordinate, Zeke는 연결할 수 있습니다. x = 3을 그의 이차 함수로 y = 2x² + x + 4 지점 (3, 25)이 맞는지 확인하고 한 지점만 더 있으면 오류 없는 전송을 다시 확인합니다.

그리고 그 추가 포인트는 잠재적으로 오류를 수정할 수도 있습니다. 오류가 감지되고 수신자가 메시지를 포함하는 다항식 함수를 구성할 수 없는 경우 대신 회귀 기술을 사용하여 "최적" 다항식을 구성할 수 있습니다. 통계학 수업에서 가장 잘 맞는 선처럼 주어진 점을 모두 통과하지 않더라도 주어진 점에 가장 근접하게 맞도록 수학적으로 결정되는 다항식 함수입니다. 메시지의 구조와 전송하는 추가 정보의 양에 따라 이 최적 다항식은 올바른 다항식을 재구성하여 손상된 정보에서도 올바른 메시지를 재구성하는 데 도움이 될 수 있습니다.

통신 전송 및 수정의 이러한 효율성은 NASA가 달과 화성에 대한 임무에서 리드-솔로몬 코드를 사용한 이유를 설명합니다. 그리고 다음 연립방정식을 풀 때 숙고할 무언가를 제공합니다. 솔루션에 대한 방법을 추측하거나 확인하거나 제거하고 Reed-Solomon 코드의 강력함과 우아함 및 시스템이 공개할 수 있는 모든 비밀을 생각해보십시오.

운동

1. Art는 수업에서 사용한 것과 동일한 방식을 사용하여 Zeke가 해독할 수 있도록 공개 번호 33과 57을 게시합니다. 메시지가 무엇입니까?

2. Art와 Zeke는 그들의 사적인 숫자에서 비롯된 방정식 시스템이 x = 3 및 x = 6은 항상 해결책이 있습니까?

3. Art의 영어 시험에 대한 "나쁜" 메시지에 대한 응답으로 Zeke는 [90, 387, 534]를 회신합니다. 그들이 수업에서 사용한 것과 같은 체계를 사용한다고 가정하면 그의 메시지는 무엇입니까?

4. Lola는 Reed-Solomon 코드와 Art 및 Zeke가 사용하는 동일한 간단한 알파벳 암호를 사용하여 두 글자 메시지와 오류 확인 번호 하나를 보냅니다. 당신은 비밀리에 동의했습니다 x-미리 1, 3, 10을 좌표하고 Lola는 공개 번호 [27, 43, 90]를 전송합니다. 메시지에 오류가 포함되어 있습니까?