# Thread: RNG and relative primes

1. ## 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

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. ## 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

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. ## random

Heya Goatass (: , Kythen where you been hiding? (:

6. ## 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

7. ## 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

#### Posting Permissions

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