현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

모듈러 연산기를 구현하려고 합니다.

shs0917의 이미지
글쓴이: shs0917 / 작성시간: 월, 2004/11/15 - 4:20오후

그냥 일반적인 나눗셈의 나머지를 구하는건 어렵지 않을거 같습니다만..
128bit 정도의 크기를 가지는 정수에 대한 모듈러 연산을 하려니까 많이
난감하네요.. 128bit의 정수를 표현할 수 있는 효율적인 방법이 없을까요?
물론 연산이 가능한 형태로 표현을 해야겠죠..^^
검색을 해봐도 큰 수를 다루는 문제는 잘 안보이는거 같아서요..

Forums: 
프로그래밍 QnA
IsExist의 이미지

글쓴이: IsExist / 작성시간: 월, 2004/11/15 - 4:53오후

BIGNUM 관련으로 해서 검색해 보세요.

openssl 도 BIGNUM을 자체로 구현해 놓았고
GNU 쪽에서도 Math Library 로 Bignum을 구현해 놓은것도 있습니다.

---------
간디가 말한 우리를 파괴시키는 7가지 요소

첫째, 노동 없는 부(富)/둘째, 양심 없는 쾌락
셋째, 인격 없는 지! 식/넷째, 윤리 없는 비지니스

이익추구를 위해서라면..

다섯째, 인성(人性)없는 과학
여섯째, 희생 없는 종교/일곱째, 신념 없는 정치

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/11/15 - 10:16오후

아... 답변 감사합니다.. 큰수를 계산한다는게 말은 쉬운데.. 실천은 어렵네요..^^;;

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

송효진의 이미지

글쓴이: 송효진 / 작성시간: 월, 2004/11/15 - 10:28오후

라이브러리가 있습니다.
http://www.swox.com/gmp/

php와 연동도 되고요.
http://kr.php.net/manual/en/ref.gmp.php

<?php
function fact($x)
{
   if ($x <= 1) {
       return 1;
   } else {
       return gmp_mul($x, fact($x-1));
   }
}

echo gmp_strval(fact(1000)) . "\n";
?>

결과

4023872600770937735437024339230039857193748642107146325437999104299385123986
2902059204420848696940480047998861019719605863166687299480855890132382966994
4590997424504087073759918823627727188732519779505950995276120874975462497043
6014182780946464962910563938874378864873371191810458257836478499770124766328
8983595573543251318532395846307555740911426241747434934755342864657661166779
7396668820291207379143853719588249808126867838374559731746136085379534524221
5865932019280908782973084313928444032812315586110369768013573042161687476096
7587134831202547858932076716913244842623613141250878020800026168315102734182
7977704784635868170164365024153691398281264810213092761244896359928705114964
9754199093422215668325720808213331861168115536158365469840467089756029009505
3761647584772842188967964624494516076535340819890138544248798495995331910172
3355556602139450399736280750137837615307127761926849034352625200015888535147
3316117021039681759215109077880193931781141945452572238655414610628921879602
2383897147608850627686296714667469756291123408243920816015378088989396451826
3243671616762179168909779911903754031274622289988005195444414282012187361745
9926429565817466283029555702990243241531816172104658320367869061172601587835
2075151628422554026517048330422614397428693306169089796848259012545832716822
6458066526769958652682272807075781391858178889652208164348344825993266043367
6601769996128318607883861502794659551311565520360939881806121385586003014356
9452722420634463179746059468257310379008402443243846565724501440282188525247
0935190620929023136493273497565513958720559654228749774011413346962715422845
8623773875382304838656889764619273838149001407673104466402598994902222217659
0433990188601856652648506179970235619389701786004081188972991831102117122984
5901641921068884387121855646124960798722908519296819372388642614839657382291
1231250241866493531439701374285319266498753372189406942814341185201580141233
4482801505139969429015348307764456909907315243327828826986460278986432113908
3506217095002597389863554277196742822248757586765752344220207573630569498825
0879689281627538488633969099598262809561214509948717012445164612603790293091
2088908694202851064018215439945715680594187274899809425474217358240106367740
4595741785160829230135358081840096996372524230560855903700624271243416909004
1536901059339838357779394109700277534720000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000

https://xenosi.de/

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/11/15 - 11:38오후

코드는 아마도 라이브러리 이용한 예제인가봐요?? fact()함수가 뭘 하는건지는 모르겠지만.. 결과값은 엄청난 숫자를 출력하네요..^^ 아.. 팩토리알 구하는 거군요..^^;; 링크 사이트에 적혀 있군요..ㅎㅎ 감사합니다. 라이브러리를 단순히 사용하는건 공부에 도움이 안될듯 하구요.. 제가 암호학쪽에 관심이 있어서요..큰 수에 대한 연산은 필수적인 기본기라고 생각하고 직접 구현해보고 싶은거죠..^^ 저 라이브러리도 분석해보면 도움이 되겠죠? ^^

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

cdpark의 이미지

글쓴이: cdpark / 작성시간: 월, 2004/11/15 - 11:43오후

shs0917 wrote:
코드는 아마도 라이브러리 이용한 예제인가봐요?? fact()함수가 뭘 하는건지는 모르겠지만.. 결과값은 엄청난 숫자를 출력하네요..^^ 아.. 팩토리알 구하는 거군요..^^;; 링크 사이트에 적혀 있군요..ㅎㅎ 감사합니다. 라이브러리를 단순히 사용하는건 공부에 도움이 안될듯 하구요.. 제가 암호학쪽에 관심이 있어서요..큰 수에 대한 연산은 필수적인 기본기라고 생각하고 직접 구현해보고 싶은거죠..^^ 저 라이브러리도 분석해보면 도움이 되겠죠? ^^

암호학에 필요한 a^k mod N 류를 계산하는 알고리즘은 따로 있습니다.
가장 널리 쓰이는게 Montgomery 알고리즘이죠. 이걸 상황에 맞게 적당히 최적화해서 씁니다. 자세한 내용은 google을 참조하시고요.

shs0917의 이미지

글쓴이: shs0917 / 작성시간: 월, 2004/11/15 - 11:55오후

너무 노력도 안해보고 질문을 올리는거 같아서 조금 걱정스럽기도 하고 죄송스럽기도 했는데... 이렇게 답변을 달아주셔서 너무너무 감사하네요.. 알고리즘 자체는 계산에 대한 문제이고 입출력 데이터로서 큰 수를 다루는건 다른 방향에서 봐야 하는거라고 생각했는데.. 제 생각이 틀렸나봐요?? 이런저런 논문 찾아보니까 효율적인 모듈러 연산기를 구현하기 위한 방법들이 정말로 많더군요..^^

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.