The factorization tag has no wiki summary.

**12**

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

**0**

votes

**1**answer

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

**8**

votes

**2**answers

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

**3**

votes

**2**answers

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

**3**

votes

**3**answers

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

**4**

votes

**0**answers

58 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

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

**-6**

votes

**1**answer

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

**3**

votes

**1**answer

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

**5**

votes

**1**answer

183 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

**0**answers

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

**0**

votes

**1**answer

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

**6**

votes

**4**answers

409 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

330 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

**3**answers

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

**7**

votes

**2**answers

306 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

**0**answers

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

**5**

votes

**1**answer

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

**7**

votes

**3**answers

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

**1**

vote

**3**answers

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

**5**

votes

**2**answers

148 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

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

**2**

votes

**0**answers

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

**11**

votes

**6**answers

1k views

### Seeking Noetherian normal domain with vanishing Picard group but not a UFD

Once again, the question says it all.
My motivation is the article on factorization I am writing. I want to explain (as well as to understand!) why for normal Noetherian domains of dimension greater ...

**0**

votes

**2**answers

182 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

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

**11**

votes

**2**answers

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

**0**

votes

**1**answer

625 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

251 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) = ...

**15**

votes

**11**answers

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

406 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

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

**2**

votes

**3**answers

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

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

**5**

votes

**1**answer

381 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

500 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

**7**

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

393 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

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

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

**1**

vote

**2**answers

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

**-2**

votes

**1**answer

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

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

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

**16**

votes

**1**answer

930 views

### Factoring Integers using Complex Integrals

Suppose $n$ is an integer and we wish to factor it. As a special case we have $n = pq$ with $p,q$ distinct primes. The problem: factoring $n$ via complex analysis tools
Background
I have been ...

**2**

votes

**1**answer

427 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

489 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

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

**2**

votes

**1**answer

611 views

### What are the chances of finding a small factor?

EDIT 2011.05.09
Thanks to Junkie and Tapio Rajala for checking on me. While most of the candidates
referred to below have small factors, the "large" small factors I list below are incorrect. Also, ...