do I got any cryptography mutuals?
I'm puzzled about something with textbook RSA. Doesn't the message you encrypt need to be an integer that's coprime with N? So that it's in the multiplicative group? Seems like it would be a hassle to have a restriction on the messages
Conversation
Replying to
bearing in mind that idk how commercial software actually resolves this problem, N is the product of two large primes so this isn’t very likely to be a problem, on the off chance it is you can reroll the primes or salt the message
Replying to
do the products of two large primes not have that many numbers less than them that aren't coprime?
1
about 1 / p of all numbers are divisible by p and about 1 / q of all numbers are divisible by q. so at most 1 / p + 1 / q of all numbers are divisible by either (it's exactly 1 / p + 1 / q - 1 / pq but that last term is very small)
2
1
Show replies
This Tweet was deleted by the Tweet author. Learn more
lol, yeah you're right. Forgot how primes worked for a second
1