User m.s. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T16:25:51Z http://mathoverflow.net/feeds/user/4415 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31646/does-algebraic-numbers-coloured-by-degree-form-a-fractal Does "Algebraic numbers coloured by degree" form a fractal? M.S. 2010-07-13T01:28:38Z 2012-10-09T08:56:32Z <p><a href="http://en.wikipedia.org/wiki/File%3AAlgebraicszoom.png" rel="nofollow">This picture</a> from Wikipedia's article on <a href="http://en.wikipedia.org/wiki/Algebraic_number" rel="nofollow">Algebraic numbers</a> shows a visualization of Algebraic numbers coloured by degree.</p> <p>I'm wondering if this is a fractal?</p> http://mathoverflow.net/questions/65921/is-integer-factorization-harder-than-rsa-npq-factorization Is integer factorization harder than RSA ($n=pq$) factorization? M.S. 2011-05-25T03:14:07Z 2011-05-25T03:14:07Z <p><em>This is a repost. I could not get a precise answer on <a href="http://math.stackexchange.com/questions/40971/is-the-factorization-problem-harder-than-rsa-factorization-n-pq" rel="nofollow" title="math.SE">math.SE</a> and <a href="http://cstheory.stackexchange.com/q/6704/17" rel="nofollow" title="cstheory.SE">cstheory.SE</a></em></p> <p>Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $n = \prod_{i=0}^{k} p_{i}^{e_i}.$</p> <p>Let RSA denote the special case of factoring problem where $k=2, e_i=1$ for all $i$. That is, given $n,$ find two primes $p,q,$ such that $n = pq$ or NONE if this factorization does not exist.</p> <p>Obviously, RSA is an instance of FACT. Is FACT harder than RSA? Given an oracle that solves RSA in polynomial time, could we construct a polynomial time algorithm to solve FACT?</p> http://mathoverflow.net/questions/61861/fast-algorithms-for-computing-nullspace-of-a-positive-semidefinite-matrix-over-z Fast algorithms for computing nullspace of a positive semidefinite matrix over Z M.S. 2011-04-15T20:06:43Z 2011-04-15T22:38:21Z <p>Let $A \in \mathbb{Z}^{n \times n}$ be a positive semidefinite <em>sparse</em> matrix. I am looking for asymptotically fast algorithms for computing the nullspace basis of $A$ (or just random elements in the nullspace). I wonder whether there are methods that can exploit the fact that $A$ is positive semidefinite to achieve better perfomance.</p> http://mathoverflow.net/questions/51264/smallest-prime-that-does-not-divide-the-vandermonde-determinant Smallest prime that does not divide the Vandermonde determinant M.S. 2011-01-05T23:21:29Z 2011-01-06T00:42:39Z <p>Let $V = \Pi_{1 \le i &lt; j \le n} (a_j - a_i)$ be the <a href="http://planetmath.org/encyclopedia/DeterminantOfTheVandermondeMatrix.html" rel="nofollow">determinant of the Vandermonde matrix</a> where $1 = a_1 &lt; \cdots &lt; a_n = d$ (with $d >> n$). What is the smallest prime $p$ (or the lower bound) such that $p \nmid V$? Preferably $p &lt; n$.</p> http://mathoverflow.net/questions/48988/matrix-version-of-berlekamp-massey-algorithm Matrix version of Berlekamp Massey algorithm M.S. 2010-12-10T22:04:35Z 2010-12-10T22:40:19Z <p>What are the most obvious generalizations of Berlekamp Massey algorithm [1] to matrix sequences?</p> <blockquote> <p>[1] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.9932" rel="nofollow">Massey, J. L.</a>, "Shift-register synthesis and BCH decoding", IEEE Trans. Information Theory IT-15 (1): 122–127</p> </blockquote> http://mathoverflow.net/questions/17247/set-comprehension-when-the-condition-is-false Set comprehension when the condition is false M.S. 2010-03-06T00:07:56Z 2010-03-06T01:29:01Z <p>The Cartesian product of two empty sets is the singleton set $\{ () \}$ containing the empty tuple. So, given a set $A$ which is empty, $A \times A$ is defined as: $$A \times A = \{ (a,a) \mid a \in A \} = \{ () \}$$ Now, does that mean that $()$ satisfies the condition $a \in A$? And if so, why don't we include the empty tuple in the Cartesian product of non-empty sets?</p> <p>(It would be nice if you point out which concept I mis-understand: the set comprehension, or the tuple.)</p> <p>Thanks in advance.</p> <p>[edit: I should add the following link: <a href="http://en.wikipedia.org/wiki/Empty_product#Nullary_Cartesian_product" rel="nofollow">Wikipedia: Empty_product#Nullary_Cartesian_product</a>]</p> http://mathoverflow.net/questions/88130/question-about-matrices-linear-algebra Comment by M.S. M.S. 2012-02-10T19:29:02Z 2012-02-10T19:29:02Z Ops. link broken: <a href="http://math.stackexchange.com/" rel="nofollow">math.stackexchange.com</a> http://mathoverflow.net/questions/88130/question-about-matrices-linear-algebra Comment by M.S. M.S. 2012-02-10T19:28:31Z 2012-02-10T19:28:31Z You should post this type of questions to [math.SE](math.stackexchange.com). http://mathoverflow.net/questions/65921/is-integer-factorization-harder-than-rsa-npq-factorization Comment by M.S. M.S. 2011-05-25T16:29:26Z 2011-05-25T16:29:26Z @KotelKanim If $n$ is not decomposable into a product $pq$ of two primes, then RSA oracle will terminate (in polytime) with the answer NONE (or 'false' if you wish). http://mathoverflow.net/questions/65921/is-integer-factorization-harder-than-rsa-npq-factorization Comment by M.S. M.S. 2011-05-25T03:44:17Z 2011-05-25T03:44:17Z @Fran&#231;ois: Well, fair enough. http://mathoverflow.net/questions/51264/smallest-prime-that-does-not-divide-the-vandermonde-determinant Comment by M.S. M.S. 2011-01-06T00:07:36Z 2011-01-06T00:07:36Z Yes. Consider the primes in the range [2 .. d]. Some of them will divide V, other won't. I want the smallest prime p that does not divide V. http://mathoverflow.net/questions/51264/smallest-prime-that-does-not-divide-the-vandermonde-determinant/51266#51266 Comment by M.S. M.S. 2011-01-06T00:04:45Z 2011-01-06T00:04:45Z I'm looking for a prime $p &lt; n$ such that $p \nmid V$. It is the case that a_1 = 1 (actually, 1 = a_1 &lt; .. &lt; a_n = d and d &gt;&gt; n). http://mathoverflow.net/questions/31646/does-algebraic-numbers-coloured-by-degree-form-a-fractal Comment by M.S. M.S. 2010-07-14T17:19:07Z 2010-07-14T17:19:07Z Fair enough. Thanks for the clarification. http://mathoverflow.net/questions/17247/set-comprehension-when-the-condition-is-false/17253#17253 Comment by M.S. M.S. 2010-03-06T20:25:58Z 2010-03-06T20:25:58Z I now see where is my confusion. Thanks