Tagged Questions

The tag has no usage guidance.

2k views

How did Cole factor $2^{67}-1$ in 1903

I just heard a This American Life episode which recounted the famous anecdote about Frank Nelson Cole factoring $N:=2^{67}-1$ as $193707721 \times 761838257287$. There doesn't seem to be a historical ...
2k views

Difficulty of factoring a Gaussian integer (compared to factoring its norm)

Given a Gaussian integer $G=a+ib$, with $gcd(a,b)=1$, a well-known strategy for factoring $G$ is to first compute its norm $N(G)=a^2+b^2$, factor the norm and finally recover the correct generator ...
4k views

Fastest way to factor integers < 2^60

I've been running a search for Mordell curves of rank >=8 for about 12 months and have identified approximately 280,000 curves in our archivable range, amongst many millions that aren't. For this ...
3k views

Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
1k views

Factoring Integers using Complex Integrals

Suppose $n$ is an integer and we wish to factor it. As a special case we have $n = pq$ with $p,q$ distinct primes. The problem: factoring $n$ via complex analysis tools Background I have been ...
2k views

Seeking Noetherian normal domain with vanishing Picard group but not a UFD

Once again, the question says it all. My motivation is the article on factorization I am writing. I want to explain (as well as to understand!) why for normal Noetherian domains of dimension greater ...
1k views

How divisible is the average integer?

I don't know any number theory, so excuse me if the following notions have names that I'm not using. For a positive natural number $n\in{\mathbb N}_{\geq 1}$, define $Log(n)\in{\mathbb N}$ to be ...
467 views

503 views

Why going to number fields in number field sieve help beat quadratic sieve?

To factor an $n$ bit integer number field sieve roughly takes $$e^{c{(\ln\ln n)^{\frac23}}({\ln n})^{\frac13}}$$ time while quadratic sieve takes $$e^{c{(\ln\ln n)^{\frac12}}({\ln n})^{\frac12}}$$ ...
1k views

Polynomials all of whose roots are rational

I have two questions about the class of integer-coefficient polynomials all of whose roots are rational. I asked this at MSE, but it attracted little interest (perhaps because it is not interesting!) ...
2k views

Density of Irreducible Polynomials in $\mathbb{Z}[x]$

Recently I was thinking about some questions concerning $\mathbb{Z}[x]$ and realized that they might be a bit easier if I knew the relative densities of reducible polynomials. Let $P_d$ denote the ...
97 views

Factorisation in $\mathbb{N}[X]$?

Do we know an efficient algorithm to factorise in $\mathbb{N}[X]$ ? One way to do factorisation in $\mathbb{N}[X]$ is to use an algorithm to factorise in $\mathbb{Z}[X]$ and to combine some factor to ...
553 views

Is this pleasing polynomial irreducible?

Let: $f(x)=x^n+2x^{n-1}+3x^{n-2}+4x^{n-3}+\ldots + (n-1)x^2+nx+(n+1)$. Is $f(x)$ irreducible? In light of the answers to this question, I now know that this is true when $n+1$ is prime. What about ...
694 views

runs of consecutive non squarefree integers

This question gained no attention at Math SE. Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us ...
163 views

Intuition for density comonad in relation to lifting problems

In Emily Riehl's Categorical Homotopy Theory, there is a section on Garner's Small Object Argument which I'm trying and failing to understand. Originally I followed most of Garner's paper, using the ...
6k views

Fast trace of inverse of a square matrix

Which would be the most efficient way (in computational time) to compute tr(inv(H)), where H is a (dense) square matrix? In my particular problem I also have a LU decomposition of H already available,...
2k views

Consecutive numbers with n prime factors

Let $P(m,n)$ mean that there is a number, $M$, such that starting with $M$ there are $m$ consecutive numbers each having exactly $n$ distinct prime factors. Is it obvious that $P(m,n)$ is true for ...
482 views

711 views

