Results 1 to 7 of 7

Thread: RNG and relative primes

  1. #1
    goatass
    Guest

    RNG and relative primes

    How do I check if a number I generated is relatively prime to another number? I'm using the mircle library for the big number functions.

    Thanks,

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

  2. #2
    You check to see if Greatest Common Divisor (GCD) for the two numbers is 1.

    ie. z = GCD(x,y)
    if z equals 1 then you have relatively prime numbers


    In MIRACL this would be:

    egcd(x, y, z);
    if(z == 1)
    {
    // the numbers are relatively prime
    }

  3. #3
    goatass
    Guest

    RNG

    Kythen my friend how are you?

    Here is what I got for code:

    sz1=mirvar(1);

    decr(p,1,p);

    do {
    bigrand(p,k);
    egcd(k,p,y2);
    } while ( (compare(y2,sz1))!=0 );

    incr(p,1,p);

    The problem I have with this is that I get a small number from the RNG that when I do these ElGamal calulations:

    // x3=M-x2
    subtract(m2,x2,x3);
    divide(x3,p2,x2);

    on it I get a negative number and this screws up the rest of the claculations.

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

  4. #4
    Doing quite well here, just finishing up the barrage of exams/projects/papers/God-only-knows-what-else that comes with semester's end.

    And from what I can see, your problem has a very simple solution...

    do
    {
    do
    {
    bigrand(p,k);
    }while(k < SOME_LIMIT);
    egcd(k,p,y2);
    } while ( (compare(y2,sz1))!=0 );

    Just keep repeating the bigrand call until you get a number that's both big enough and is relatively prime to p.

    You may want to check some of your other calculations though, as the size of the random number k should not matter unless it's something like 1.

  5. #5
    Sab`
    Guest

    random

    Heya Goatass (: , Kythen where you been hiding? (:
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  6. #6
    goatass
    Guest

    rng

    Kythen, I think I might have some other issues with my calculations I'll check it out again.

    Good luck on all your exams and stuff, I'm so glad I'm done with school eventhough social life blows now it still feels good not to have exams and papers.

    Sab my friend how are you, long time no talk, how you been? how's life been treaing you?

    I love this board it brings together all these great friends

    talk to you later

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

  7. #7
    goatass
    Guest

    rng

    Hey ArthaXerXes, I'm haven't looked too deeply into how thier PRNG works but from the docs I can tell you that it uses the IRAND function which like you said gets a psuedo random long number and uses it as the seed to the main PRNG fucntion.
    All of the none-cryptographically secure RNG routines in the miracl library use the IRAND function so they are not very strong but they do say so in the docs. The strong_rng function suppose to be the cryptographically secure PRNG function. I haven't looked at all how it works so I can't give you any details on it.

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

Similar Threads

  1. Replies: 0
    Last Post: July 14th, 2009, 22:22
  2. ElGamal with non relative prime k to p-1 ?
    By scarebyte in forum RCE Cryptographics
    Replies: 5
    Last Post: December 30th, 2008, 06:57
  3. RSA - More than 2 primes
    By jandis in forum RCE Cryptographics
    Replies: 1
    Last Post: August 20th, 2004, 02:53
  4. recover RSA primes p and q if we have n,d,e
    By Solomon in forum RCE Cryptographics
    Replies: 8
    Last Post: October 2nd, 2003, 13:20

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
  •