Results 1 to 10 of 10

Thread: Data structure for big Integer

  1. #1
    jjhsd
    Guest

    Question Data structure for big Integer

    Hi,

    I plan to code a program to simulate RSA encryption. I am using JAVA but do not want to use the inbuilt Big Integer Class. Could anyone advise me how to store the large integer? (> 100 digits) and how to write the function which do the same as pwoerMod.

    thanks a lot!


    C
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  2. #2
    Artifex
    Guest
    If you change your mind and accept to use the BigInteger class (and its modPow(e,n) method) you may have a look to this web page :
    http://homex.coolconnect.com/member2/wailian/QuickStartRSA/

    Loading that page you will load a RSA.java file which you may read.

    I attached that page, another interesting java source (publickey.java) and a javascript implementation (rsajscript).

    Artifex
    Attached Files Attached Files
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  3. #3
    jjhsd
    Guest

    Post

    the problem is that using bigint class will lead java code that i've written can not immigrate to another language in the future, which doesn't have bigint class ready to use. (the code has to be rewritten.)
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  4. #4
    Artifex
    Guest
    After tasting Java for your simulation you won't want any other language !

    I can hardly understand why you want to use Java, and only a part of the Java language... but it's up to you.

    If you want to try to re-invent the wheel (I mean BigInteger methods), you will have to store your long integers in strings and write an addition and a substraction routine. With them you will be able to emulate modpow(e,n). I would understand it 25 years ago, but nowadays... ? In the midtime very smart guies worked for us.

    I prefer Java, but you could write your simulation in C and use Freelip or MIRACL libraries.

    Artifex
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  5. #5
    jjhsd
    Guest
    thank you for your reply. i think i can check Java's biginteger class for representing large numbers. but how about mod arithmetic? could you please kindly provide me an effective algorithm to compute mod?

    thanks in advance.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  6. #6
    Artifex
    Guest
    The Java BigInteger class has all methods to compute mod arithmetic.

    If you don't want to use them (!!!???) you will have to do the following :

    A power is a succession of multiplications
    a multiplication is a succession of additions
    a division (or a modulo) is a succession of substractions.

    You know that.

    So you store the big integers in strings.
    You extract each character (=figure) of the first string and add (or substract it) with the corresponding character (=figure) of the other string, and create a third string with your results.
    "123456789...........123456789"
    +
    "123456789...........123456789"
    ---------------------------------------
    ".........................................578"

    and so on... and so on...in a loop.

    Each compute is a one figure compute.
    It is up to you to choose to work in radix-10 or radix-2

    I keep it short because we are off topic.
    You could get better information on a programmation language forum.
    Good luck.

    Artifex
    Last edited by Artifex; September 4th, 2002 at 11:10.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  7. #7
    jjhsd
    Guest
    thanks for your help, i will try it!
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  8. #8
    Artifex
    Guest
    I attached a few lines of C. If you compile them you will be able to compute instantly a two big integers product. The method is not the addition method, but the way we multiply two numbers on a blackboard.

    Here are two runs :

    First big integer ?
    123456789123456789123456789
    Second big integer ?
    123456789123456789123456789
    gave the result :
    =15241578780673678546105778281054720515622620750190521
    or
    First big integer ?
    123456789123456789123456789123456789123456789123456789
    Second big integer ?
    123456789123456789123456789123456789123456789123456789
    gave the result :
    1524157878067367854610577831153787807696997784240207757735101981191892004648682028105472051562262075 0190521

    If it is not correct you may want to debug them !

    The division is a bit more tricky.

    Smart programmers spent months trying to improve their biginteger routines. With the way you decided to work you will spend more time testing your computation routines than yours rsa simulation ones !

    Enjoy yourself !

    Artifex
    Attached Files Attached Files
    Last edited by Artifex; September 6th, 2002 at 05:55.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  9. #9
    jjhsd
    Guest
    Thank you so much for your great help! I will check the attached source code.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  10. #10
    Artifex
    Guest
    I edited the source in order to make the draft a little bit clearer.

    Artifex
    I promise that I have read the FAQ and tried to use the Search to answer my question.

Similar Threads

  1. Replies: 3
    Last Post: April 19th, 2012, 05:37
  2. ms_exc structure.
    By calcite in forum The Newbie Forum
    Replies: 3
    Last Post: July 22nd, 2011, 10:52
  3. Integer overflow
    By OpenRCE_EliCZ in forum Blogs Forum
    Replies: 0
    Last Post: April 25th, 2008, 12:41
  4. Easy structure types
    By Hex Blog in forum Blogs Forum
    Replies: 0
    Last Post: February 18th, 2008, 15:10
  5. Negated structure offsets
    By Hex Blog in forum Blogs Forum
    Replies: 0
    Last Post: November 14th, 2007, 00:35

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •