most recent 30 from http://mathoverflow.net 2013-05-19T00:24:44Z http://mathoverflow.net/feeds/user/4757 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62100/is-there-a-good-known-algorithm-for-generating-sets-of-monomials-alternatively/62103#62103 AVS 2011-04-18T09:12:42Z 2011-04-18T11:59:51Z

<p>See Chapter 7.2.1.4 of Knuth "The Art of Computer Programming" Vol. 4 Fascicle 3. On page 38 he gives algorithms to efficiently enumerate all partitions of an integer $n$ (see Algorithm P), or to enumerate all partitions of $n$ into exactly $m$ parts (see Algorithm H). Running Algorithm H repeatedly with $m$ varying from 1 to $r$ should solve your problem in essentially optimal time (i.e. within a constant factor of the size of the output).</p>

http://mathoverflow.net/questions/57548/second-stage-of-elliptic-curve-factorization-via-random-walk-pollards-rho-in-con/57565#57565 AVS 2011-03-06T13:24:10Z 2011-03-06T19:06:36Z

<p>Brent's paper <em><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.126.5687" rel="nofollow">Some integer factorization algorithms using elliptic curves</a></em> describes a "birthday paradox" ECM extension based on a random walk that only uses $O(\sqrt{r})$ group operations on the elliptic curve (see Section 6), however it is not space efficient. Cycle detection techniques do not apply because the iteration function used is not a deterministic operation on the elliptic curve modulo any of the (unknown) prime factors of $n$, and it is not clear how one might construct such a function.</p> <p>One can apply the usual Pollard-$\rho$ approach to computations on the elliptic curve performed mod $n$, say using an iteration function where $Q_{i+1}$ is $2Q_i$ or $2Q_i+Q$, depending on the parity of the $x$-coordinate of $Q_i$ when viewed as an integer in $[0,n-1]$. This will eventually lead to a cycle, which can be recognized using standard techniques (e.g. Floyd's algorithm) with a space complexity of $O(\log n)$ bits. But the expected length of this cycle (assuming this iteration function actually approximates a random walk) is $O(\sqrt{m})$, where $m$ is the order of $P$ on $E(\mathbb{Z}/n\mathbb{Z})$, not $O(\sqrt{r})$.</p>

http://mathoverflow.net/questions/14054/where-can-i-find-a-comprehensive-list-of-equations-for-small-genus-modular-curves/18812#18812 AVS 2010-03-20T01:05:11Z 2010-12-20T17:02:43Z

<p>Explicit equations for X_1(N) that have been optimized to reduce both the degree and coefficient sizes are available for N &lt;= 50 at <a href="http://math.mit.edu/~drew/X1_curves.txt" rel="nofollow">http://math.mit.edu/~drew/X1_curves.txt</a>. These were obtained using the algorithm described in <a href="http://arxiv.org/abs/0811.0296" rel="nofollow">http://arxiv.org/abs/0811.0296</a>.</p> <p><strong>EDIT</strong>: Tables of defining equations for X_1(N) for N &lt;= 189 are now available at <a href="http://www-math.mit.edu/~drew/X1_altcurves.html" rel="nofollow">http://www-math.mit.edu/~drew/X1_altcurves.html</a></p>

http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41004#41004 AVS 2010-10-04T10:07:35Z 2010-10-04T16:28:53Z

