The tag has no usage guidance.

learn more… | top users | synonyms

5
votes
1answer
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 ...
11
votes
0answers
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 = ...
9
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
552 views

Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
114 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} ...
3
votes
0answers
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
0answers
112 views

Coim factorization of a morphism in a complete well-powered category

In a complete, cocomplete and well-powered category with zero object consider the canonical factorization of a morphism $f=k\circ \mathrm{Coim}(f)$. Does cocomplete+complete+well-powered guarantee ...
3
votes
0answers
596 views

Least Prime Factor in a sequence of 2n consecutive integers

I was thinking about consecutive integers and I wondered if anyone had done work exploring whether a sequence of $2n$ consecutive integers (i.e. 101,102,103,...,100+2n) always contains at least one ...
3
votes
0answers
156 views

Pulling out factors in a Noetherian Domain

Let $R$ be a Noetherian domain (not-necessarily commutative), and let $S$ be a Noetherian subring of $R$. An element $r\in R$ is left $S$-irreducible if, for any $s\in S$ and $r' \in R$ with $sr'=r$, ...
2
votes
0answers
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 ...
2
votes
0answers
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
0answers
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
0answers
162 views

Elements of low multiplicative order and computing square roots modulo composites

In "On computing factors of cyclotomic polynomials", Richard P. Brent gives the identity $$ 4 \Phi_n(x) = A_n(x)^2 - (-1)^{(n-1)/2} n B_n(x)^2 \qquad (1) $$ where $n$ is odd squarefree and $A_n,B_n$ ...
1
vote
0answers
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
0answers
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
0answers
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 ...
1
vote
0answers
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{ ...
0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...