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

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
}

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

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.

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

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

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