도구스개발

베를레캄프–매시(최단 LFSR) 계산기

유한체 위의 수열 앞부분만 보고 그것을 만들어 내는 가장 짧은 선형점화식을 찾습니다. 매 단계의 불일치 d와 그때의 연결다항식 C(x)·되돌림 다항식 B(x)를 표로 보여 주고, 찾은 점화식으로 수열을 다시 만들어 원래 값과 맞는지 검산합니다.

쉼표나 공백으로 구분합니다. 60개까지, 음수·중복 모두 됩니다.

찾은 차수 L

2

앞 4개 항이면 이 차수가 확정됩니다 (입력은 8개)

점화식s_i = 1·s_{i-1} + 1·s_{i-2} (mod 999983)
연결다항식 C(x) 계수[1, 999982, 999982]
점화식으로 재현한 수열이 원래와 일치하는가일치
재현한 수열1, 1, 2, 3, 5, 8, 13, 21

단계별 자취 — 불일치 d, C(x), B(x)

idLC(x)B(x)
011[1, 999982][1]
101[1, 999982][1]
212[1, 999982, 999982][1, 999982]
302[1, 999982, 999982][1, 999982]
402[1, 999982, 999982][1, 999982]
502[1, 999982, 999982][1, 999982]
602[1, 999982, 999982][1, 999982]
702[1, 999982, 999982][1, 999982]

d=0인 자리는 점화식이 그대로입니다. L(파란 강조)이 늘어나는 자리는 언제나 2L≤i일 때뿐입니다 — 불일치가 났다고 무조건 차수를 늘리지 않습니다.

2L개 항이면 차수 L짜리 점화식이 확정됩니다. 미지수가 계수 L개이면서, 「지금까지의 점화식이 틀렸다」는 신호도 확인해야 하므로 딱 2L개가 경계선입니다. 선형귀환시프트레지스터(LFSR)로 만든 스트림이 출력 비트 2L개만 새어 나가도 내부 상태 전체가 복원되는 이유이기도 합니다.
부동소수점 오차를 피하려고 법(p)은 1,000,000 이하의 소수만 받습니다. 더 큰 법이 필요하면 BigInt로 직접 계산해야 합니다.

사용 방법

  1. 1법(소수 p)을 정합니다. 정수 수열이면 대부분 큰 소수 하나로 충분합니다.
  2. 2수열을 입력합니다. 차수 L짜리 점화식이 숨어 있다면 앞 2L개만 있어도 찾아냅니다.
  3. 3단계별 표에서 불일치 d가 0이 아닌 자리마다 C(x)가 어떻게 바뀌는지 봅니다.
  4. 4찾은 점화식으로 수열을 이어 만들어 원래 값과 일치하는지 확인합니다.

자주 묻는 질문

s_i = c_1·s_{i−1} + c_2·s_{i−2} + ... + c_L·s_{i−L} (mod p) 형태의 점화식 가운데 차수 L이 가장 작은 것을 찾습니다. 이런 점화식을 만족하는 수열이라면, 앞의 2L개 항만 보고도 계수와 차수를 정확히 복원할 수 있습니다.

미지수가 계수 L개이면서, "지금까지 세운 점화식이 이 항에서 어긋난다"는 신호를 확인하려면 항이 하나 더 필요합니다. 그래서 L개만으로는 부족하고 2L개가 되어야 차수 L짜리 점화식임이 확정됩니다. 더 준다고 답이 달라지지 않고, 덜 주면 더 짧은(때로는 틀린) 점화식으로 오인될 수 있습니다.

선형귀환시프트레지스터(LFSR)로 만든 출력은 정의상 선형점화식을 따릅니다. 그래서 LFSR 하나로만 만든 스트림은 출력 비트가 2L개(L은 레지스터 길이)만 새어 나가도 이 알고리즘으로 내부 상태 전체가 복원됩니다. 그 때문에 실전 스트림 암호는 LFSR을 그대로 쓰지 않고 비선형 결합이나 필터를 반드시 섞습니다.

d는 그 시점의 점화식 C(x)로 다음 항을 예측했을 때 실제 값과 어긋난 정도입니다. d=0이면 지금 점화식이 맞으므로 그대로 둡니다. d≠0이면 예전에 처음 실패했던 점화식 B(x)를 끌어와 x^m만큼 밀어서 C(x)에서 빼 새 점화식을 만듭니다. 이때 차수를 늘릴지는 2L≤i라는 별도 조건으로 정해서, 불일치가 났다고 무조건 차수가 길어지지 않도록 합니다.

나눗셈(모듈러 역원)을 항상 할 수 있어야 알고리즘이 성립하기 때문입니다. 법이 소수가 아니면 0이 아닌 값끼리 곱해 0이 되는 경우가 생겨 역원이 없는 값이 나올 수 있습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.

알아두면 좋은 점

  • 피보나치(차수 2)·등비수열(차수 1)처럼 정답을 아는 수열의 앞 2L개만 넣어 정확한 차수와 계수가 나오는지 확인했습니다.
  • 무작위 계수로 차수 1~5짜리 점화식을 직접 만들고, 그 수열의 앞 2L개만 베를레캄프–매시에 넣어 원래 점화식(또는 그와 동등한 더 짧은 것)을 복원하는지, 복원한 점화식으로 수열 전체를 다시 만들면 원래 값과 정확히 일치하는지 검산했습니다.
  • 불일치 d가 0인 단계는 점화식이 바뀌지 않는지, 차수가 늘어나는 단계는 언제나 2L≤i 조건을 만족하는지 확인했습니다.
  • 이 계산기가 다루는 정수는 자바스크립트의 안전 정수 범위 안에서만 정확합니다. 법과 수열 값이 아주 크면(약 10^7 이상을 곱하는 경우) 오차가 날 수 있어 입력 범위를 제한합니다.

함께 보면 좋은 도구

피보나치 행렬 거듭제곱[[1,1],[1,0]]ⁿ을 분할정복으로 거듭제곱해 피보나치수를 O(log n)에 구합니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.2-SAT「둘 중 하나는 참」인 조건을 여럿 넣으면 참·거짓 배정이 가능한지 판정하고 배정을 하나 찾아 줍니다.2의 보수 변환N비트 폭에서 정수를 2의 보수 이진 표현으로 바꿔 줍니다.

마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.