무한강하법


1. 변수 p,A,B,M, u,v, r, a, b, imsi_a, imsi_b 를 마련 (p는 소수를 입력 받음, a와 b는 결과값 제곱수가 저장 됨.)


2. p=1 mod 4 인가? 맞으면 진행, 아니면 새로운 소수 입력 대기


3. A값 구하기 : x^2 = -1(mod p) 의 값


4. B = 1 대입 :


5. M값 구하기 (A^2 + B^2) / p


6. u,v값 구하기 : u = A mod M, v = B mod M

조건 : (-)M/2 <= u, v <= M/2 사이 일 것.


7. 좌,우변 일치 확인 : u^2 + v^2 == A^2 + B^2 == 0 mdod M , M으로 나뉘어 떨어지는지 확인.


8. r구하기 : (u^2 + v^2) / M = r , 조건 (1 <=  r < M )


9 두 개의 식을 비교


(u^2 + v^2) * (A^2 + B^2) == M^2 * r * p 는 같은가?


10 imsi_a, imsi_b를 구함 : imsi_a = (u*A + v*B) , imsi_b = (v*A - u*B)


11 a, b를 구한다 : a = imsi_a / M, imsi_b /M


12. 검산 a^2 + b^2 = p * r


13. r이 1이 아니면


M = r

A = a

B = b  대입 후,  6번으로 가서 반복


14. r이 1이면 a, b가 제곱수



실행결과

p = 881


a=25

b=16


881 = 25^2 + 16^2


두 개의 제곱수로 나뉘어 짐.