# 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).

168
questions

**2**

votes

**0**answers

44 views

### How to prove polynomial inequality encoded from 1-factors in $K_{2n}$

Let $G=(V,E)$ be a complete graph $K_{2n}$ and it has $m$ 1-factors $f_{i,(i=1,\dots,m)}$, where $m=\frac{(2n)!}{n!2^n}$.
Some definition:
$F=\{f_{1},f_{2},...,f_{2n-1}\}$ is one 1-factorization in $...

**3**

votes

**0**answers

250 views

### If $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then is one of its prime factors always greater than $17$? [closed]

Is it true that if $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then it has a prime factor greater than $17$?
Note: This question was asked in MSE but did not receive an ...

**2**

votes

**1**answer

41 views

### Matrix factorization for dimensional reduction similar to spectral decomposition/SVD

I have a graph clustering problem I'm working on and it basically involves finding a factorization of the adjacency matrix $A$ such that the following equations are (approximately) satisfied:
$$
A \...

**1**

vote

**1**answer

128 views

### Around a characterization for even perfect numbers, similar than Euclides-Euler theorem, in terms of totatives

In this post we denote the sum of divisors function as $$\sigma(n)=\sum_{1\leq d\mid n}d,$$ then an even perfect number is a positive integer $n\equiv 0\text{ mod }2$ for which $\sigma(n)=2n.$ As ...

**2**

votes

**1**answer

164 views

### Equations involving arithmetic functions of primorials

Let $\sigma(n)=\sum_{1\leq d\mid n}d$ the sum of divisors, $\varphi(n)$ the Euler's totient function and we denote the primorial $\prod_{k=1}^n p_k$ as $N_n$, where $p_k$ denotes the $k$-th prime ...

**4**

votes

**0**answers

139 views

### Near Pochhammer symbols: the equation $(n)_m-(k)_l=2$ for integers greater than or equal to two

In this post I consider the following equation involving Pochhammer symbols,
$$(n)_m-(k)_l=2\tag{1}$$
for positive integers $n\geq 2$ and $k\geq 2$, and positive integers $m\geq 2$ and $l\geq 2$.
...

**2**

votes

**1**answer

145 views

### Factorizing a bivariate polynomial

