Questions tagged [factorization]
For questions about factorization, the decomposition of mathematical objects (e.g. natural numbers, polynomials) into products of smaller objects (e.g. primes, lower degree polynomials).
256
questions
116
votes
5
answers
32k
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 $193{,}707{,}721\times 761{,}838{,}257{,}287$. There doesn't seem to be ...
44
votes
1
answer
17k
views
Conjecturally unsafe RSA primes $p=27a^2+27a+7$
We got strong numerical evidence that primes of the form $p=27a^2+27a+7$
are unsafe for cryptographic purposes since they can be found in the factorization.
Consider the following generic factoring ...
33
votes
7
answers
3k
views
On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$
Let $n = 2m$ be an even integer and let $F_n(X)$ be the polynomial $$F_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}.$$ I observed (but cannot prove) that the polynomial $F_n$ is always divisible by $...
26
votes
4
answers
2k
views
Structures in the plot of the “squareness” of numbers
(This is based on an earlier MSE posting,
"Structures in the plot of the “squareness” of numbers.")
My main question is to explain the structural features of this plot:
This is a plot of what I call ...
25
votes
1
answer
6k
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 ...
23
votes
1
answer
3k
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 ...
22
votes
11
answers
8k
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 ...
20
votes
1
answer
2k
views
Circle $x^2 + y^2 = n!$ doesn't hit any lattice points for any $n$ except for $0$, $1$, $2$ and $6$ or does it?
I stumbled across the following problem in high school:$$
x^2 + y^2 = n!
$$
I tested it within my laptop capabilities, watched a 3b1b video Pi in prime regularities, where he explains how to find the ...
18
votes
2
answers
2k
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 ...
17
votes
0
answers
417
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}+...
15
votes
6
answers
2k
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 ...
15
votes
2
answers
937
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 ...
15
votes
1
answer
585
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 $P,...
14
votes
2
answers
1k
views
How divisible is the average integer?
I don't know any number theory, so excuse me if the following notions have names that I'm not using.
For a positive natural number $n\in{\mathbb N}_{\geq 1}$, define $Log(n)\in{\mathbb N}$ to be ...
14
votes
2
answers
1k
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 ...
13
votes
2
answers
5k
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 = ...
13
votes
3
answers
3k
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 ...
13
votes
1
answer
640
views
Would efficient factoring have any *other* useful applications?
This question is certainly somewhat opinion-based, but hopefully not hopelessly so.
The granddaddy of all applications for an efficient period finding or factoring capability (e.g. Shor's algorithm) ...
13
votes
1
answer
316
views
Factorization of polynomials into "shortest possible" factors
A while ago I asked a question at Mathematica.SE about how to factorize a polynomial into terms with as few monomials as possible each. I now realized that I actually do not know what is rigorous ...
12
votes
5
answers
2k
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!)
...
12
votes
1
answer
627
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 ...
12
votes
3
answers
3k
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 not----...
12
votes
0
answers
166
views
Are there efficient algorithms 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 then to combine some factor to find a factorisation in $\mathbb{N}[X]$. Note that the ...
11
votes
1
answer
1k
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 ...
11
votes
2
answers
1k
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}}$$ ...
11
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
10
votes
4
answers
4k
views
Consecutive numbers with n prime factors
Let $P(m,n)$ mean that there is a number, $M$, such that starting with $M$ there are $m$ consecutive numbers each having exactly $n$ distinct prime factors. Is it obvious that $P(m,n)$ is true for ...
10
votes
3
answers
2k
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 $\...
10
votes
2
answers
17k
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,...
10
votes
1
answer
306
views
Fixpoints of $m\longmapsto \mathrm{rad}(\phi(m^2))$ under iteration
Given a strictly positive integer $m$ let $\alpha(m)=\mathrm{rad}(m\phi(m))$
be the radical (product of all distinct prime divisors) of the product of $m$ and of Euler's totient function $\phi(m)=m\...
10
votes
3
answers
3k
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
...
10
votes
1
answer
291
views
$2$-adic valuation of Schur $P$-functions in the power-sum basis
For a partition $\lambda$, let $P_\lambda$ be the Schur $P$-functions (case $t=-1$ of Hall-Littlewood symmetric functions) and let $p_\lambda=p_{\lambda_1}p_{\lambda_1}\cdots p_{\lambda_k}$ be the ...
9
votes
2
answers
1k
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 ...
9
votes
1
answer
675
views
Hensel's lemma, Bezout's identity, and the integers
Factorization in the ring $\mathbb{Z}[x]/(x^2+1)\mathbb{Z}[x]\cong \mathbb{Z}[i]$ is well known. For instance, $5$ and $13$ (and any prime $\equiv 1\pmod{4}$) are no longer prime.
The factorization ...
9
votes
1
answer
566
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 ...
9
votes
2
answers
533
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 ...
9
votes
3
answers
971
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 ...
9
votes
1
answer
354
views
Adding a multiple of the Identity to a LU factorized matrix
Suppose a square, dense, symmetric matrix $A$ has been factorized into $L$ and $U$ components by performing a LU decomposition. Now let $B = A+\lambda I$. Is there any way to efficiently compute the ...
8
votes
2
answers
821
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 $\...
8
votes
2
answers
734
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. ...
8
votes
2
answers
770
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 ...
8
votes
1
answer
233
views
Functions over monoids which factor in two different ways
This is a follow-up question to this MO question, which was asked by Richard Stanley in a comment to my answer there.
Let $S$ be a commutative monoid and $f(x_1, \dots, x_n)$ be a function from $S^n$ ...
8
votes
1
answer
569
views
Can a squarefree polynomial in K[x,y] not be squarefree in K[[x]][y]?
In a UFD, as usual one says that $f$ is square-free if it is not divisible by the square of any irreducible element, i.e., if it has no multiple factor.
An polynomial $f\in k[x,y]$ can have more ...
8
votes
0
answers
151
views
A factorization game
This is a toy version of a problem I have posted recently.
Imagine playing the following game. You choose a polynomial $B$ over a finite field $\mathbb F_p$, of degree $\deg B\le p-1$ (where $p$ is a ...
7
votes
3
answers
9k
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 ...
7
votes
4
answers
938
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 ...
7
votes
1
answer
375
views
$\log \log p / \log \log n$, where $p|n$, gets equidistributed in [0,1] (for almost all $n$)
According to Hardy-Ramanujan/Erdős-Kac we know that usually there are $\sim\log\log n$ prime numbers in a factorization. But if you pick up a natural number at random, and you factor it, what is the ...
7
votes
2
answers
531
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 ...
7
votes
1
answer
299
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 $N+2,\...
7
votes
1
answer
981
views
Results on the largest prime factor of $2^n+1$
A work of Cameron Stewart (the paper has appeared in Acta Mathematica), proving a conjecture of Erdos, Stewart shows that
the largest prime factor of $2^n-1$ is at least
$n \times \exp\Big( \frac{\...