The factorization tag has no usage guidance.

**3**

votes

**1**answer

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

**5**

votes

**1**answer

310 views

### Bounded domain matrix factorization

Assume we're trying to find $A\in [-1,1]^{n\times d}, B\in [-1,1]^{m\times d}$, from an observed matrix $C\in [-d,d]^{n\times m}$, where $C=AB^T$.
The goal is to return $\widehat A, \widehat B$ such ...

**1**

vote

**1**answer

115 views

### On a reciprocal of Ostrowski theorem on Newton polytopes and factorization

$\newcommand\KK{\mathbb{K}}$Let $\KK$ be any field and $f\in\KK[x_1,\dotsc,x_n]$ be a polynomial. Its support $S_f$ is the set $\{(e_1,\dotsc, e_n) : x_1^{e_1}\dotsb x_n^{e_n}$ has a nonzero ...

**2**

votes

**0**answers

134 views

### On reducible polynomials

Let $f(x),g(x)\in\Bbb Z[x]$ with $deg(f)>deg(g)$.
Given an integer $B$, is there any algorithm that runs in $\log^c |B|$ for some fixed $c\in \Bbb R$ to find a $h(x)\in\Bbb Z[x]$ (if one exists) ...

**9**

votes

**0**answers

97 views

### Factorisation in $\mathbb{N}[X]$?

Do we know an efficient algorithm 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 to combine some factor to ...

**8**

votes

**1**answer

163 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

105 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

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

**1**

vote

**0**answers

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

**3**

votes

**1**answer

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

**2**

votes

**0**answers

59 views

### When is Coppersmith method polynomial? (Factorization related)

From pari's implementation of Coppersmith method
zncoppersmith(P, N, X, {B=N}): finds all integers $x$ with $|x| \le X$ such that
$\gcd(N, P(x)) \ge B$. $X$ should be smaller than
$$\exp((\...

**6**

votes

**1**answer

174 views

### Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Is there a polynomial analog of this problem ...

**-2**

votes

**1**answer

200 views

### On odd perfect numbers $N$ given in the Eulerian form $N = {q^k}{n^2}$, Part II

I posted this question on MSE two days ago, but did not receive any responses. I have cross-posted it on MO, hoping it gets more attention here and that it is appropriate for this site.
A positive ...

**1**

vote

**0**answers

60 views

### On mid common divisor

Given $a,b\in\Bbb N$ of $n$ bits each and $c,d\in\Bbb N$ of $m$ bits each with $\frac{n}\beta<m<n$ with $\beta>1$ is there a better way to decide if $\exists e\in[c,d]\cap\Bbb N$ such that $e|...

**1**

vote

**3**answers

277 views

### Finding integer representation as difference of two triangular numbers

Since $n = \frac{n(n+1)}{2}-\frac{n(n-1)}{2}$, every natural number can be represented as the difference of two triangular numbers:
$ n = \frac{a(a+1)}{2}-\frac{b(b-1)}{2}$. Finding such a ...

**4**

votes

**2**answers

1k views

### Factoring and solving trinomials

Has the problem of factoring (over the rationals) the general trinomial $ax^n+bx^k+c$ with $a,b,c\in\mathbb{Z}$, $n,k\in\mathbb{N}, n>k>1$ been solved? By solved I mean a classification theorem ...

**1**

vote

**0**answers

34 views

### Most accurate separation of tensor product of matrices

Given a matrix $A \in \mathbb{R}^{n^m \times n^m}$, how I can find a set of $m$ matrices $\{B_i\}$ such that
$$\arg \min_{\{B_i\, \in\, \mathbb{R}^{n \times n}\}} \|A - B_1 \otimes \ldots \otimes B_m\...

**1**

vote

**0**answers

66 views

### Does Coppersmith's method always finds non-trivial factor of integers of the form $n=a(2^k b+1)$ assuming $1 < a<2^k b +1$ and $b < n^{1/4-0.05}$?

Got an argument and numeric evidence that pari's implementation
of Coppersmith's method finds non trivial factor of integers
of certain form under some assumptions very efficiently.
Three $5000$ bit ...

**6**

votes

**2**answers

488 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 = ...

**3**

votes

**1**answer

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

**10**

votes

**2**answers

503 views

### Why going to number fields in number field sieve help beat quadratic sieve?

To factor an $n$ bit integer number field sieve roughly takes $$e^{c{(\ln\ln n)^{\frac23}}({\ln n})^{\frac13}}$$ time while quadratic sieve takes $$e^{c{(\ln\ln n)^{\frac12}}({\ln n})^{\frac12}}$$ ...

**1**

vote

**1**answer

131 views

### Does this modification of the General Number Field Sieve factor integers?

The General Number Field Sieve
factors composite $n$ basically this way.
Select homogeneous polynomials with integer coefficients $f(x,y),g(x,y)$
s.t. $f(x,1),g(x,1)$ have common root modulo $n$ but ...

**1**

vote

**0**answers

76 views

### On variant of integer factorization

In the post on site cstheory.stackexchange on whether a variant of integer factorization
$$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ ...

**7**

votes

**2**answers

284 views

### A Different 2-factor in a graph

We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891).
My question is in ...

**2**

votes

**1**answer

72 views

### Simple decomposition of $K_{2n}-I$ into hamiltonian cycles

http://mathworld.wolfram.com/HamiltonDecomposition.html
In the 1890s, Walecki showed that complete graphs K_n admit a Hamilton decomposition for odd n, and decompositions into Hamiltonian cycles ...

**2**

votes

**1**answer

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

**9**

votes

**3**answers

2k 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 ...

**5**

votes

**0**answers

128 views

### On factorization algorithms for $\mathcal{O}[x]$

We know that $\mathsf{LLL}$ algorithm provides factorization procedure that runs in poly time for polynomials in $\Bbb Z[x]$ that are primitive.
What other rings $\mathcal{O}$ can we use instead of $\...

**7**

votes

**2**answers

334 views

### Theorems of the Galois groups of quintics appears not to work for the ${F}_{20}$ group determination

I am computing the Galois groups of quintics using the theorems from Ryan Kavanagh paper "On Irreducible Rational Quintics" using the decic resolvent ${P}_{10} \left({x}\right) = \prod\limits_{1 \le i ...

**5**

votes

**1**answer

165 views

### Dynamics of the distribution of prime factorization types in increasing intervals

I've tagged this as reference request as surely this question must be very well investigated, I just don't know how to look for it. Most likely the perfect answer will be in form of a keyword for ...

**0**

votes

**0**answers

82 views

### Is this factoring algorithm sufficiently efficient for some integers of special kind?

Basically the question is if $m$ is factored over the integers,
can it be relatively efficiently factored over $\mathbb{Z}[\sqrt{n}]$
where $n$ is not factored, but might be of special form?
Suppose ...

**3**

votes

**0**answers

245 views

### Possible $\mathsf{NP}$ complete problem from number theory

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-...

**0**

votes

**1**answer

186 views

### Find all possible rational pairs of a parametric sextic and all cases where it is reducible for either parameter

Find all possible rational solutions pairs $(z,a)$ of the equation
$a^6 + a^4 (-18368 + 9184 z - 2912 z^2) + a^2 (61702144 - 61702144 z + 36814848 z^2 - 10694656 z^3 + 1748992 z^4) - z^2 (...

**3**

votes

**1**answer

93 views

### $P_3$-factors for 3-regular, 3-connected cubic graphs

Suppose that $G=(V,E)$ is a simple graph.
We know if $G$ is 3-regular, 3-connected and $|V|=4k$ for some $k\in \mathbb{N}$, then $G$ has a $P_4$-factor.
Question. Let $G=(V,E)$ be 3-regular, 3-...

**8**

votes

**2**answers

6k 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,...

**1**

vote

**0**answers

66 views

### Factoring quaternion into three parts [closed]

I am faced with a problem where I have a quaternion which represents rotation and three arbitrary axis about which I can make rotations, thus three unit vectors.
What I would like to know is angles (...

**45**

votes

**4**answers

2k 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 $193707721 \times 761838257287$. There doesn't seem to be a historical ...

**4**

votes

**0**answers

238 views

### Analog of Euler's factoring technique

Is there an analog of Euler's Two Squares factoring theorem over polynomial rings $\Bbb Z[x]$ by considering a version for non-negative polynomials?
Euler's two squares factoring states that numbers ...

**7**

votes

**3**answers

711 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 $\...

**4**

votes

**2**answers

340 views

### Find all possible rational values of a parametric quartic such that it is reducible

Description: Given the following parametric quartic polynomial
$y^4 - 28 z y^3 - 14 (656 - 328 z + 83 z^2) y^2 +
4 z (-20464 + 10232 z + 3409 z^2) y +
91 (62208 - 62208 z + 41504 z^2 - 12976 z^3 +...

**1**

vote

**2**answers

292 views

### Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime number....

**0**

votes

**1**answer

228 views

### Find all possible rational values of the parameter of a parametric cubic such that it is reducible

Description: Given the following parametric cubic polynomials ${E}^{3}
- 15\, {\beta}_{\pm}\, {E}^{2} - 3 \left({71\, {\beta}_{\pm}^{2} + 352\, {\beta}_{\mp}}\right) E
+ 135\, {\beta}_{\pm} \left({5\...

**4**

votes

**3**answers

495 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 (...

**12**

votes

**2**answers

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

**2**

votes

**3**answers

2k views

### Finding the greatest (smallest) factor of a number smaller (greater) than another number

Instead of iterating through all the possible numbers, is there a better way to find the greatest factor of a number $n$, such that it is less than $m$ ($m$ < $n$). Similarly how does one find the ...

**11**

votes

**0**answers

325 views

### Do the coefficients of these irreducible polynomials always become periodic?

Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_n\ne0$.
Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+...

**18**

votes

**1**answer

2k views

### Difficulty of factoring a Gaussian integer (compared to factoring its norm)

Given a Gaussian integer $G=a+ib$, with $gcd(a,b)=1$, a well-known strategy for factoring $G$ is to first compute its norm $N(G)=a^2+b^2$, factor the norm and finally recover the correct generator ...

**2**

votes

**0**answers

110 views

### counting irreducible factors

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer.
Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ ...

**2**

votes

**1**answer

134 views

### Which nonnegative matrices have exact nonnegative matrix factors of smaller dimensionality?

The nonnegative matrix
$V = \left( \begin{array}{cc}
1 & 1 \\
1 & 1 \end{array} \right)$
has nonnegative matrix factors $W = \left( \begin{array}{c} 1 \\ 1 \end{array} \right)$ and $H = \...

**1**

vote

**0**answers

124 views

### Puzzling CAS-detected factorization by cyclotomic polynomials [closed]

If one factorizes by CAS the expression $$x^{\frac{m(m+1)}{2}}\prod_{k=1}^m(x^k+(\frac{1}{x})^k)$$ a puzzling perfect factorization seems to be possible for all natural values of $m$.
E.g. for $m=5$...