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

**4**

votes

**1**answer

192 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

157 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

126 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

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

**2**

votes

**0**answers

186 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

125 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

185 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

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

**5**

votes

**1**answer

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

**31**

votes

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

260 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

150 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

67 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

62 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

163 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

385 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

16k 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

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

**0**

votes

**0**answers

128 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

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

**0**

votes

**0**answers

115 views

### What relation does this problem have to Number Field Sieve?

In here Small geometric progression modulo N it is asked 'Must there exist a 5-term geometric progression $\lbrace a_0,a_1,a_2,a_3,a_4\rbrace$ (mod $N$) such that each term is $O(N^{2/3})$?
We also ...

**2**

votes

**0**answers

137 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^...

**0**

votes

**0**answers

69 views

### Finding numbers in specified interval with specified number of divisors

Problem: given an interval $[M_0,M_1]\subset Z_+$ and $D\in Z_+$, generate list of $x\in [M_0,M_1]$ such that $\tau(x)=D$. (here, $\tau$ is the number-of-divisors function).
Question 1: is there any ...

**4**

votes

**2**answers

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

**0**

votes

**0**answers

47 views

### how two orthonormal function multiplication can be represented as a function of their arguments difference

Can a pair of orthonormal signals ${{\phi }_{k}}\left( t \right),\phi _{n}^{{}}\left( t \right)$ admit the following relation
${{\phi }_{k}}\left( t \right)\phi _{n}^{*}\left( s \right)+{{\phi }_{...

**7**

votes

**1**answer

291 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

130 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

139 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

244 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

81 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

222 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

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

**0**

votes

**1**answer

90 views

### Upper bound for tuple of exponents of prime factorization

Let $a(n)$ be the $k$-ary tuple of the exponents of the prime factorization of $n$. For example,
$$a(5184)=a(2^{6}⋅3^{4})=(6, 4), a(65536)=a(2^{16})=(16).$$
Formally, let $p_{1}^{a_{1}}, p_{2}^{a_{2}...

**2**

votes

**1**answer

200 views

### Upper bound for product of exponents of prime factorization

Let $p(n)$ be the product of the exponents of the prime factorization of $n$. For example,
$$p(5184)=p(2^{6}\cdot 3^{4})=24,\qquad
p(65536)=p(2^{16})=16.$$
Is $p(n) = O(\log^{k}(n))$ for some constant ...

**-2**

votes

**3**answers

189 views

### Is it possible to show that :for $n \geq 1:\sigma(n!-1) $ never be prime and why $\sigma(n!-1)\bmod 10 $ at most is $0$?

This question is related to my question here , I w'd like to check if $n \geq 1:\sigma(n!-1) $ never be prime according to some computations which i did in wolfram alpha to come up with parity of sum ...

**1**

vote

**1**answer

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

**26**

votes

**4**answers

2k views

### Structures in the plot of the “squareness” of numbers

(This is based on an earlier MSE posting,
"Structures in the plot of the “squareness” of numbers.")
My main question is to explain the structural features of this plot:
This is a plot of what I call ...

**2**

votes

**0**answers

82 views

### Factorially closed subrings

Lemma 3.2 says: Let $A$ be a UFD. Let $R \subseteq A$ be a subring of $A$ such that
$R^* = A^*$.
The following conditions are equivalent:
(i) Every irreducible element of $R$ remains irreducible in $...

**7**

votes

**2**answers

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

**4**

votes

**0**answers

149 views

### Unique factorization for the semigroup generated by {2cos(π/n) | n>3}?

Let $S$ be the multiplicative semigroup of numbers generated by $B=\{ 2cos(\frac{\pi}{n}) \mid n \ge 4 \}$.
Question: Does every number of $S$ factorize uniquely (up to perm.) as a product of ...

**2**

votes

**1**answer

232 views

### Is there a “small $\omega$” number theorem?

In my studies of how primes jump (search this forum for a link), a question has been raised which may have been studied. Can anyone jump-start my literature search with references regarding the ...

**3**

votes

**1**answer

221 views

### Is a category regular iff extremal epis and monomorphisms are a strong factorization system?

I'm reviewing some notes of mine on regular categories to try and get a better feel for regular, strong, and extremal epimorphisms, and this leads me to ask: is a category $\mathsf C$ regular if and ...

**7**

votes

**1**answer

608 views

### Results on the largest prime factor of $2^n+1$

A work of Cameron Stewart (the paper has appeared in Acta Mathematica), proving a conjecture of Erdos, Stewart shows that
the largest prime factor of $2^n-1$ is at least
$n \times \exp\Big( \frac{\...

**3**

votes

**1**answer

190 views

### Irreducibility of family of polynomials

Consider the following family of polynomials over $\mathbb{Q}$:
$$f_n = x^n - x^{n-1} - \dots - 1$$
Notice that these polynomials satisfy the recurrence
$$ f_{n+1} = x f_n - 1 $$
I would like to ...

**11**

votes

**0**answers

154 views

### Are there efficient algorithms 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 then to combine some factor to find a factorisation in $\mathbb{N}[X]$. Note that the ...

**9**

votes

**1**answer

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

**0**

votes

**0**answers

124 views

### More generalized RSA construction

Is there a way to construct RSA type cryptosystem over general number rings?
Can Number Field Sieve technique be applied here?

**2**

votes

**2**answers

84 views

### Solution of $\left(\Gamma(x+c)/ \Gamma(x+d)\right)y^d/y^c = {\rm const}$

When I try to solve $F(x,y)= \Gamma(x+c)/\Gamma(x+d) y^d/y^c = {\rm const}$,
I find that $y = p x + q$ satisfies the above equation, whith specific $p$ and $q$ constants for the given constants $c$ ...

**3**

votes

**1**answer

127 views

### Reference Request on the existence of $k$ satisfying $P(\Phi_d(2))^k \gt \Phi_d(2)$ for all $d$

I am working my way through the literature regarding the following conjecture: There is a positive integer $k$ such that for all positive integers $d$,
$$P(\Phi_d(2))^k \gt \Phi_d(2).$$
I am ...

**1**

vote

**0**answers

110 views

### Expressing Numbers with a Minimal Sum in Powers of 2 [closed]

The first 64 bits of pi are:
11.00100100001111110110101010001000100001011010001100001000110100
Computer multiplication can be sped up by looking for patterns and ...