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

219
questions

3
votes

0
answers

78
views

### Construct a special kind of SVD

Given two matrices, $A,B\in\mathbb{C}^{n\times n}$ which can be written as
$$ A = XD_AY^H \\
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\...

1
vote

0
answers

80
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\...

3
votes

0
answers

118
views

### Order of elements $\gamma$ and $1-\gamma$ in $\mathbb{F}_q$

I'd like to find if possible the orders possible for $1-\gamma$ given a $\gamma\in\mathbb{F}_q$ of given order $\mathcal{o}$ (where $q=p^f$).
Which is clear is that these order have the same degree (...

1
vote

1
answer

76
views

### Order of roots for a polynomial $P\in\mathbb{F}_p[T]$

Let $P\in\mathbb{F}_p[T]$ (not supposed irreducible). All roots $\xi$ of $P$ have a certain order $k$ such that $\xi^k=1$.
Question: is it possible to know the order of the roots of the given ...

0
votes

0
answers

97
views

### From direct sum of quotient group of a group to direct sum of the group

We know that for a cyclic group $G$, if $G=A\oplus B$, then for some subgroups $H$ of $G$, We have $G/H=(A+H)/H\oplus (B+H)/H.$ But, if we know that for a subgroup $H$ of $G$, $G/H=(A+H)/H\oplus (B+H)...

0
votes

0
answers

57
views

### Sampling a distribution related to factoring

Consider these two problems.
Given two numbers $a$ and $N$, find the smallest $r$ such that $a^r= 1 \pmod N$.
Given three numbers $a$, $r$, and $N_{max}$, find $N\le N_{max}$ such that $a^r= 1 \pmod ...

1
vote

0
answers

51
views

### What is the factorization algebra/space of an affine W algebra?

The affine vertex algebra $V_k(\mathfrak{g})$ factorizes, i.e. comes from a factorisation space, the Beilinson Drinfeld Grassmannian. Similarly, lattice vertex algebras have a factorization analogue.
...

2
votes

1
answer

217
views

### Eisenstein polynomial of totally ramified extension over $p$-adic field

Let $p\geq 3$ be a prime number, $K$ be a finite extension of $\mathbb{Q}_p$ with no non-trivial unramified subextension, $f(x)$ be an irreducible monic polynomial in $\mathcal{O}_K[x]$, making $L=K[x]...

0
votes

0
answers

46
views

### Partition of multisets of polynomials

Problem: Given a multiset $S$ of irreducible polynomials in $\mathbb{Z}[x]$, say YES if $S$ can be partitioned into two nonempty multisets $A$ and $B$ such that both the product of all the elements of ...

12
votes

1
answer

509
views

### Would efficient factoring have any *other* useful applications?

This question is certainly somewhat opinion-based, but hopefully not hopelessly so.
The granddaddy of all applications for an efficient period finding or factoring capability (e.g. Shor's algorithm) ...

10
votes

1
answer

273
views

### Fixpoints of $m\longmapsto \mathrm{rad}(\phi(m^2))$ under iteration

Given a strictly positive integer $m$ let $\alpha(m)=\mathrm{rad}(m\phi(m))$
be the radical (product of all distinct prime divisors) of the product of $m$ and of Euler's totient function $\phi(m)=m\...

0
votes

0
answers

28
views

### Number of different factorizations

I define $\nu(n)$ the number of different factorizations for an integer $n$. I know there are papers about $\delta(n)$ the number of dividers for an integer $n$ (Landau, Euler, Dirichlet) but I still ...

3
votes

1
answer

92
views

### Factoring higher-order differential operators

I have been researching various methods for solving differential equations. In particular, I want to better understand the factoring approach. For example, if we want to solve a general second order ...

1
vote

2
answers

160
views

### Does having the discrete logarithm of prime factors of $n$ allow us to calculate any discrete log more efficiently?

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\...

6
votes

1
answer

843
views

### Solution to sixth order equation

I'm dealing with the expression $x = \frac{1}{3}y(y+1)(2y+1)^2(2y^2+2y+1)$. What is this approximately, if one is explicitly writing y in terms of x? There's no general formula for sixth powers ...

4
votes

1
answer

167
views

### Groups suitable for algebraic group factorizations of integers

Quoting Wikipedia on Algebraic-group factorisation algorithm
Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group defined modulo N whose ...

4
votes

0
answers

97
views

### Reducibility of $f(x)^{2^n}+1$ and $f(x)^{2^n}+g(x)^{2^n}$

Related to generalized Fermat numbers.
Let $f(x),g(x)$ be coprime polynomials with integer coefficients.
Assume that if $f(x)$ or $g(x)$ are of the form $h(x)^k$ then $k$ is power
of two.
Q1 Is it ...

1
vote

0
answers

36
views

### Systematic approach to Weierstrass factorization

If you want to calculate the Taylor expansion of a function, you only need to know the derivatives of the function at the point of expansion.
Is there a similar algorithmic approach that can be ...

3
votes

0
answers

117
views

### Integers with exactly three factor pairs whose successors are relatively prime

I am interested in the following problem, and will appreciate pointers around how it can be solved – partially or fully – and/or indicators around whether it is even tractable:
Characterize $N \in \...

9
votes

1
answer

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

1
vote

0
answers

125
views

### Factorization of argmax

We consider a function $f(s_{1:p}, a_{1:p})$, where $p>1$ is an integer, $s_{1:p}$ denotes $(s_1,\ldots,s_p)^\top \in R^p$, and $a_{1:p}$ denotes $(a_1,\ldots,a_p)^\top \in R^p$.
Question: What is ...

2
votes

1
answer

317
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{...

0
votes

0
answers

135
views

### A diophantine equation involving partial sums of exponentials similar than the equation in Fermat's Last Theorem

I'm curious about the following diophantine equation from my invention: I don't know if this is in the literature, I wrote it using creativity in an attempt to write a variant of the equation in ...

10
votes

1
answer

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

3
votes

0
answers

84
views

### Next smooth number

I want to find the next $n \in \mathbb{N}$ such that
$$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$
Where $\mathbb{P}_B$ is the set of primes not greater than $B$
I know that we can generate ...

1
vote

0
answers

103
views

### Need help interpreting this formula for the number of Goldbach partitions [closed]

1: Formula for the number of Goldbach partitions.
Let $g\left(n\right)$ denote the number of Goldbach partitions of even integer $2n$:
$$g_{\left(n\right)}=\sum_{3\leq p\leq2n-3}\left[\pi\left(2n-p\...

8
votes

1
answer

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

4
votes

1
answer

271
views

### Numbers with large prime exponents and the ABC conjecture

By Fermat's Last Theorem, there are no solutions to the Diophantine equation $a^n + b^n = c^n$ for $a,b,c > 0$ and $n>2$. Beal's conjecture allows the exponents to be different (but also $>...

5
votes

1
answer

364
views

### When $p(x)^2 \mid f(g(x))$?

Let $f(x),g(x),p(x)$ be non-constant polynomials with rational coefficients.
Is it true that for all $f$ exist $g,p$ such that $p(x)^2 \mid f(g(x))$?
Partial results:
$f(g(x))$ is divisible by square ...

3
votes

1
answer

181
views

### Do there exist irreducible elements in this domain?

I asked this question on MSE. Here also I have the same motive in the question.
Let $D= \{\,a_1x^{r_1} + \cdots + a_n x^{r_n} \, \vert \, a_i \in \mathbb{C} \text{ for } i= 1,2,\dots,n \text{ and ...

3
votes

1
answer

207
views

### The smallest solution to $2^{2k}-1=\text{powerful}$

Integer is powerful if all the exponents in its factorization are at least $2$.
Every powerful integer can be written in the form $a^2 b^3$.
For odd $k$, define $F(k)=(2^{2k}-1)=(2^k-1)(2^k+1)$.
This ...

3
votes

1
answer

438
views

### Must Mersenne numbers be divisible by arbitrary large primes with exponent one?

Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...

1
vote

2
answers

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

2
votes

0
answers

156
views

### Factoring integers of the form $n=p q^2$ using elliptic curves

We got argument and strong experimental support
that integers of the form $n=p q^2$ can
be factored using elliptic curves easier than general integers
Q1 Is this known?
Added This is known since at ...

0
votes

0
answers

170
views

### Functor factorization theorem and the structure of a functor

Corollary 4.8 in Awodey's book states that every functor $\mathcal F$:$\mathcal C$$\rightarrow$$\mathcal D$ factors $\mathcal F$ = $\mathcal H$ ◦ $\mathcal G$ where
$\mathcal G$ : $\mathcal C$$\...

1
vote

0
answers

85
views

### Smooth number pairs satisfying a congruence

Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$.
Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...

2
votes

1
answer

136
views

### Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?

1
vote

0
answers

60
views

### Factoring a complex function such that it is analytic in upper and lower plane

Consider this function $$\frac{k^{2}-\xi^{2}}{k^{2}+1}$$
which has singularities at $k=\pm i$, the strips where it is analytic are
$$
-1<k^{\prime \prime}<0 \quad \text { or } \quad 0<k^{\...

3
votes

1
answer

149
views

### Subobject- and factorization-preserving typings

Let $\rightarrowtail$ denote a monomorphism.
Given a morphism $A \stackrel{j}{\to} B$, I am interested in the (not necessarily unique) existence of a factorization $A \stackrel{j'}{\rightarrowtail} X \...

2
votes

0
answers

101
views

### Evidence of optimality of sieve algorithms

Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm.
The state ...

0
votes

1
answer

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

3
votes

0
answers

150
views

### The kronecker symbol and factorization of $n=\frac{B^N-1}{B-1}$

Let $n=\frac{B^N-1}{B-1}$. Assume $n$ is congruent to 3 modulo 4.
We have the following:
If $N$ is 1 modulo 4, then $N$ is quadratic residue modulo $n$
and $-N$ is quadratic non-residue. The square ...

0
votes

1
answer

71
views

### Factorization of a polynomial involving cosine into $m$ second-order factors [closed]

For each $m\in\mathbb{N}$ and fixed $a>0,\theta\in\mathbb{R}$, I want to factorizate the polynomial $p_m(x) = x^{2m} - 2a^m\cos (m\theta)x^m + a^{2m}$ into $m$ polynomials of second order. Using ...

7
votes

0
answers

136
views

### Factor-counting sequence

Define a non-negative integer sequence $\{\mathcal{F}_n\}$ as follows: start with 1 and, at each step, insert the number of entries already present in the sequence which are factors of the last one.
...

0
votes

0
answers

105
views

### Can factorization of very large numbers be aided by associating them with a series (described below) of quadratic polynomials?

My name is J. Calvin Smith. I graduated in 1979 with a Bachelor of Arts in Mathematics from Georgia College in Milledgeville, Georgia. My Federal career (1979-2012) in the US Department of Defense led ...

-1
votes

3
answers

118
views

### Are <sum, product, N> triplets unique and hard to solve? [closed]

This question comes from some reasoning I made myself about a "joke block chain" where every new block is labeled with a triplet <S, P, N> where where S = sum of the N transactions so ...

5
votes

2
answers

280
views

### Updates on a least prime factor conjecture by Erdos

In the 1993 article "Estimates of the Least Prime Factor of a Binomial Coefficient," Erdos et al. conjectured that
$$\operatorname{lpf} {N \choose k} \leq \max(N/k,13)$$
With finitely many ...

2
votes

1
answer

161
views

### For an integral domain $R$ when does $a^2 \equiv b^2 \bmod 4R$ imply $a \equiv b \bmod 2R$?

Suppose we have $a^2 \equiv b^2 \bmod 4R$ where $R$ is an integral domain. Under what conditions on $R$ can we conclude that $a \equiv b \bmod 2R$?
This would hold if $2 \in R$ is a prime or the ...

1
vote

0
answers

49
views

### Probability of factor of particular size

What is the probability that an integer $a$ picked uniformly in $[t/2,t]$ has a factor in $[t^{\alpha},2t^{\alpha}]$ where $\alpha\in(0,1)$? I am interested when $\alpha=1/3$ but if there is a general ...

0
votes

1
answer

95
views

### Could prime factorization of n!+1 using the general number field sieve be said to take subfactorial time?

I am interested in the prime factorization using the general number field sieve. This method is said to take subexponential time relative to the number of bits in a number. (Other algorithms are ...