피사노 주기 알고리즘 - 팩토리얼 계산

피사노 주기 개요

• 피보나치 수열은 0과 1로 시작하며, 다음 항은 앞의 두 항의 합으로 이루어지는 수열입니다.
• 주어진 양의 정수 m에 대해, 피보나치 수열의 모듈로 m 연산 결과가 주기적으로 반복되는 최소 주기를 말합니다.

피사노 주기 예제

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610에 대한 모듈러 3으로 나눈 나머지는
• 0, 1, 1, 2, 0, 2, 2, 1 / 0, 1, 1, 2, 0, 2, 2, 1 로 8개의 단위로 주기를 가집니다.

피사노 주기 식

• 모듈러가 10^k 일때 주기는 15 * 10^(k -1)입니다.
• 주기 안에서 모듈러로 나눈 나머지는 어떤 주기안에서도 같습니다.

피사노 주기 알고리즘 동작 원리

• 모듈로 m에 대한 피보나치 수열을 생성합니다.
• 주기가 나타날 경우는 최대 m * m입니다.
• 이 수열에서 처음으로 0, 1이 나오는 위치를 찾습니다.

피사노 주기 코드 예시

function pisanoPeriod(m) {
 let prev = 0, current = 1, temp
 for(let i = 0; i < m * m; i++) {
  temp = (prev + current) % m
  prev = current
  current = temp
  
  if(prev === 0 && current === 1) return i + 1
 }
}

 

피사노 주기 활용

• 암호학
• 계산 기하학