The factorization tag has no wiki summary.

**2**

votes

**1**answer

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

**7**

votes

**1**answer

503 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

610 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

244 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

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

**3**

votes

**0**answers

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

**16**

votes

**1**answer

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

**5**

votes

**0**answers

525 views

### Is integer factorization harder than RSA ($n=pq$) factorization? [closed]

This is a repost. I could not get a precise answer on math.SE and cstheory.SE
Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers ...

**2**

votes

**1**answer

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

**2**

votes

**2**answers

480 views

### when does a regular graph have a 1-factorization?

Is there a sufficient condition for a regular graph to have a 1-factorization (i.e. being able to pack all of its edges into disjoint perfect matchings, and excluding one vertex if the number of ...

**0**

votes

**1**answer

130 views

### “locally” factoring subgroups of Lie groups

I'm not really a math person, and apologize if the question here is too simple. I've ended up with the following type of question for a few Lie groups, but state it for SO(n).
I start with a subgroup ...

**7**

votes

**3**answers

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

**2**

votes

**2**answers

498 views

### Second stage of elliptic curve factorization via random walk/Pollard's rho in constant (or low) memory?

The second stage of elliptic curve factorization has the drawback of large memory usage.
Let $n=pq$, $E(\mathbb{Z}/n\mathbb{Z})$ is elliptic curve and $P$ point on $E(\mathbb{Z}/n\mathbb{Z})$.
On ...

**1**

vote

**1**answer

312 views

### Cartesian factorization of a finite set of n-tuples

I'm interested in factoring a finite set of $n$-tuples as the Cartesian product of two "factor sets", of which the first factor is itself the Cartesian product of some of the set's projection images, ...

**2**

votes

**1**answer

646 views

### A subring question (revised)

Hello,
Let $K/{\mathbb Q}$ be a finite extension which is not necessarily Galois, and ${\mathcal O}$ be the ring of integers of $K$. Let $p$ be a prime in ${\mathbb Q}$ and let
$p {\mathcal ...

**7**

votes

**4**answers

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

**0**

votes

**2**answers

752 views

### Prime factorization theory

Firstly, let me divulge. I've been doing a lot of research on the summation of two coprime numbers and unfortunately have failed to come up with the properties I'm seeking; it is my hope that someone ...

**7**

votes

**1**answer

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

**6**

votes

**2**answers

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

**0**

votes

**1**answer

159 views

### QR factorization: How to get decreasing r_ii

Hi,
I'm attempting to implement a QR factorization with column pivoting so that the returned R matrix has decreasing diagonal elements (that is, $r_{i,i} \leq r_{i-1,i-1}$ for all $i\geq 2$). ...

**3**

votes

**0**answers

155 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$, ...

**3**

votes

**1**answer

405 views

### Factorization in the Wiener algebra on the unit disc.

Consider the Banach algebra $W^+=\ell^1(\mathbb{Z}^+)$, viewed upon as the analytic functions $f$ on the unit disc $\mathbb{D}$ such that $$\|f\|=\sum_{k\ge0}|a_k|<\infty$$ where
$$f(z)=\sum ...

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

**4**

votes

**2**answers

993 views

### Factoring and solving trinomials

Has the problem of factoring (over the rationals) the general trinomial $ax^n+bx^k+c$ with $a,b,c\in\mathbb{Z}$, $n,k\in\mathbb{N}, n>k>1$ been solved? By solved I mean a classification theorem ...

**12**

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