The factorization tag has no wiki summary.

**2**

votes

**1**answer

94 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

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

**3**

votes

**0**answers

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

**6**

votes

**2**answers

209 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

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

**0**

votes

**1**answer

113 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

69 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

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

**3**

votes

**3**answers

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

**-6**

votes

**1**answer

147 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|})$.
...

**0**

votes

**1**answer

119 views

### Aurifeuillean factorization with number fields

Basically the question is if number fields can be used
in Aurifeuillean factorization.
Probably this is easy and the answer is "no".
Let $f,g \in \mathbb{Z}[x], a \in \mathbb{N}$.
Let $f(x)$ and ...

**8**

votes

**2**answers

516 views

### runs of consecutive non squarefree integers

This question gained no attention at Math SE.
Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us ...

**6**

votes

**4**answers

428 views

### Are there any fast algorithms for factoring integers that don't work by searching for smooth numbers?

All of the fast algorithms that I have seen which factor integers work by searching for smooth numbers. Are there any fast algorithms for factoring integers that don't work by searching for smooth ...

**4**

votes

**1**answer

370 views

### The number of distinct prime factors of $n\in\mathbb N$

Let $\omega(n)$ be the number of distinct prime factors of a natural number $n$.
Note that $\omega(n)=0\iff n=1$, and that $\omega(24)=\omega(2^3\cdot 3^1)=2\ (\not = 4)$.
(For more details, you ...

**7**

votes

**0**answers

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

**5**

votes

**1**answer

186 views

### Large gaps between consecutive irreducible polynomials with small heights

For a prime gap of length at least $n$, a trivial upper bound for its first occurrence is $N=n!$ or $N=lcm(2,\dots,n)$. A bit better is $N=p_1\cdots p_n$ where $p_k$ is the $k$th prime, as then ...

**7**

votes

**2**answers

325 views

### Number of ways to write an integer as a product of irreducibles

Is there any way to tell the number of distinct ways to factor $a\in\mathcal{O}_k$ (up to units, of course) when $k$ is not a PID? A simple investigation in $\mathbb{Q}(\sqrt{-5})$ with integer ring ...

**3**

votes

**1**answer

341 views

### Proving conditions on $(r+s)^2 \mid (4r^4+1)$, related to Pell oblongs

While working on another problem (Solving the quartic equation $r^4 + 4r^3s - 6r^2s^2 - 4rs^3 + s^4 = 1$), I came across a question which seems to be of [semi-] independent interest.
Conjecture. If ...

**3**

votes

**0**answers

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

**6**

votes

**1**answer

367 views

### Using the decomposition $641 = 5^4 + 2^4$ to factor $F_5$

The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it:
Problem 19.5 (p. 224) ...

**15**

votes

**1**answer

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

**5**

votes

**2**answers

150 views

### Collision polynomials

Consider $P_n(x)$ polynomials defined through the recurrence relations
$$P_n(x)=2(1-x)P_{n-1}(x)-(1+x)^2P_{n-2}(x),$$ with $P_0(x)=1$ and $P_1(x)=1-3x$.
In fact, the explicit solution of these ...

**3**

votes

**0**answers

142 views

### Significance behind splitting of (x+y)^7-(x^7+y^7)? [closed]

A quick check via third roots of unity establishes$$(x+y)^7-(x^7+y^7) = 7xy(x+y)(x^2+xy+y^2)^2$$
Some questions:
What is the significance of this factorization?
Does it have any connection to the ...

**7**

votes

**3**answers

745 views

### $\omega(p^n - 1)$ as $n \rightarrow \infty$

Although I am also interested in the number of distinct prime factors (not counting
multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime
factors (with multiplicity) of the ...

**2**

votes

**0**answers

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

**0**

votes

**2**answers

198 views

### Generating 3SAT circuit for Integer factorization example

I read somewhere that 3SAT can be used to solve Integer Factorization.
If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...

**0**

votes

**1**answer

213 views

### How can an integer be factorized as n*m so that n^m has the highest value. [closed]

Given an integer d, is there a way of finding max(n^m), where d=n*m, except brute-forcing it ?
n and m don't have to be primes.
For example:
The number 12 can be factorized into two factors as: ...

**0**

votes

**1**answer

700 views

### Can infinite polynomials be expressed as a product of its linear factors?

Background:
In the 1700s, Euler solved the Basel Problem, which was to solve $\sum_{n=1}^\infty\frac{1}{n^2}$ in closed-form. Euler showed that it was equal to $\frac{\pi^2}{6}$ by first expressing ...

**2**

votes

**2**answers

253 views

### Factorization of antisymmetric bounded holomorphic functions

A basic principle in complex function theory is that one can split off zeros of holomorphic functions in a similar way as for polynomials: If $f$ is holomorphic near $0$ and $f(0) = 0$, then $f(z) = ...

**16**

votes

**11**answers

3k views

### Fastest way to factor integers < 2^60

I've been running a search for Mordell curves of rank >=8 for about 12 months and have identified approximately 280,000 curves in our archivable range, amongst many millions that aren't.
For this ...

**5**

votes

**0**answers

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

**2**

votes

**3**answers

507 views

### Groups of Rational Points on Gaussian Circles

Let a gaussian circle $C_R$ be any circle defined by the equation:
$$x^2+y^2 = R, (x,y) \in \mathbb{R}^2$$, where $R$ is the norm of a gaussian integer ($R=a^2+b^2, (a,b) \in \mathbb{Z}^2$). IF $R$ ...

**1**

vote

**3**answers

508 views

### For any prime $p$, is there $C$ such that if $x\ge C$, then all but one integer among $x+1, x+2, \dots, x+p$ has Greatest Prime Factor $> p$

I apologize if this is a naive question about greatest prime factors (gpf). I was thinking about the sequence of integers where $\mathrm{gpf}(x) \le p$ where $p$ is any prime.
Clearly, as $x$ ...

**2**

votes

**3**answers

2k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...

**11**

votes

**3**answers

929 views

### What is known about the polynomial factorization of power series?

Some power series factorize; $1+\sum_{n=1}^\infty x^n=\prod_{n=1}^\infty (1+x^{2^n})$ and $1+\sum_{n=1}^\infty x^{2n}/(2n+1)!=\prod_{x=1}^\infty (1+x^2/n^2\pi^2)$ for example; while others do ...

**11**

votes

**2**answers

692 views

### Saying things rapidly about integer factorisations

Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...

**5**

votes

**1**answer

398 views

### Divisibility and factorization in rings that are not integral domains

In my course notes for an undergraduate course "Algebra I", I wrote at the point when I'm introducing the notion of divisibility in rings (in a section on unique factorization):
We want to study ...

**1**

vote

**2**answers

518 views

### find the minimum difference between the factors of a number

Given a number c, what is the smartest way to find |x - y| such that x * y =c and |x - y| is minimum

**8**

votes

**5**answers

1k views

### Polynomials all of whose roots are rational

I have two questions about the class of integer-coefficient polynomials all of whose roots are rational.
I asked this at MSE, but it attracted little interest (perhaps because it is not interesting!)
...

**2**

votes

**5**answers

395 views

### Factoring a certain quartic mod primes

Let $h(x)=x^4+12x^3+14x^2-12x+1$, and let $p>5$ be a prime.
I want to show $h(x)$ factors into 2 quadratics mod $p$ if $p \equiv 9,11$ mod 20, while
$h(x)$ factors mod $p$ into 4 linear factors if ...

**12**

votes

**1**answer

408 views

### Is the ring of quaternionic polynomials factorial?

Denote by $\mathbb{H}[x_1,\dots,x_n]$ the ring of polynomials in $n$ variables with quaternionic coefficients, where the variables commute with each other and with the coefficients. Two polynomials ...

**-2**

votes

**1**answer

426 views

### Are these polynomials irreducible over ring Z of integers ?

Is it true that polynomials of the form :
$ f(x)= x^n+x^{n-1}+...+x^{k+1}+ax^k+ax^{k-1}+...a$
where $gcd(n+1,k+1)=1$ and $ a\in \mathbb{Z^{+}} $
are irreducible over ring $\mathbb{Z} $ of ...

**1**

vote

**2**answers

369 views

### Finding a divisor of a number under a constraint

Given 2 positive integers $n, l$ with $ l \leq n$, I am looking for a way to find the largest divisor $d$ of $n$, such as $d \leq l$.
Assume $n$ has too many divisors for an exhaustive search.
Thanks ...

**12**

votes

**1**answer

2k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...

**1**

vote

**2**answers

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

**2**

votes

**1**answer

434 views

### Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them

If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the index calculus algorithm used for Discrete Log calculation in any serious way?
Other connections
$1.)$ ...

**6**

votes

**1**answer

492 views

### Is this pleasing polynomial irreducible?

Let:
$f(x)=x^n+2x^{n-1}+3x^{n-2}+4x^{n-3}+\ldots + (n-1)x^2+nx+(n+1)$.
Is $f(x)$ irreducible?
In light of the answers to this question, I now know that this is true when $n+1$ is prime. What about ...

**7**

votes

**2**answers

605 views

### Factoring some integer in the given interval

I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms.
Let N be a positive integer. Is there an efficient (i.e. ...

**2**

votes

**1**answer

237 views

### 10 factors for x^2 coefficient in quadratic sieve?

I wrote a quadratic sieve and I tried plugging in all the same parameters as the wikipedia article says msieve uses: http://en.wikipedia.org/wiki/Quadratic_sieve#Parameters_from_realistic_example
It ...

**5**

votes

**3**answers

1k views

### Reduction from factoring to solving Pell equation

The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims
There are reductions from factoring to solving Pell’s equation, and from solving Pell’s
...