in what follows all the rings are commutative, nontrivial, with unit. Recall the following definitions: 1) $\pi\in A$ is prime if $(\pi)$ is a nonzero prime ideal 2) $\pi\in A$ is irreducible if $\... 1answer 521 views Divisibility and factorization in rings that are not integral domains In my course notes for an undergraduate course "Algebra I", I wrote at the point when I'm introducing the notion of divisibility in rings (in a section on unique factorization): We want to study ... 2answers 636 views Factoring some integer in the given interval I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms. Let N be a positive integer. Is there an efficient (i.e. ... 2answers 284 views A Different 2-factor in a graph We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891). My question is in ... 2answers 298 views Cubic graphs whose 2-factors all have the same cycle type Let$G$be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ... 3answers 817 views $\omega(p^n - 1)$as$n \rightarrow \infty$Although I am also interested in the number of distinct prime factors (not counting multiplicity), today I use$\omega(m)$to denote the number of (positive) prime factors (with multiplicity) of the ... 1answer 223 views Adding a multiple of the Identity to a LU factorized matrix Suppose a square, dense, symmetric matrix$A$has been factorized into$L$and$U$components by performing a LU decomposition. Now let$B = A+\lambda I$. Is there any way to efficiently compute the ... 2answers 488 views Parametrization of positive semidefinite matrices We know that a real, symmetric, positive definite matrix$A$of size$n\times n$can be parametrized by a vector$\theta$of$\frac{n(n+1)}{2}$parameters thanks to the Cholesky decomposition: $$A = ... 1answer 449 views Using the decomposition 641 = 5^4 + 2^4 to factor F_5 The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it: Problem 19.5 (p. 224) ... 3answers 2k views Reduction from factoring to solving Pell equation The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims There are reductions from factoring to solving Pell’s equation, and from solving Pell’s ... 1answer 174 views Shortest vector problem over polynomials In shortest vector problem, given a lattice in \Bbb Z^n, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult. Is there a polynomial analog of this problem ... 1answer 165 views Dynamics of the distribution of prime factorization types in increasing intervals I've tagged this as reference request as surely this question must be very well investigated, I just don't know how to look for it. Most likely the perfect answer will be in form of a keyword for ... 1answer 211 views Large gaps between consecutive irreducible polynomials with small heights For a prime gap of length at least n, a trivial upper bound for its first occurrence is N=n! or N=lcm(2,\dots,n). A bit better is N=p_1\cdots p_n where p_k is the kth prime, as then N+2,\... 2answers 164 views Collision polynomials Consider P_n(x) polynomials defined through the recurrence relations$$P_n(x)=2(1-x)P_{n-1}(x)-(1+x)^2P_{n-2}(x),$$with P_0(x)=1 and P_1(x)=1-3x. In fact, the explicit solution of these ... 0answers 128 views On factorization algorithms for \mathcal{O}[x] We know that \mathsf{LLL} algorithm provides factorization procedure that runs in poly time for polynomials in \Bbb Z[x] that are primitive. What other rings \mathcal{O} can we use instead of \... 1answer 310 views Bounded domain matrix factorization Assume we're trying to find A\in [-1,1]^{n\times d}, B\in [-1,1]^{m\times d}, from an observed matrix C\in [-d,d]^{n\times m}, where C=AB^T. The goal is to return \widehat A, \widehat B such ... 0answers 559 views Optimal Gear Trains Suppose you need to slow down a turning motor so that a gear turns at an angular velocity \frac{a}{b} of that of the motor shaft, where a and b are natural numbers. For example, this set of ... 0answers 563 views Is integer factorization harder than RSA (n=pq) factorization? [closed] This is a repost. I could not get a precise answer on math.SE and cstheory.SE Let FACT denote the integer factoring problem: given n \in \mathbb{N}, find primes p_i \in \mathbb{N}, and integers ... 3answers 494 views 2^n-1 consisting only of small factors I've checked the factorization of 2^N - 1 up through N = 120 for the largest prime factor, and it looks like the largest value of N where 2^N-1 has a largest prime factor under 2500 is N = 60 (... 2answers 1k views Factoring and solving trinomials Has the problem of factoring (over the rationals) the general trinomial ax^n+bx^k+c with a,b,c\in\mathbb{Z}, n,k\in\mathbb{N}, n>k>1 been solved? By solved I mean a classification theorem ... 2answers 340 views Find all possible rational values of a parametric quartic such that it is reducible Description: Given the following parametric quartic polynomial y^4 - 28 z y^3 - 14 (656 - 328 z + 83 z^2) y^2 + 4 z (-20464 + 10232 z + 3409 z^2) y + 91 (62208 - 62208 z + 41504 z^2 - 12976 z^3 +... 1answer 1k views The number of distinct prime factors of n\in\mathbb N Let \omega(n) be the number of distinct prime factors of a natural number n. Note that \omega(n)=0\iff n=1, and that \omega(24)=\omega(2^3\cdot 3^1)=2\ (\not = 4). (For more details, you ... 3answers 421 views Distinct primitive factorizations over integers of number fields I am curious about the following. Let K be a number field. For any a \in \mathcal{O}_K in its ring of integers, let N(a) be zero if there exist elements b, c \in \mathcal{O}_K \setminus \... 1answer 462 views Factorization in the Wiener algebra on the unit disc. Consider the Banach algebra W^+=\ell^1(\mathbb{Z}^+), viewed upon as the analytic functions f on the unit disc \mathbb{D} such that$$\|f\|=\sum_{k\ge0}|a_k|<\infty$$where$$f(z)=\sum a_kz^k$...
Is there an analog of Euler's Two Squares factoring theorem over polynomial rings $\Bbb Z[x]$ by considering a version for non-negative polynomials? Euler's two squares factoring states that numbers ...
The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...