I have a bivariate polynomial for each $n=0,1,2...$
$$
f_n(x,y)=\sum _{k=0}^n \frac{(-1)^k}{2 k+1} \binom{n}{k} \left(x ^2-y ^2\right)^{2 n-2 k}\left([y ( x^2 -1) +x(1 -y^2 )]^{2 k+1}\\ \qquad\qquad\...

**3**

votes

**0**answers

71 views

### Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...

**3**

votes

**1**answer

77 views

### Irreducible skew polynomials over an algebraically closed field

Let $\mathbb{F}$ be a field, and denote with $\mathbb{F}[t,\sigma]$ the skew-polynomial ring, where $\sigma$ is an automorphim of $\mathbb{F}$. Recall that the multiplication of this ring is defined ...

**5**

votes

**0**answers

382 views

### Factorizations as a product of primes minus one

Let $x$ be a positive rational number. I am interested in factorizing $x$ as a product of primes minus one. In fact, I would also like make sure the primes in the decomposition are distinct, and I ...

**1**

vote

**0**answers

166 views

### Heuristic for lower bounding the time for integer factorization?

I am posting this question here in hope that someone finds this heuristic useful, and maybe someone with more experience will make use of this:
As @GerryMyerson suggested here is a statement of what ...

**8**

votes

**0**answers

130 views

### A factorization game

This is a toy version of a problem I have posted recently.
Imagine playing the following game. You choose a polynomial $B$ over a finite field $\mathbb F_p$, of degree $\deg B\le p-1$ (where $p$ is a ...

**3**

votes

**1**answer

122 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$...

**1**

vote

**1**answer

168 views

### Proving largest power of $(a^2-ab+b^2)$ that divides $a^p-b^p-(a-b)^p$ for odd prime $n$

It is obvious that for odd $n \in \Bbb N$, $a^n-b^n-(a-b)^n$ is divisible by $ab(a-b)$ (with $n=1$ being a special case in which $a^n-b^n-(a-b)^n$ is zero). This can be viewed as a fact about ...

**21**

votes

**1**answer

2k views

### Circle $x^2 + y^2 = n!$ doesn't hit any lattice points for any $n$ except for $0$, $1$, $2$ and $6$ or does it?

I stumbled across the following problem in high school:$$
x^2 + y^2 = n!
$$
I tested it within my laptop capabilities, watched a 3b1b video Pi in prime regularities, where he explains how to find the ...

**4**

votes

**0**answers

151 views

### Consecutive integers each of which has a large prime factor

There are many results about consecutive integers all having small prime factors. But what about consecutive integers each of which has a large prime factor?
More precisely, let $P(n)$ be the ...

**5**

votes

**1**answer

119 views

### Density of numbers with multiple factors near square root

Fix constants $1\leq \alpha<\beta$. What is the density of the set of positive integers $n$ with at least two factors between $\alpha\sqrt{n}$ and $\beta\sqrt{n}$?
(I am specifically interested ...

**0**

votes

**1**answer

290 views

### Reason Coppersmith fails here?

Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$.
$P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and ...

**1**

vote

**1**answer

130 views

### Factoring with partial information on gaps

If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of ...

**1**

vote

**1**answer

62 views

### Generalizing cycle/pseudo-tree factorizations for permutations/transformations to arbitrary binary relations

It's well known every permutation has a unique factorization into disjoint cycles (up to a re-ordering of these factors since they commute), while similarly it can be shown that every transformation ...

**2**

votes

**0**answers

95 views

### Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?

We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...

**4**

votes

**1**answer

236 views

### Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?

The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...

**5**

votes

**1**answer

174 views

### $\{ P_3, P_4 \}$-factor

Definition. A graph $G=(V,E)$ is to be $\{d_1,\dots,d_n\}$-graph if for each vertex $v\in V$ we have $\text{deg}(v)=d_i$ for some $i=1,\dots n$.
Definition. A connected graph $G=(V,E)$ is called $...

**-1**

votes

**1**answer

138 views

### The power of a prime in the prime factorization of a factorial [closed]

How do we find—for example—how many $5$s are in the prime factorization of $n!$? I've read that it is $\lfloor n/5 \rfloor$, but why is that?

**5**

votes

**1**answer

133 views

### Finding a particular matrix factor

Consider the following Laurent polynomial matrix-valued function in the variable $x\in\mathbb{C}$
$$
A(x) = \begin{bmatrix} 0 & x \\ x^{-1} & 0\end{bmatrix}.
$$
I'm interested in finding a ...

**3**

votes

**0**answers

223 views

### Can we efficiently factor $n$ given that $n=pq$ where $p,q$ are primes satisfying $p=a^2+b^2, q=2ab+1$ for some $a,b$

Suppose we're given a particular number $n \in \mathbb{N}$.
We're also given that $n=pq$ where $p,q$ are unknown primes satisfying
$$
p=a^2+b^2
$$ and
$$
q=2ab+1
$$
for some $a,b$.
Is there an ...

**3**

votes

**2**answers

142 views

### Factoring certain Hessians of real homogeneous bivariate polynomials

For any homogeneous polynomial $f \in \mathbb R [x,y]$, define the homogeneous polynomial
$$H(f) := \partial_yf^2\partial_x\partial_xf-2\partial_xf\partial_yf\;\partial_x\partial_yf+\partial_xf^2\...

**5**

votes

**2**answers

200 views

### Factoring a positive semidefinite matrix into binary matrices

This question is motivated by a research problem I recently encountered. Consider two sets of random variables $\mathbf{X}$ and $\mathbf{Y}$, where $\mathbf{Y}$ can be expressed as a linear ...

**2**

votes

**0**answers

142 views

### List of analytically known eigensystems?

In condensed matter physics, we often come across matrices that are multi-diagonal or banded. For example, I may have a matrix with three tridiagonal bands, or a tridiagonal band and two/four ...

**2**

votes

**2**answers

663 views

### What is the natural density of hyper prime numbers?

What do we mean by hyper prime numbers? Well, roughly speaking they are natural numbers which are prime with respect to hyperoperators in arithmetic such as exponentiation, tetration, pentation, et ...

**33**

votes

**7**answers

1k 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 $...

**12**

votes

**1**answer

279 views

### Factorization of polynomials into “shortest possible” factors

A while ago I asked a question at Mathematica.SE about how to factorize a polynomial into terms with as few monomials as possible each. I now realized that I actually do not know what is rigorous ...

**4**

votes

**1**answer

186 views

### A Handbook of Matrix Factorizations

I am looking for a good collection of facts regarding the various types of matrix factorizations, something like a "Handbook of Matrix Factorizations" or a very-thorough review paper. I am hoping for ...

**1**

vote

**1**answer

89 views

### amalgamated sum of monoids

Consider the amalgamated sum $Q_1 \rightarrow^{v_1} Q_1 \oplus_P Q_2 \leftarrow^{v_2} Q_2$ of $Q_1 \leftarrow^{u_1} P \rightarrow^{u_2} Q_2$ with $Q_1,Q_2,P$ being monoids.
Why does $v:= v_i \circ u_i$...

**1**

vote

**0**answers

80 views

### What size factor-base for Lenstra Elliptic Curve factorization

I'm writing a program to factorize numbers using Lenstra Elliptic Curve Factorization.
According to the wikipedia article, I should pick some k with a lot of small factors and then take a random ...

**5**

votes

**1**answer

209 views

### Factorization of Gabriel-Zisman localization construction?

My question concerns whether the Gabriel-Zisman localization construction $S^{-1}$ for categories admits a known factorization into a pair of commuting constructions $S^l$ and $S^r$.
The localization ...

**8**

votes

**1**answer

446 views

### Can a squarefree polynomial in K[x,y] not be squarefree in K[[x]][y]?

In a UFD, as usual one says that $f$ is square-free if it is not divisible by the square of any irreducible element, i.e., if it has no multiple factor.
An polynomial $f\in k[x,y]$ can have more ...

**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 ...

**2**

votes

**1**answer

248 views

### Which composites pass this probabilistic primality test?

If a composite integer resembles a prime too closely, it must pass
algorithmic tests designed to find primes and in addition avoid nontrivial
factorization.
Given an integer $p$, assume it is prime ...

**2**

votes

**1**answer

249 views

### How hard is it to compute these prime factor related problems?

We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).
Let $\omega(n)$ be number of distinct ...

**1**

vote

**1**answer

240 views

### Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ are irreducible and of equal degree what is the best ...

**3**

votes

**0**answers

151 views

### Finding Rational Curves on a Surface

Let the field of rational numbers be our base field $k$. I hope to find all rational curves on the following surface $S$ defined by $f$. You can find the motivation in the end.
$f= (x^2y^2)z^3 + (5x^...

**4**

votes

**2**answers

733 views

### Hilbert Numbers

A positive integer $n$ is called a Hilbert number if $\exists a,b,d \in \mathbb{N}$ such that $ 4ab-a-b = d n$ and $d|a b$.
I ran an algorithm checking divisors for all $0\lt a,b\le500$, and the ...

**7**

votes

**1**answer

327 views

### $\log \log p / \log \log n$, where $p|n$, gets equidistributed in [0,1] (for almost all $n$)

According to Hardy-Ramanujan/Erdős-Kac we know that usually there are $\sim\log\log n$ prime numbers in a factorization. But if you pick up a natural number at random, and you factor it, what is the ...

**4**

votes

**1**answer

151 views

### Irreducible Hurwitz Factorization of A Complex Polynomial

I've decided to repost this question, which originally appeared on MSE, here. It is part of my series of open problems for enthusiasts and, while I understand this crowd is focused on professionals, ...

**2**

votes

**1**answer

164 views

### Factorization of trigonometric matrices

Consider two real square matrices $A_1$ and $A_2$ and $t_1,t_2\in\mathbb{R}$. $A_1$ and $A_2$ do not commute. Consider the following matrix involving matrix trigonometric functions:
\begin{equation}
...

**6**

votes

**1**answer

256 views

### Check irreducibility of an explicit polynomial, without computer

I have a polynomial of degree 8 in 6 variables given explicitly by
$$ (\sqrt{1+(x_1+x_2+x_3)^2+(y_1+y_2+y_3)^2}+\sqrt{1+x_1^2+y_1^2}+\sqrt{1+x_2^2+y_2^2}+\sqrt{1+x_3^2+y_3^2})\times\text{the other ...

**3**

votes

**0**answers

86 views

### Current best time for factoring in $\Bbb Q[x]$

Lenstra Lenstra Lovasz have a $O((nb)^{11})$ deterministic algorithm to factor primitive polynomials in $\Bbb Q[x]$ where $b$ is total number of bits in the polynomial and $n$ is degree of the ...

**4**

votes

**1**answer

245 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}^...

**4**

votes

**1**answer

131 views

### Counting integers with k large prime divisors

If $x \ge y \ge 1$ are real numbers and if $k$ is a positive integer, take $\Phi_k(x, y)$ to be the number of integers $\le x$ with exactly $k$ prime factors and no prime factor $\le y$. If $y$ is ...