Questions tagged [factorization]

For questions about factorization, the decomposition of mathematical objects (e.g. natural numbers, polynomials) into products of smaller objects (e.g. primes, lower degree polynomials).

Filter by
Sorted by
Tagged with
116 votes
5 answers
32k 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 $193{,}707{,}721\times 761{,}838{,}257{,}287$. There doesn't seem to be ...
David E Speyer's user avatar
44 votes
1 answer
17k views

Conjecturally unsafe RSA primes $p=27a^2+27a+7$

We got strong numerical evidence that primes of the form $p=27a^2+27a+7$ are unsafe for cryptographic purposes since they can be found in the factorization. Consider the following generic factoring ...
joro's user avatar
  • 24.2k
9 votes
2 answers
533 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 ...
Wolfgang's user avatar
  • 13.2k
4 votes
1 answer
312 views

Generalizing Kasteleyn's formula even more?

Inspired and intrigued by this question, I decided just for fun to throw in another integer into the factors and look what happens. So for $k\in\mathbb Z$, let us define $$K_r(n,k):=\prod_{\ell_1=1}^...
Wolfgang's user avatar
  • 13.2k
4 votes
3 answers
2k 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 (...
Jason S's user avatar
  • 653
33 votes
7 answers
3k views

On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$

Let $n = 2m$ be an even integer and let $F_n(X)$ be the polynomial $$F_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}.$$ I observed (but cannot prove) that the polynomial $F_n$ is always divisible by $...
WhatsUp's user avatar
  • 3,232
25 votes
1 answer
6k 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 ...
user16007's user avatar
  • 780
15 votes
2 answers
937 views

Factorization when a factor is partially known

Let's say that I have a very large number of the order ($10^{250+}$) which is composite. I have been given one of its factor partially to a significant amount of digits (say 75+). Then, how can I ...
Student's user avatar
  • 153
15 votes
6 answers
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 ...
Pete L. Clark's user avatar
13 votes
3 answers
3k 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 ...
ARupinski's user avatar
  • 5,181
13 votes
2 answers
5k 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 = ...
epsilone's user avatar
  • 313
12 votes
3 answers
3k views

What is known about the polynomial factorization of power series?

Some power series factorize; $1+\sum_{n=1}^\infty x^n=\prod_{n=1}^\infty (1+x^{2^n})$ and $1+\sum_{n=1}^\infty x^{2n}/(2n+1)!=\prod_{x=1}^\infty (1+x^2/n^2\pi^2)$ for example; while others do not----...
John Bentin's user avatar
  • 2,427
12 votes
5 answers
2k 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!) ...
Joseph O'Rourke's user avatar
11 votes
2 answers
4k views

How can one construct a sparse null space basis using recursive LU decomposition?

Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
Alec Jacobson's user avatar
10 votes
2 answers
17k 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,...
César's user avatar
  • 339
10 votes
1 answer
291 views

$2$-adic valuation of Schur $P$-functions in the power-sum basis

For a partition $\lambda$, let $P_\lambda$ be the Schur $P$-functions (case $t=-1$ of Hall-Littlewood symmetric functions) and let $p_\lambda=p_{\lambda_1}p_{\lambda_1}\cdots p_{\lambda_k}$ be the ...
Antoine Labelle's user avatar
10 votes
3 answers
3k 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 ...
joro's user avatar
  • 24.2k
10 votes
3 answers
2k views

Irreducible/prime/indivisible elements

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 $\...
GreginGre's user avatar
  • 183
9 votes
1 answer
566 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 ...
Arrow's user avatar
  • 10.3k
9 votes
1 answer
675 views

Hensel's lemma, Bezout's identity, and the integers

Factorization in the ring $\mathbb{Z}[x]/(x^2+1)\mathbb{Z}[x]\cong \mathbb{Z}[i]$ is well known. For instance, $5$ and $13$ (and any prime $\equiv 1\pmod{4}$) are no longer prime. The factorization ...
Pace Nielsen's user avatar
9 votes
3 answers
971 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 ...
The Masked Avenger's user avatar
8 votes
1 answer
233 views

Functions over monoids which factor in two different ways

