 PDA

View Full Version : rsa Questions

tommychong
September 6th, 2005, 16:10
.i was wondering if it is not feasable to find the common denomanator whith 2 large pirmes

tommychong
September 6th, 2005, 20:14

dELTA
September 7th, 2005, 01:52
Are you trying to find a common denominator for two primes? The thing with primes is sorta that they don't have any denominators at all you know...

And if we're not talking primes, you should try LCD instead of GCD.

tommychong
September 7th, 2005, 04:40
thanks fella i guess i sound like a retard but yes the lowest common is what i need.say if i found away to turn every rsa modulo into 2 numbers and the LCD=Q. is it too hard to compute the LCD of say 600 byte numbers?it seems almost as hard to compute as factoring no?because if it cant be done i really dont wanna spend the time learning c++

dELTA
September 7th, 2005, 05:14
Yes, it should be equally hard (complexity-wise) to find the smallest factor and to factor it completely.

tommychong
September 7th, 2005, 16:08
yea i was reading on attacking rsa and in one of the attacks it said that sometimes if you can find the common dennomonator of the 2 modulo that you would break there system.But from what i can see it is not posible for me on my 2800 to find the lcd of 2 huge numbers

mike
September 14th, 2005, 17:12
I think you're confusing a few different things. There's

Greatest Common Divisor gcd(a,b), the largest number that is a factor of both a and b. When a and b are both primes, then gcd(a,b) = 1.

Least Common Multiple lcm(a,b), the smallest positive number that is divisble by both a and b. When a and b are primes, their least common multiple is a*b.

Lowest Common Denominator. This is really the same thing as lcm. When you are trying to add two fractions a/b and c/d by hand, one way to find the answer is (ad+bc)/bd, but this often leads to large denominators. One way to keep numbers small is to multiply through first with lcm(b,d) and then divide it out again.
Example:
First method: 1/6 + 1/9 = (1*9+1*6)/(6*9) = 15/54 = 5/18
LCM method: lcm(6,9)*(1/6 + 1/9) = 18/6 + 18/9 = 2+3 = 5 => 5/18

Both LCM and GCD are easy to compute given the product n=a*b of two primes.