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

187 questions
Filter by
Sorted by
Tagged with
149 views

95 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 ...
119 views

106 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 ...
274 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 ...
160 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 ...
47 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 ...
83 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 ...
105 views

### Primes which do not divide certain homogeneous polynomials

It is known that if $x^2 + y^2 = z^2$ is a primitive Pythagorean triplet then $z$ is not divisible by any prime of the form $4k-1$. The following is a generalization of this classical result which ...
49 views

134 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 ...
63 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 ...
99 views

144 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?
137 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 ...
### 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 ...