Reputation
6,268
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
6 22 45
Impact
~326k 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.
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.