This is a follow-up question to this MO question, which was asked by Richard Stanley in a comment to my answer there. Let $S$ be a commutative monoid and $f(x_1, \dots, x_n)$ be a function from $S^n$ ...
Tony Huynh's user avatar
  • 31.5k
7 votes
0 answers
849 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 ...
Joseph O'Rourke's user avatar
7 votes
1 answer
299 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 $k$th prime, as then $N+2,\...
Wolfgang's user avatar
  • 13.2k
4 votes
0 answers
214 views

Characterizing atomicity in a commutative domain

In Proposition 1.1 of [Math. Proc. Cambridge Phil. Soc. 64 (1968), No. 2, 251-264], P.M. Cohn famously claimed (without proof) that a commutative domain is atomic if and only if it satisfies the ...
Salvo Tringali's user avatar
4 votes
0 answers
206 views

More 3-connected cubic graphs with all 2-factors of same cycle type?

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 ...
Wolfgang's user avatar
  • 13.2k
3 votes
0 answers
66 views

Atomicity and BF-ness in monoids of integer points of a polyhedral cone of $\mathbb R^n$

Fix an integer $n \ge 2$ and let $H$ be the (additive) monoid of integer points of a polyhedral cone of the Euclidean space $\mathbb R^n$ with the additional property that $H \setminus \{0_n\}$ is ...
Salvo Tringali's user avatar
3 votes
1 answer
3k views

Uniqueness of the reduced rank QR decomposition

Let $A$ be a $n\times n$ matrix that is a real, symmetric, positive semidefinite and has rank $r$. I read about the rank reduced $QR$ decomposition (here for example) as the QR variant where $A=QR$ ...
epsilone's user avatar
  • 313
3 votes
1 answer
487 views

How much space between these smooth numbers?

In looking at OEIS sequence A063539, $1,8,12,16,18,24,27,30,32,36,40,45,...$ I noticed that the first 1000 members were less than 4000, and thought there were no large gaps between them. What (if ...
Gerhard Paseman's user avatar
3 votes
1 answer
131 views

Factoring $x^p H(x) + x^q B(x) + T(x)$ over a finite field

$\newcommand\S{\mathcal S}$ Let $p$ be a prime, and suppose that $0.9(p-1)<q<p-1$. Suppose, furthermore, that $H,B,T\in\mathbb F_p[x]$ satisfy $\max\{\deg H,\deg T\}\le q-1$ and $\deg B\le p-1-q$...
Seva's user avatar
  • 22.8k
2 votes
1 answer
354 views

Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$

This is a follow-up question to Positive integer solutions to the diophantine equation $(xz+1)(yz+1)=z^4+z^3 +z^2 +z+1$ Let \begin{equation} P(x,n)= 1+x+x^2+ \cdots + x^n, \end{equation} \begin{...
ASP's user avatar
  • 319
2 votes
1 answer
372 views

Irreducibility of Faulhaber-like Polynomials over $\mathbb Q[x]$

Motivation: Inspired by the famous Faulhaber polynomials $F_k(N)=\displaystyle\sum_{n=0}^Nn^k,$ I decided to study their alternating versions, $\Phi_k(M)=\displaystyle\sum_{n=0}^M(-1)^nn^k$. For $k\...
Lucian's user avatar
  • 655
1 vote
2 answers
366 views

When is a prime factor of Mersenne number Wieferich prime?

Wieferich prime is a prime number $p$ such that $p^2$ divides $2^{p - 1} - 1$. There are only two Wieferich primes known and it is an open problem if there are infinitely many non-Wieferich primes. ...
joro's user avatar
  • 24.2k
1 vote
0 answers
223 views

Construct special "joint SVD" from separate SVDs

Given two matrices, $A,B\in\mathbb{C}^{n\times n}$ which can be written as $$ A = XD_AY^T \\ B = XD_BY^T $$ where $X$ and $Y\in\mathbb{C}^{n\times n}$ are unitary and with diagonal $D_A$ and $D_B\in\...
sqrt6's user avatar
  • 61
0 votes
1 answer
251 views

Infinite products for linear combinations of sines or cosines

There is a well known infinite product both for $\phi(x)=\sin x$ and $\phi(x)=\cos x$. These are particular cases of the Weierstrass factorization theorem. What about $\phi(x)=a_1\cos b_1 x + a_2\cos ...
Vincent Granville's user avatar