Fixee
Reputation
6,343
Top tag
Next privilege 10,000 Rep.
Access moderator tools
 Feb 27 awarded Favorite Question Feb 16 awarded Yearling Nov 8 comment Equation for largest text-block size mod n in RSA encryption @HenningMakholm Most proofs I have seen in textbooks and in all classes I've taught and in every class I've taken where RSA is presented prove that RSA works in $Z^*_n$. Such a proof necessarily requires that messages belong to that group, which precludes multiples of $p$ and $q$. This condition is fine from a practical standpoint because (as I pointed out) running across a message not coprime to $p$ or $q$ is as hard as factoring $n$. And even if this happened (as I pointed out) RSA still works. All of this was in my original answer, so I'm not sure what the point of your comments is. Nov 7 comment Equation for largest text-block size mod n in RSA encryption @HenningMakholm "should be" is different to "must be." I said "should be" because otherwise the standard proof fails and you have to use a more involved argument (as you have done in your comment). I noted in my answer that RSA still works even without this condition. You seem to be agreeing. Nov 7 answered Equation for largest text-block size mod n in RSA encryption Oct 11 awarded Popular Question Sep 7 answered The last/largest semi-prime of the form $16^n+1$? Sep 7 revised The last/largest semi-prime of the form $16^n+1$? improve accuracy Sep 7 revised The last/largest semi-prime of the form $16^n+1$? Corrected typo Sep 7 comment The last/largest semi-prime of the form $16^n+1$? Why does anyone care who Mr Norata is? It's just a math question. Sep 7 revised The last/largest semi-prime of the form $16^n+1$? Missed 89 in the list Sep 7 comment Instantly Factor a Semiprime of Any Size? Primality testing is a much much easier problem than factoring. Aug 17 revised calculate $a/b\ mod\ p$ where p is a prime and a,b can be very large deleted 48 characters in body Aug 17 comment calculate $a/b\ mod\ p$ where p is a prime and a,b can be very large Yes, use the max power of $p$ that divides both numerator and denominator. This max power can be found quickly with binary search. Aug 15 answered calculate $a/b\ mod\ p$ where p is a prime and a,b can be very large Jul 14 comment What is the last digit of $\pi$? @SimonS The best way to answer that question would be a web search. My research area is cryptography, so it's too far afield for me to have anything but recreational interest, but a lot of very interesting math isn't that well-used. It doesn't mean it's not cool or fun to think about. For example, here's a question: we know that $\pi$ is irrational in base 10; is 10 irrational in base $\pi$? Jul 14 comment What is the last digit of $\pi$? @SimonS I think I did above: $\pi = 10_\pi$. Irrational bases do lead to weird results, but I'm not the first one to suggest them. I first encountered the idea of irrational (and transcendental) bases in Knuth's 2nd book, but the idea predates even that: mathworld.wolfram.com/Base.html Jul 6 revised Expected value when die is rolled $N$ times typography Jul 2 comment proof by contradiction puzzle Isn't this just en.wikipedia.org/wiki/Chomp ? Jun 29 answered How many edges in a graph with $n$ vertices are needed to guarantee it is connected?