의사 코드 (NTRUEncrypt)에서 재귀 구현

Question

최종 프로젝트 인 University Project의 일부로 NTRU 공개 키 시스템을 구현해야합니다. 재귀를 통해 긴 다항식을 곱하는 알고리즘을 구현하려고하지만 의사 코드를 이해하려고 노력하는 데 꽤 어려움이 있습니다.

Algorithm PolyMult(c, b, a, n, N) 
Require: N, n, and the polynomial operands, b and c. 
PolyMult returns the product polynomial a through the argument list 
PolyMult(a,b,c,n,N) 
{ 
1. if(...) 
2. { 
3. ... 
4. ... 
5. ... 
6. ... 
7. } 
8. else 
9. { 
10. n1 = n/2; 
11. n2 = n-n1; 
12. b = b1+b2*X^(n1); 
13. c = c1+c2*X^(n1); 
14. B = b1+b2; 
15. C = c1+c2; 
16. PolyMult(a1,b1,c1,n1,N);// a1 = b1*c1 
17. PolyMult(a2,b2,c2,n2,N);// a2=b2*c2 
18. PolyMult(a3,B,C,n2,N);// a3 = B*C=(b1+b2)*(c1+c2) 
19. a = a1 + (a3-a1-a2)*X^(n1) + a2*X^(2*n1); 
20.} 
} 

N, n, n1 및 n2는 모두 int 유형입니다. a1, a2, b, b1, b2, c, c1, c2, B, C는 모두 다항식이며 배열로 표시됩니다.

16, 17, 18 행에서 a1, b1, c1, n1, N 다음 a2, b2, c2, n2, N 및 마지막으로 a3, B, C, n2, N의 인수로 PolyMult 함수를 호출합니다. 각기. 나는 16 번째 줄에 배열 a1, b1, c1을 초기화했다. 그런 다음 PolyMult 자체 (재귀가 여기에서 시작된다!)로 전달하고 대답을 반환하고 임시 배열에 저장한다. 예를 들어 다음과 같이 16 행을 구현한다.

int z[] = PolyMult(a1,b1,c1,n1,N); 

지금 내 질문은 : 다항식 어레이 Z []를 프로그램에 다시 사용에 저장된 때, I는 상기 의사 코드에서 다시 사용되는 것이라는 표시를 볼 수 없지만, 만약 어레이 Z []는 프로그램에서 다시 사용되지 않습니다. 16 번 줄과 재귀가 모두 함께 무엇입니까? 16-18 행을 어떻게 구현해야합니까?

따라서 반복 할 때 배열 z에 저장된 다항식은 언제 프로그램에서 다시 사용됩니까? 그리고 16-18 행을 어떻게 구현해야합니까?

의사 코드에 대한 자세한 내용은이 기사의 3 페이지에있는 http://www.ntru.com/cryptolab/pdf/NTRUTech010.pdf에서 확인할 수 있습니다.

Answer 1

의사 코드에서 결과는 매개 변수로 제공된 a[] 배열에 저장하여 "반환"됩니다. PolyMult(a1, b1, c1, n1, N)은 그 결과를 a1[]에 저장합니다.

그 곱셈 기법은 단순히 다항식에 적용되는 Karatsuba 곱셈입니다 (다항식에 캐리가 없으므로 더 쉽게 만듭니다). 포인터는 this Wikipedia article을 참조하십시오.

개인적으로는 의사 코드를 따르는 것이 아니라 수학적으로 이해하는 것이 더 쉽다고 생각합니다.

Answer 2

저는 NTRU에서 일하기 때문에이 관심사를 보게되어 기쁩니다.

어떤 매개 변수가 사용 중인지 잘 모르겠지만 많은 NTRU 매개 변수 세트에 대해 Karatsuba를 구현하는 데 소요되는 오버 헤드는 가치가 없다는 것을 알 수 있습니다. A와 B를 곱하고 있다고 가정 해보십시오. NTRUEncrypt 컨볼 루션 연산의 경우 관련된 다항식 중 하나는 항상 2 진수 또는 3 진수입니다. 그 대답은 다음과 같습니다. 결과의 각 계수는 의 계수 B의 계수의 합계입니다. A를 1의 배열로 저장하는 대신 0이 아닌 계수의 인덱스 배열로 저장하면 0이고 A가 너무 조밀하지 않으면 Karatsuba보다 인덱스 배열을 통해 작업하는 것이 더 빠릅니다. 코드는 작고 단순합니다.

내가 공부하는 대학을 물어볼 수 있습니까?