The factorization tag has no usage guidance.

**9**

votes

**0**answers

86 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

153 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

104 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

74 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

114 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

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

**2**

votes

**0**answers

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

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

63 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

403 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

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

**1**

vote

**1**answer

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

**1**

vote

**3**answers

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

**7**

votes

**2**answers

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

**10**

votes

**2**answers

488 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}}$$ ...

**2**

votes

**1**answer

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

**5**

votes

**0**answers

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

**6**

votes

**1**answer

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

**7**

votes

**2**answers

332 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

164 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

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

**3**

votes

**1**answer

92 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, ...

**1**

vote

**0**answers

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

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

**44**

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

**-2**

votes

**1**answer

194 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

**2**answers

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

**4**

votes

**2**answers

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

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

**4**

votes

**3**answers

487 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

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

**1**

vote

**1**answer

108 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

**1**answer

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

**4**

votes

**0**answers

236 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

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

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

**0**answers

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

**2**

votes

**1**answer

131 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

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

**4**

votes

**0**answers

119 views

### More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...

**7**

votes

**2**answers

290 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**3**

votes

**2**answers

390 views

### Degrees of factors of polynomial $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$

I’m facing the problem of factoring polynomials of type $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$ and the degrees of factors seem to be quite special. For example, according to my experimental results ...

**5**

votes

**1**answer

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

**4**

votes

**0**answers

115 views

### Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form:
\begin{equation}
A =
\left[\begin{array}{c|c}
...

**0**

votes

**0**answers

94 views

### What algebras does the hidden subgroup problem for finite abelian groups apply to?

Shor's algorithm is said to solve the hidden subgroup problem for finite Abelian groups, of which factoring and the discrete logarithm problem for integers belong to. Apparently the HSP for finite ...

**4**

votes

**3**answers

418 views

### Distinct primitive factorizations over integers of number fields

I am curious about the following.
Let $K$ be a number field. For any $a \in \mathcal{O}_K$ in its ring of integers, let $N(a)$ be zero if there exist elements $b, c \in \mathcal{O}_K \setminus ...

**-5**

votes

**1**answer

344 views

### Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that $P-Q \neq 1$ and $N=P^2-Q^2$ [closed]

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that:
$P-Q \neq 1$ and $N=P^2-Q^2$
I am assuming that the best known solution to this problem runs at $O(2^{|N|})$.
...