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

Filter by
Sorted by
Tagged with
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 ...
David E Speyer's user avatar
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 ...
joro's user avatar
  • 24.2k
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 $...
WhatsUp's user avatar
  • 3,232
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 ...
Joseph O'Rourke's user avatar
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 ...
user16007's user avatar
  • 780
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 ...
minar's user avatar
  • 492
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 ...
Kevin Acres's user avatar
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 ...
Betydlig's user avatar
  • 343
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 ...
Aleks Vlasev's user avatar
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}+...
Wolfgang's user avatar
  • 13.2k
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 ...
Pete L. Clark's user avatar
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 ...
Student's user avatar
  • 153
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,...
mikhail skopenkov's user avatar
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 ...
David Spivak's user avatar
  • 8,549
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 ...
James Cranch's user avatar
  • 3,034
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 = ...
epsilone's user avatar
  • 313
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 ...
ARupinski's user avatar
  • 5,181
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) ...
tparker's user avatar
  • 1,243
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 ...
მამუკა ჯიბლაძე's user avatar
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!) ...
Joseph O'Rourke's user avatar
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 ...
MrB's user avatar
  • 399
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----...
John Bentin's user avatar
  • 2,427
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 ...
Sylvain Lefuste's user avatar
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 ...
Tom De Medts's user avatar
  • 6,494
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}}$$ ...
user avatar
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 ...
Alec Jacobson's user avatar
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 ...
Darrell Plank's user avatar
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 $\...
GreginGre's user avatar
  • 183
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,...
César's user avatar
  • 339
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\...
Roland Bacher's user avatar
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 ...
joro's user avatar
  • 24.2k
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 ...
Antoine Labelle's user avatar
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 ...
Wolfgang's user avatar
  • 13.2k
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 ...
Pace Nielsen's user avatar
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 ...
Arrow's user avatar
  • 10.3k
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 ...
Wolfgang's user avatar
  • 13.2k
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 ...
The Masked Avenger's user avatar
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 ...
César's user avatar
  • 339
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 $\...
Adam Hughes's user avatar
  • 1,039
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. ...
Sadeq Dousti's user avatar
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 ...
Mohemnist's user avatar
  • 400
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$ ...
Tony Huynh's user avatar
  • 31.5k
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 ...
Santiago's user avatar
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 ...
Seva's user avatar
  • 22.8k
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 ...
Xander Faber's user avatar
  • 1,159
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 ...
Craig Feinstein's user avatar
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 ...
Luca Ghidelli's user avatar
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 ...
Lorenz H Menke's user avatar
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,\...
Wolfgang's user avatar
  • 13.2k
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{\...
Michael's user avatar
  • 267

1
2 3 4 5 6