jwpat7
Reputation
515
Top tag
Next privilege 1,000 Rep.
Create tags
 Sep10 asked Conditions on polygon to ensure equal interior angles or opposite sides Aug24 revised Error measurement between given perfect 2D shape and freeform shape drawn by user rev'd last paragraph WRT normalizing Aug24 answered Error measurement between given perfect 2D shape and freeform shape drawn by user Aug22 comment Number of $k^p \bmod q$ classes when $q\%p > 1$ @awllower, the "q%p>1" part of the title was used as shorthand for "q != 1 mod p". The "number of classes" part refers to the number of equivalence classes, mod q, of k^p. How would you phrase it? Aug22 comment Number of $k^p \bmod q$ classes when $q\%p > 1$ thanks for the answer, @awllower. I agree with what you say, except that the theorem's last assertion is stronger than what I wanted to show -- it also characterizes the number of classes when q == 1 mod p. For my purposes (given p, finding q so that k^p falls into q-1 classes, so that computed numbers can quickly/efficiently be recognized as probable p'th powers) I don't care about that case, although other people could very well care about it. Aug15 revised Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? change wrong-refs of n to u Aug15 comment Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? @Charles, you are right, I apologize for that. I'm now going to edit the "n=#bits" references in my answer to "u=#bits" to reduce longer-term confusion. Aug15 comment Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? Perhaps you wrote $n$ rather than $p$ in the above. $p$ is the prime being factored, $n$ is the number of bits in its binary representation. But your point is correct -- $O(1)$ is too pessimistic. If we suppose a modern method is $O(p^{1/3})$ and solve $p^{1/3} = 3^k$, we get $k\approx n\cdot{\ln2\over3\ln3}\approx0.21n$; so brute force is competitive for these numbers if no more than 42% of the bits change places. Aug15 awarded Teacher Aug15 revised Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? corrected solve for k at end Aug15 answered Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? Aug14 comment Winning on Prize Bonds @francis, the "squiggly equals" stands for approximately equal. The "upside down y" is a greek lambda, as commonly used for the parameter of a Poisson distribution. Re Binomial distribution and approximations to it, the Wikipedia page I linked to explains in detail; briefly, a Binomial dist. expresses the probability of getting k out of n flips to come up heads, with a given probability p for a head. Re "probability of success on one draw", I approximated a binomial by a geometric-probability ratio; the other answers don't make that approximation. Aug13 revised Winning on Prize Bonds Added update 1. Aug13 revised Winning on Prize Bonds added 283 characters in body Aug13 answered Winning on Prize Bonds Aug13 awarded Supporter Aug13 awarded Scholar Aug13 accepted Number of $k^p \bmod q$ classes when $q\%p > 1$ Aug13 comment Number of $k^p \bmod q$ classes when $q\%p > 1$ @Jyrki, I'd like to think I was conversant with the techniques you mentioned, when I took number theory classes long ago. However, I've forgotten quite a lot. The straightforward and basic techniques of André's answer are more helpful to me, while I expect practicing mathematicians will prefer the conciseness of your hints. Aug13 awarded Editor