<p>The fast Euclidean algorithm runs in time $O(M(n)\log n)$, where $n=\log q,$ and $M(n)$ is the time to multiply two $n$-bit integers. This yields a bit-complexity of $$ O(n\log^2 n\log\log n) $$ for the time to compute the inverse of an integer modulo $q$, using the standard Schonhage-Strassen algorithm for multiplying integers (a slightly better asymptotic result can be obtained using Furer's multiplication algorithm).</p> <p>To understand the basic idea behind the fast Euclidean algorithm, recall that the standard Euclidean algorithm computes the (extended) gcd of two integers $r_0 > r_1$ by successively computing $m_i=\lfloor r_{i-1}/r_i\rfloor$ and setting $$ r_{i+1} = r_{i-1} - m_ir_i, $$ until it obtains $r_{k+1} = 0$, at which point $r_k = \gcd (r_0, r_1)$. This can be expressed in matrix form as $$ R_1 = \begin{bmatrix} r_0\newline r_1 \end{bmatrix};\qquad R_{i+1} = \begin{bmatrix} r_i\newline r_{i+1}\end{bmatrix} = M_iR_i;\qquad M_i=\begin{bmatrix} 0&amp;1\newline 1&amp;-m_i \end{bmatrix}, $$ and if we compute the matrix $S_k=M_kM_{k-1}\ldots M_1$, we have $R_{k+1}=S_kR_1$ which expresses the entry $r_k=\gcd(r_0,r_1)$ as a linear combination of $r_0$ and $r_1$. Assuming this gcd is 1, we can then read off the inverse of $r_1$ modulo $r_0$ (and vice versa) from the top row of $S_k$.</p> <p>As described above, this involves $O(k)$ arithmetic operations on integers of size $O(n)$, and one can show that $k=O(n)$, leading to a running time that is roughly quadratic in $n$. The fast Euclidean algorithm achieves a quasi-linear running time by only computing $O(\log n)$ of the matrices $S_i$. Roughly speaking (and ignoring many important details), this is done by directly computing $S_{k/2}$ using what is known as a "half-gcd" algorithm, computing $R_{k/2+1}=S_{k/2}R_1$, and then proceeding recursively. The half-gcd algorithm, in turn, works by recursively calling itself. The depth of the recursion is $O(\log n)$ and this yields an $O(M(n)\log n)$ complexity bound.</p> <p>This algorithm also works over polynomial rings and is often described in this setting. Further details can be found in the (incomplete) list of references below:</p> <p>Chapter 11 of von zur Gathen and Gerhard, "Modern Computer Algebra," Cambridge University Press, 2003.</p> <p>Chapter 2 of Yap, "Fundamental Problems of Algorithmic Algebra," Oxford University Press, 2000.</p> <p>N. Moller, "<a href="http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf" rel="nofollow">On Schonhage's algorithm and subquadratic integer GCD computation</a>," Mathematics of Comutation 77(261), pp. 589-607 (2008).</p> <p>Stehle and Zimmerman, "<a href="http://perso.ens-lyon.fr/damien.stehle/downloads/recbinary.pdf" rel="nofollow">A binary recursive GCD algorithm</a>," ANTS-VI, LCNS 3076, pp. 411-425, 2004.</p>

http://mathoverflow.net/questions/37862/need-algorithm-to-generate-all-permutations-of-the-integers-1-to-n/37868#37868 AVS 2010-09-06T09:08:42Z 2010-09-06T09:24:03Z

<p>Knuth's <em>The Art of Computer Programming, Volume 4, Fascicle 2: Generating all Tuples and Permutations</em> gives efficient (non-recursive) solutions to this and many other combinatorial enumeration problems.</p> <p>Section 7.2.1.2 contains 36 pages of material devoted to precisely the question you ask.</p>

http://mathoverflow.net/questions/19880/computationally-bounding-a-curves-genus-from-below/19903#19903 AVS 2010-03-31T01:24:59Z 2010-03-31T02:09:56Z

<p>I don't know an easy way to bound the genus from below (and I would love to hear of one), but there is a fairly general automated technique that can be used to simplify affine curves given by a plane equation (one that is not necessarily irreducible and possibly has many singularities). If the genus of the curve is small, the equation can often be simplified dramatically (possibly made trivial if the genus is 0). On the other hand, if the algorithm fails to make any progress you really can't say anything (so no lower bound).</p> <p>The basic idea is as follows. First define a cost metric that measures the "complexity" of a given plane equation that defines your curve (e.g. in terms of the degree in each variable, number of nonzero terms, coefficient sizes, etc...). Now define a small set of atomic "steps", say $d$ of them, each of which corresponds to a simple birational transformation (e.g. $x \to 1/x$ might be one step).</p> <p>Now consider the (infinite) $d$-regular graph whose edges correspond to atomic steps and whose vertices consist of birationally equivalent curves. We want to find a path from the given curve to one with lower cost. This is a combinatorial optimization problem that can be tackled with standard local search techniques (e.g. hill-climbing, simulated annealing, etc...). It isn't guaranteed to work (you could get stuck at a bad local minima), but it can be quite effective.</p> <p>This technique was originally developed in an effort to find "good" defining equations for $X_1(N)$ (which came up in another <a href="http://mathoverflow.net/questions/14054/where-can-i-find-a-comprehensive-list-of-equations-for-small-genus-modular-curves/18812#18812" rel="nofollow">Math Overflow question</a>) but it applies to any plane curve, see Section 3 of <a href="http://arxiv.org/abs/0811.0296" rel="nofollow">http://arxiv.org/abs/0811.0296</a> for more details.</p>

http://mathoverflow.net/questions/19824/the-limits-of-parallelism/19839#19839 AVS 2010-03-30T15:18:38Z 2010-03-30T15:18:38Z

<p>As a general rule, <em>parallel time</em> complexity classes are closely related to <em>serial space</em> complexity classes. A standard result (see Sipser or Papadimitriou) is $$ {\rm\bf PT/WK}\bigl(f(n),k^{f(n)}\bigr)\subseteq {\rm\bf SPACE}(f(n))\subseteq{\rm\bf NSPACE}(f(n))\subseteq{\rm\bf PT/WK}\bigl(f(n)^2,k^{f(n)^2}\bigr), $$ where ${\rm\bf PT/WK}\bigl(f(n),g(n)\bigr)$ is the class of problems that can be solved in $f(n)$ time with $g(n)$ total work (sum of the times over all processors).</p> <p>So if we impose a space restriction, say we consider a problem in ${\rm\bf TIME}(n!)\cap{\rm\bf SPACE}(n^k)$, then this problem also lies in ${\rm\bf PT/WK}\bigl(n^{2k},k^{n^{2k}}\bigr)$ and the answer to your question is yes.</p> <p>Without any space restriction, I believe the answer to your question is unknown. It is analogous to asking whether ${\rm\bf P}$ is contained in ${\rm\bf NC}$. We know ${\rm\bf NC}\subseteq{\rm\bf P}$, so this amounts to the open question ${\rm\bf NC} = {\rm\bf P}$?</p>

http://mathoverflow.net/questions/19204/a-question-on-liftings-of-supersingular-elliptic-curves-over-the-prime-fields/19331#19331 AVS 2010-03-25T17:34:11Z 2010-03-25T17:34:11Z

<p>This question is addressed as part of the proof of Theorem 14.18 (attributed to Deuring) given by Cox in "Primes of the Form $x^2 +ny^2$," see pp. 321-322. Cox counts curves rather than $j$-invariants, but for $p > 3$ there are exactly $p-1$ elliptic curves for each of the $p$ possible $j$-invariants of an elliptic curve over $\mathbb{F}_p$ (see Ex. 14.19). He first shows that the number of elliptic curves with trace $a\ne 0$ is exactly $$ \frac{p-1}{2}H(a^2-4p), $$ where $H(D)$ is the Hurwitz class number of the quadratic order with discriminant $D&lt;0$ (NB: many authors negate $D$). Cox then notes that the total number of elliptic curves over $F_p$ is $$ p(p-1) = N + \sum_{0&lt;|a|\le 2\sqrt{p}}\frac{p-1}{2}H(a^2-4p), $$ where $N$ counts the number of supersingular elliptic curves over $\mathbb{F}_p$ (so $N=(p-1)h_p^{(1)}$ in your notation). He then applies the class number formula $$ 2p = \sum_{0\le|a|\le2\sqrt{p}}H(a^2-4p), $$ to obtain $N=(p-1)/2H(-4p)$. Dividing by $p-1$ gives $h_p^{(1)} = H(-4p)/2$, which covers all three of the cases you list above.</p> <p>This argument may not be as direct as you would like, but it is fairly simple.</p>

http://mathoverflow.net/questions/10014/applications-of-the-chinese-remainder-theorem/18864#18864 AVS 2010-03-20T18:18:54Z 2010-03-20T18:18:54Z

<p>A variant of the CRT that has many practical applications is the "explicit CRT" (see <a href="http://cr.yp.to/antiforgery/meecrt-20060914-ams.pdf" rel="nofollow">http://cr.yp.to/antiforgery/meecrt-20060914-ams.pdf</a>, for a good introduction).</p> <p>One scenario where the explicit CRT (mod m) can be used, is the following. Suppose we know the value of an integer x modulo primes p_1, ..., p_n, whose product exceeds, say, 4|x|. Now we could use a standard CRT computation to determine x, but suppose we actually wish to know x mod m, where m is some integer not among the p_i. The explicit CRT lets us compute x mod m using arithmetic operations that involve operands that are all about the same size as m (rather than x). This is useful when x >> m; if x is a 100 digit number but the p_i's and m are all 3 or 4 digits numbers, you could compute x mod m on a pocket calculator with an 8 digit display, given the values x mod p_1, ..., x mod p_n.</p> <p>This technique is especially useful when one needs to compute many large integers x modulo the same m (the integers x might be the coefficients of a polynomial and m might be the characteristic of a finite field, for example). This approach is used in <a href="http://arxiv.org/abs/0903.2785" rel="nofollow">http://arxiv.org/abs/0903.2785</a> to compute Hilbert class polynomials, and in <a href="http://arxiv.org/abs/1001.0402" rel="nofollow">http://arxiv.org/abs/1001.0402</a> to compute modular polynomials, both of which are notoriously large but can be efficiently computed with the explicit CRT.</p>

http://mathoverflow.net/questions/62630/what-theorem-of-liouvilles-is-gian-carlo-rota-referring-to-here AVS 2011-04-23T09:43:40Z 2011-04-23T09:43:40Z

I apologize for misinterpreting your comment. Your meaning and tone would have been entirely clear had you ended your comment at the word universe as you suggest (and I'm sure Rota would have heartily approved).

http://mathoverflow.net/questions/62630/what-theorem-of-liouvilles-is-gian-carlo-rota-referring-to-here AVS 2011-04-23T02:03:56Z 2011-04-23T02:03:56Z

Hyperbole is far from the worst thing in the universe. Rota's flair for the dramatic is part of what made him such an engaging lecturer.

http://mathoverflow.net/questions/57548/second-stage-of-elliptic-curve-factorization-via-random-walk-pollards-rho-in-con/57565#57565 AVS 2011-03-07T16:54:10Z 2011-03-07T16:54:10Z

@jerr18 Yes, it would.

http://mathoverflow.net/questions/57548/second-stage-of-elliptic-curve-factorization-via-random-walk-pollards-rho-in-con/57565#57565 AVS 2011-03-06T19:08:51Z 2011-03-06T19:08:51Z

@jerr18 ...after further thought I don't see how to solve your problem using the approach described in Brent's paper. I have amended my answer to reflect this.

http://mathoverflow.net/questions/57548/second-stage-of-elliptic-curve-factorization-via-random-walk-pollards-rho-in-con/57565#57565 AVS 2011-03-06T16:18:10Z 2011-03-06T16:18:10Z

Actually, I may be missing something. It's been a while since I read this paper, and after looking at it more carefully I think I agree with you. The random walk approach does work and has the desired running time, but it is not clear how to detect collisions using a small amount of space. I will need to think about this some more...

http://mathoverflow.net/questions/57548/second-stage-of-elliptic-curve-factorization-via-random-walk-pollards-rho-in-con AVS 2011-03-06T14:24:19Z 2011-03-06T14:24:19Z

I assume that by constant memory you mean $O(1)$ elements of $\mathbb{Z}/n\mathbb{Z}$, or $O(\log n)$ bits.

http://mathoverflow.net/questions/51132/algorithm-for-summing-certain-sums-involving-the-floor-function AVS 2011-01-05T10:22:37Z 2011-01-05T10:22:37Z

When you say that your algorithm runs in polynomial time, I presume you mean that its complexity is polynomial in the size of its inputs, i.e. $\log P$, $\log Q$, and $\log N$.

http://mathoverflow.net/questions/42046/efficiently-getting-bits-of-n AVS 2010-10-13T19:28:45Z 2010-10-13T19:28:45Z

This doesn't answer your question, which I believe assumes that the base n is fixed, i.e. n=O(1), but I note that if n is allowed to grow with N, say log n ~ c log N for some small constant c &gt; 0, then the answer to your question is almost certainly no, since a positive answer would give a polynomial-time algorithm to factor n (even just using M=0).

http://mathoverflow.net/questions/41912/computation-of-inverses-modulo-p-followup AVS 2010-10-12T18:45:33Z 2010-10-12T18:45:33Z

The algorithm sketched in my comment above was only meant to show that your approach <i>could</i> be implemented in quasi-linear time. But this comes at the cost of making the algorithm much more complicated (which may be a pedagogical flaw or feature, depending on one's point of view), and it will still be slower than just computing the extended gcd.

http://mathoverflow.net/questions/41912/computation-of-inverses-modulo-p-followup AVS 2010-10-12T18:39:25Z 2010-10-12T18:39:25Z

I didn't mention this in my answer to the linked question, but the half-gcd algorithm can be used to &quot;jump&quot; directly to any particular step of the extended Euclidean computation (not necessarily the last one) using a logarithmic number of recursive calls. One could perform a binary search to find the greatest remainder less than p using half-gcds, yielding a quasi-linear running time that is slower than the fast Euclidean algorithm by only a log factor, and even this might be avoided (at least on average) by jumping to the middle step and searching linearly from there.

http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41004#41004 AVS 2010-10-04T15:21:16Z 2010-10-04T15:21:16Z

@idoneal: Actually, while Lehmer's idea does improve the constant and logarithmic factors in the standard Euclidean algorithm, it still runs in quadratic time. I believe the first subquadratic algorithms are due to Knuth (1970) and Schonhage (1971), who introduced the recursive divide-and-conquer approach that led to the half-gcd algorithm noted above. The Moller reference (to which I have added a link) gives a good summary of the historical development and the current state of the art.

http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q AVS 2010-10-04T10:13:42Z 2010-10-04T10:13:42Z

@Idoneal: The fast Euclidean algorithm takes time that is quasi-linear in the input size $n=\log q$ (whereas the standard Euclidean algorithm has complexity that is quadratic in $n$). Since linear time is required just to read the input, up to polylogarithmic factors, the fast Euclidean algorithm is optimal.

http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41001#41001 AVS 2010-10-04T10:09:52Z 2010-10-04T10:09:52Z

This is slower than the fast Euclidean algorithm, it takes time $O(nM(n))$ versus $O(M(n)\log n)$, where $n=\log q$.

http://mathoverflow.net/questions/37862/need-algorithm-to-generate-all-permutations-of-the-integers-1-to-n/37868#37868 AVS 2010-09-06T10:10:48Z 2010-09-06T10:10:48Z

@Eric Tressler: 'twas but an ephemeral shadow of the 4-dimensional object we were chasing, and such things are not meant to last. But I trust that its components have since been used to build even bigger and better things.

http://mathoverflow.net/questions/34082/order-matters-when-choosing-sets/34097#34097 AVS 2010-08-02T13:45:06Z 2010-08-02T13:45:06Z

Assume that the top square matrix B contains no bad rows or columns. Now fill in the remaining entries of A one by one with random elements drawn uniformly from V. At each step either A already contains a bad column, in which case it cannot contribute to the RHS, or it is more likely that we create a bad column than that we create a bad row. One could spell all this out using conditional probabilities, but I don't think this is necessary.