Fixee
Reputation
6,328
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
6 24 45
Newest
Impact
~345k people reached

• 0 helpful flags
• 1,343 votes cast

# 203 Comments

 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. 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 comment Instantly Factor a Semiprime of Any Size? Primality testing is a much much easier problem than factoring. 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. 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 2 comment proof by contradiction puzzle Isn't this just en.wikipedia.org/wiki/Chomp ? Jun 10 comment What is the worst-case running time of this algorithm? @Henry That's a good suggestion. Or "unbounded" even. Feb 5 comment Problem about combinations and permutations The first customer has 14 choices, the next 13, and the last 12. It's 14P3, not 14C3. Oct 14 comment $\gcd(p, (p-1)!) = 1$? Wilson's theorem settles this in 1 step: en.wikipedia.org/wiki/Wilson's_theorem Jul 15 comment Finding rational points at rational distance in the plane @QiaochuYuan: Take $p$ to be $(1/\pi, \sqrt{1-1/\pi^2})$. Aren't both coordinates transcendental? And isn't $p$ unit distance from the origin? Aug 5 comment Expected length of a sequence that contains all words of a given length. @ByronSchmuland I think that's the same ref leonbloy cited at the end of his answer below. Aug 4 comment N white and black balls and N boxes Probability Given $N$ new users posting $N$ new questions which are worded as demands rather than questions, what is the probability they are all homework problems? Jun 29 comment Fibonacci sequence - how to prove $a_n=\frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$ without induction This is given as a warmup in the free text by Wilf called generatingfunctionology. Jun 28 comment How to find generator in a finite group?what is generator? When I said, "suppose you can factor" the "you" is the OP who is (presumably) a human trying to solve a problem. I did not (and would not) say "suppose a factorization exists for $(p-1)$". Jun 24 comment practical arithmetic in prime factorizations Ross, I don't get your answer. You seem to be reiterating his idea rather than answering his question regarding the use of this technique in actual software. Jun 15 comment How to show that $\sum\limits_{k=1}^{n-1}\frac{k!k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$? @PeterR: Often mathematicians will use "elementary" to mean "does not use complex analysis". As you can see, "elementary" does not mean "easy." Jun 15 comment The sum $\sum\limits_{n \ge 0} \binom{m-1}{n} \frac{n!}{m^n} + \binom{n+1}{2}\binom{m-1}{n-1}\frac{(n-1)!}{m^n}$ is asymptotic to $\sqrt{9πm/8}$ Interesting. This immediately gives that three collisions occur in less than an expected $2 \sqrt{\pi m/2} = \sqrt{2\pi m}$. (In fact, I will guess that it's $15/8 \sqrt{\pi m/2}$.) Since $\sqrt{2\pi m}$ is the square root of the circumference of a circle of radius $m$, there is clearly a geometric proof we're missing. :) Jun 15 comment How many even number in a sequence are there? Your iff is false in both directions.