yuchi's Development Home
글 수 694
마이크로 프로세서 과목 프로젝트 4번을 끝냈다.
휴..힘들었다.
2048비트짜리 수를 입력받아 A*B mod N을 구하는게 a번.
2048비트짜리 수를 입력받아 A^x mod N을 구하는게 b번.
A^32승만해도 엄청난 수가 나온다.2의 32승이 42억쯤 된다.그런데 2048승도 아니고 2048비트짜리 숫자이다. 2048비트짜리 숫자의 최대값이 얼마가 될까?10진수로 풀어쓰면 책상 한칸 정도는 늘어질거다. A를 그 무지막지한 숫자만큼 제곱한다고 하면? 이건 애초에 산수계산으로는 불가능한 연산이다.
당연히...알고리즘이 있고 그 알고리즘을 이용해서 내부적으로 2진 연산을 해야한다.
상당히 흥미있는 화두지만 난 회사일이 바쁘고 굳이 해야할 필요를 못느꼈다.게다가 교수가 최하점수가 C라고 공언한터라 안하고 버틸 생각이었다.
어차피 난 학점에 목매지 않았으니까...
프로젝트 1,2번은 어차피 C코드였으니까 즐기는 셈 치고 했다.
근데 2번에서 내 코드가 꽤 느리다는 사실을 알았다. 다른 학생들은 어떻게 햇는지 모르겠는데 그 당시 난 나름대로 융통성 있게 짠답시고 1비트당 1바이트씩 사용했다.2048비트면 2048바이트 배열 잡은것이다.
덕택에 오버헤드가 엄청났다. 돌아는 가는데 2048비트짜리 A^x mod N을 계산하면 펜티엄4 1.8기가 기준으로 5분정도 걸렸다.
난 다 그 정도 걸리는 줄 알았는데 훨씬 빠르게 짠 놈들도 있었던 모양이다.
상당히 자존심이 상했다. 게다가 교수가 너무 열성적으로 가르치는 통에 도저히 부담이 되어서 안하고 넘어갈 수가 없었다.
그래서 이틀을 투자해서 매달렸다.
내 그 좋아하는 어셈블리임에도 불구하고 워낙에 데이타 확인하기가 힘든지라 하루웬종일 디버깅하느라 미치는줄 알았다.
그렇게 이틀만에 결과를 보게 됐다.
32비트씩 처리하도록 새로 짠 덕분에 속도는 비약적으로 향상되었다.
펜4에서 5분 걸리던것이 내 펜티엄3 866에서 36초 걸렸다.
간만에 머리 잘 굴리고 자신감을 얻어서 매우 기분이 좋다.
들들 볶으면서도 배울거리를 하나씩 던져주는 교수한테 약간 고맙기도 하고...
아 뿌듯하여라...
휴..힘들었다.
2048비트짜리 수를 입력받아 A*B mod N을 구하는게 a번.
2048비트짜리 수를 입력받아 A^x mod N을 구하는게 b번.
A^32승만해도 엄청난 수가 나온다.2의 32승이 42억쯤 된다.그런데 2048승도 아니고 2048비트짜리 숫자이다. 2048비트짜리 숫자의 최대값이 얼마가 될까?10진수로 풀어쓰면 책상 한칸 정도는 늘어질거다. A를 그 무지막지한 숫자만큼 제곱한다고 하면? 이건 애초에 산수계산으로는 불가능한 연산이다.
당연히...알고리즘이 있고 그 알고리즘을 이용해서 내부적으로 2진 연산을 해야한다.
상당히 흥미있는 화두지만 난 회사일이 바쁘고 굳이 해야할 필요를 못느꼈다.게다가 교수가 최하점수가 C라고 공언한터라 안하고 버틸 생각이었다.
어차피 난 학점에 목매지 않았으니까...
프로젝트 1,2번은 어차피 C코드였으니까 즐기는 셈 치고 했다.
근데 2번에서 내 코드가 꽤 느리다는 사실을 알았다. 다른 학생들은 어떻게 햇는지 모르겠는데 그 당시 난 나름대로 융통성 있게 짠답시고 1비트당 1바이트씩 사용했다.2048비트면 2048바이트 배열 잡은것이다.
덕택에 오버헤드가 엄청났다. 돌아는 가는데 2048비트짜리 A^x mod N을 계산하면 펜티엄4 1.8기가 기준으로 5분정도 걸렸다.
난 다 그 정도 걸리는 줄 알았는데 훨씬 빠르게 짠 놈들도 있었던 모양이다.
상당히 자존심이 상했다. 게다가 교수가 너무 열성적으로 가르치는 통에 도저히 부담이 되어서 안하고 넘어갈 수가 없었다.
그래서 이틀을 투자해서 매달렸다.
내 그 좋아하는 어셈블리임에도 불구하고 워낙에 데이타 확인하기가 힘든지라 하루웬종일 디버깅하느라 미치는줄 알았다.
그렇게 이틀만에 결과를 보게 됐다.
32비트씩 처리하도록 새로 짠 덕분에 속도는 비약적으로 향상되었다.
펜4에서 5분 걸리던것이 내 펜티엄3 866에서 36초 걸렸다.
간만에 머리 잘 굴리고 자신감을 얻어서 매우 기분이 좋다.
들들 볶으면서도 배울거리를 하나씩 던져주는 교수한테 약간 고맙기도 하고...
아 뿌듯하여라...
