Reputation
6,268
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
6 22 45
Impact
~327k people reached

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?
Jun
10
comment What is the worst-case running time of this algorithm?
@Henry That's a good suggestion. Or "unbounded" even.
Jun
10
asked What is the worst-case running time of this algorithm?