1 |
1
상수배 연산을 수행하는 상수 m을 축소하여 프로비니어스 맵 전개시 항의 수가 적은 X+Yα를 구하는 축소 절차와, 상기 축소 절차에서 구한 X+Yα를 입력으로 하여 전개식의 계수의 크기가 유한체의 위수 q 미만이 되면서 총 항의 개수가 logqm+3 이하가 되도록 하여 프로비니어스 맵 전개를 모든 q에 대해 이용할 수 있게 하는 프로비니어스 맵에 의한 전개 절차와, 상기 프로비니어스 맵에 의한 전개 절차에서 구한 전개식을 이용하여 곡선 위의 임의의 점을 직접 m배 연산하는 상수배 연산 절차를 포함하여 이루어지는 것을 특징으로 하는 프로비니어스 맵을 이용한 타원 곡선 위의 상수배 연산 방법
|
2 |
2
제 1 항에 있어서, 상기 축소 절차는 유한체의 위수 q, 정수 m, 타원 곡선군 E(GF(q))의 위수 N1과 타원 곡선군 E(GF(qn))의 위수 Nn을 입력받는 단계와, 상기 타원 곡선 E(GF(q))를 고정하고 E(GF(q))의 위수 N1에서 q+1을 뺀 수를 t, 정수 방정식 x2-tx+q=0의 한 근을 α라 하고 D를 [수학식 1]로 설정하는 단계와, 상기 정수 방정식의 한 근인 α를 [수학식 2]를 이용하여 구하는 단계와, [수학식 3]을 계산하여 계산 결과의 실수 부분을 a, 허수 부분을 b로 설정하는 단계와, 상기 [수학식 3]의 결과로부터 얻은 a 및 b를 이용하여, a-tb/D를 반올림하여 x라 놓고 2b/D를 반올림하여 y라 설정하는 단계와, 상기 x 및 y를 이용하여 X=m+x, Y=yαn+xαn-1-y를 출력하는 단계를 포함하여 이루어지는 것을 특징으로 하는 프로비니어스 맵을 이용한 타원 곡선 위의 상수배 연산 방법
|
3 |
3
제 1 항에 있어서, 상기 프로비니어스 맵에 의한 전개 절차는 상기 축소 절차에서 얻어진 정수 X, Y, 유한체의 위수 q, E(GF(q))의 위수 N1에서 q+1을 뺀 수 t를 입력받는 단계와, k를 0으로 설정하고 정수 X를 유한체의 위수 q로 나눈 나머지를 u로 설정하는 단계와, 상기 u가 0이거나 2X+tY가 2u-q보다 크거나 같은지 검사하는 단계와, 상기 u가 0이거나 2X+tY가 2u-q보다 크거나 같은지 검사한 결과 상기 u가 0이거나 2X+tY가 2u-q보다 크거나 같을 경우에는 (X,Y)를 (t(X-u)/q+Y, -(X-u)/q)로, u를 u-q로 치환하고 c(k)를 u로 설정하는 단계와, 상기 u가 0이거나 2X+tY가 2u-q보다 크거나 같은지 검사한 결과 u는 0이 아니고 2X+tY가 2u-q보다 작은 경우에는 (X,Y)를 (t(X-u)/q+Y+t, -(X-u)/q-1)로 치환하는 단계와, 상기 X와 Y 모두 0인지 검사하는 단계와, 상기 X와 Y 모두 0인지 검사한 결과 X와 Y가 동시에 모두 0이 아닌 경우에는 k의 값을 1 증가시키고 u를 계산하는 단계로 진행하는 단계와, 상기 상기 X와 Y 모두 0인지 검사한 결과 X와 Y가 동시에 모두 0인 경우에는 k값 및 c(0), c(1), c(2),
|
4 |
4
제 1 항에 있어서, 상기 상수배 연산 절차는 정수 r, 상기 프로비니어스 맵에 의한 전개 절차로 얻어진 k, c(0), c(1), c(2),
|